我正在学习 Haskell,我在 Haskell Wiki 上的以下表达式
真的让我很困惑:
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
我不太明白为什么会这样。
如果我应用标准柯里化(Currying)逻辑
(zipWith (+))
返回一个将列表作为参数的函数,然后返回另一个将另一个列表作为参数的函数,并返回一个列表(zipWith::(a -> b -> c) -> [a] -> [b] -> [c]
)。所以,fibs
是对列表的引用(尚未评估)和(tail fibs)
是同一个(未评估的)列表的尾部。当我们尝试评估 ( take 10 fibs
) 时,前两个元素绑定(bind)到 0
和 1
.换句话说fibs==[0,1,?,?...]
和 (tail fibs)==[1,?,?,?]
.第一次添加完成后fibs
变成 [0,1,0+1,?,..]
.同样,在第二次加法之后,我们得到 [0,1,0+1,1+(0+1),?,?..]
fibs !! 4
时会发生什么评估? EDIT2:我刚刚发现上述问题被问到并得到了很好的回答here .如果我浪费了任何人的时间,我很抱歉。
编辑:这是一个更难理解的案例(来源:Project Euler forums):
filterAbort :: (a -> Bool) -> [a] -> [a]
filterAbort p (x:xs) = if p x then x : filterAbort p xs else []
main :: Int
main = primelist !! 10000
where primelist = 2 : 3 : 5 : [ x | x <- [7..], odd x, all (\y -> x `mod` y /= 0) (filterAbort (<= (ceiling (sqrt (fromIntegral x)))) primelist) ]
请注意
all (\y -> x mod y /= 0)...
如何在这里引用 x 不会导致无限递归?
最佳答案
我会为你追踪评估:
> fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
和:
> zipWith f (a:as) (b:bs) = f a b : zipWith f as bs
> zipWith _ _ _ = []
> tail (_:xs) = xs
> tail [] = error "tail"
所以:
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
↪ fibs = 0 : 1 : ((+) 0 1 : zipWith (+) (tail fibs) (tail (tail fibs)))
↪ fibs = 0 : 1 : 1 : ((+) 1 1 : zipWith (+) (tail (tail fibs)) (taii (tail (tail fibs)))))
↪ fibs = 0 : 1 : 1 : 2 : ((+) 1 2 : zipWith (+) (tail (tail (tail fibs))) (tail (taii (tail (tail fibs))))))
↪ fibs = 0 : 1 : 1 : 2 : 3 : ((+) 2 3 : zipWith (+) (tail (tail (tail (tail fibs)))) (tail (tail (taii (tail (tail fibs)))))))
等等。因此,如果您对该结构进行索引,它将强制对 fibs 的每一步进行评估,直到找到索引为止。
为什么这样有效?一个字:分享。
如
fibs
计算后,它在堆中增长,记录计算机的值。稍后回溯到 fibs
get 重用所有先前计算的 fibs
的值.免费内存!堆中的共享是什么样的?
当您请求列表末尾的对象时,Haskell 计算下一个值,记录它,并将自引用向下移动到一个节点。
这终止的事实在很大程度上取决于懒惰。
关于haskell - Haskell 函数中的自引用,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6365708/