Haskell函数中的自引用

Question

我正在学习Haskell,而Haskell Wiki上的以下表达式 让我很困惑:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

我无法弄清楚为什么会这样.

如果我应用标准Currying逻辑,则(zipWith (+))返回一个函数将list作为参数,然后返回另一个函数,该函数将另一个列表作为参数,并返回一个list(zipWith::(a -> b -> c) -> [a] -> [b] -> [c]).因此,fibs是对列表的引用(尚未评估),并且(tail fibs)是相同(未评估)列表的尾部.当我们尝试evaluate(take 10 fibs)时,前两个元素绑定到0和1.换句话说fibs==[0,1,?,?...]和(tail fibs)==[1,?,?,?].第一次添加完成后fibs变为[0,1,0+1,?,..].同样,在第二次添加之后我们得到了[0,1,0+1,1+(0+1),?,?..]

• 我的逻辑是否正确？
• 有没有更简单的方法来解释这个？(知道Haskell编译器对此代码做什么的人的任何见解？)(欢迎链接和参考)
• 确实,这种类型的代码只能用于懒惰的评估吗？
• 我做什么评价fibs !! 4？
• 此代码是否假设zipWith首先处理元素？(我认为不应该,但我不明白为什么不)

编辑2:我刚刚发现上述问题并在此处得到了很好的解答.如果我浪费了任何人的时间,我很抱歉.

编辑:这是一个更难理解的案例(来源:Project Euler论坛):

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不会导致无限递归？

Answer 1

我将为您追踪评估:

> 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重用所有先前计算的值fibs.免费记忆!

堆中的共享是什么样的？

当您在列表末尾请求对象时,Haskell计算下一个值,记录它,并将该自引用向下移动到节点.

这种终止的事实在很大程度上依赖于懒惰.