Haskell函数中的自我引用

Question

Haskell函数中的自我引用

haskellrecursionlazy-evaluationself-reference

9

我正在学习Haskell，以下来自Haskell Wiki的表达式真让我感到困惑：

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

我不太明白为什么这个代码会起作用。

如果应用标准的柯里化逻辑 (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 处理元素是从前往后的？（我认为不应该，但我不明白为什么不应该）

编辑2: 我刚刚在这里找到了上述问题的答案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不会导致无限递归吗？这里的x是自由变量，它在函数外部定义。

- Vladimir Bychkovsky

这看起来很正确。对我来说也很简单——随着你更多地使用Haskell，你的大脑会开始掌握这些模式，它对你来说也会变得简单。很好的开端。 - luqui

2

首先，filterAbort 与 takeWhile 相同。其次，你可以通过写 [7,9..] 来避免偶数。第三，如果你使用 [5,7..]，就不需要在你的初始列表中有 5。最后，这个方法有效的原因相当深奥。这是因为对于每个素数 p，在 p^2 之前有另一个素数。这是 Lindemann 定理（一个介于 p 和 2p 之间的素数）的自然结果。 - augustss

谢谢，augustss。您建议的优化和清理是有道理的。至于终止条件，您能详细说明一下吗？在(\y -> x mod y /= 0)中，x绑定到什么？我怀疑我的错误在于认为它绑定到一个无限列表上。如果它只绑定到一个值（比如7），那就没有问题了。您能确认一下吗？ - Vladimir Bychkovsky

1

x 绑定到一个来自无限列表 [7..] 的单个元素。这里没有递归。 - yatima2975

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Don Stewart · Accepted Answer

我会为您跟踪评估过程：

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

With:

随着：

> 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计算的所有值。免费记忆！

这种共享在堆中是什么样子？

enter image description here

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

这种终止依赖于惰性。