haskell - Haskell函数中的自引用

我正在学习Haskell，我在Haskell Wiki上使用了以下表达式
真的让我感到困惑:

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

我不太清楚为什么这行得通。

如果我应用标准的Currying逻辑(zipWith (+))返回一个以list为参数的函数，然后返回另一个以另一个list为参数的函数，然后返回一个列表(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),?,?..]

我的逻辑正确吗？

有没有更简单的方法来解释这一点？ (了解Haskell编译器对该代码有何作用的人有何见解？)(欢迎链接和引用)

的确，这种类型的代码仅由于懒惰的评估而起作用？

当我执行fibs !! 4时会发生什么评估？

此代码是否假定zipWith首先处理元素？ (我认为不应该，但是我不明白为什么不这样做)

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的所有先前计算的值。免费备忘录!

共享在堆中看起来像什么？

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

终止的事实主要取决于懒惰。