9

我正在学习 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) 时，前两个元素绑定到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：我刚刚发现上面的问题在这里得到了很好的回答。如果我浪费了任何人的时间，我很抱歉。

编辑：这是一个更难理解的案例（来源：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 不会导致无限递归？

4

1 回答 1

16

我会为你追踪评估：

> 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 计算下一个值，记录它，并将自引用向下移动到一个节点。

这终止的事实在很大程度上取决于懒惰。

于 2011-06-16T00:17:51.723 回答