Haskell无限递归

Question

以下函数计算斐波那契数列：

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

如果我们运行它，将得到一个无限的列表，但是递归是如何工作的呢？如果函数不断调用自身，为什么可以在屏幕上打印数字？我会很感激您能解释编译器如何管理这些调用。

- Razvan Meriniuc

---

两个词：懒惰编程。 - Willem Van Onsem

Answer 1

我画了一张图片，可能对你有帮助。
请注意，zipWith op (x:xs) (y:ys) = (op x y):zipWith xs ys，这就是zipWith沿着列表“移动”的方式。它正在读取元素并输出总和：

---

以下是更详细的逐步计算过程。（虽然我会复制原文中的内容，但内存中只有一个副本。）我将使用....代替我不想写出来的内容。

fib = 0:1:zipWith (+) fib (tail fib)
    = 0:1:zipWith (+) (0:1: .... ) (tail (0:1: .... )
    = 0:1:(0+1:zipWith (+) (1:(0+1: .... )) ( 0+1:..... ))
    = 0:1:1:zipWith (+) (1: ....) (......)

请注意，现在我们知道zipWith(+)fib(tail fib) = 1:.....。

    = 0:1:1:zipWith (+) (1:1: ....) (1:......)
    = 0:1:1:(1+1):zipWith (+) (1:(1+1): .....) ((1+1):....)
    = 0:1:1:2:zipWith (+) (1:2: .....) (2:....)

我会稍微加快速度：

    = 0:1:1:2:(1+2):zipWith (+) (2: .....) (....)
    = 0:1:1:2:3     :zipWith (+) (2:3 .....) (3:....)
    = 0:1:1:2:3:(2+3):zipWith (+) (3:(2+3):.....) ((2+3):.....)
    = 0:1:1:2:3:5     :zipWith (+) (3:5:.....) (5:.....)
    = 0:1:1:2:3:5:8    :zipWith (+) (5:8:....) (8:......)
    = 0:1:1:2:3:5:8:13  :zipWith (+) (8:13:....) (13:......)
    = 0:1:1:2:3:5:8:13:21:zipWith (+) (13:21....) (21:......)

每个阶段，zipWith 函数的最后两个参数就像指向比我们当前所在位置高 (一和两个位置) 的 fib 列表的指针。

- AndrewC

Answer 2

懒惰。在Haskell中，列表更像是生成器：只有在其他地方需要计算值时，它才会计算值。

例如，head [1, 2+3]不会执行加法，因为它不需要。同样，如果我们递归地让ones = 1:ones，那么head ones = head (1:ones) = 1并不需要评估所有的尾部。

你可以猜测一下，如果我们打印一个成对出现的x，它的定义如下：

x = (n, fst x + 1)

上面我们使用了一个（懒惰的）pair而不是（懒惰的）list，但是推理是相同的。除非被其他东西需要，否则不要评估任何东西。

- chi

---

请问您能否解释一下我提供的函数在前几次调用时是如何工作的？它是什么时候决定停止调用自身并计算结果的？在最后一次调用时，zipWith (+) fib (tail fib) 会发生什么？该函数只是简单地返回0:1:[]吗？ - Razvan Meriniuc

“最后通知”或者“停止自我调用”这些说法是错误的，因为Haskell是惰性的，计算直到需要时才会被评估。如果你从fib中取出前4个数，那么Haskell将评估表达式直到它计算出4个元素，然后它将暂停评估。如果你接着取前8个数字，它会恢复计算以获取接下来的四个数字，然后再次暂停直到有需要。这个过程没有“结束”。如果你试图获取所有的数字（例如通过折叠操作），它永远不会完成。 - Alexis King