list - Haskell无限递归

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

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

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

最佳答案

我画了一幅画，对您可能会有所帮助。
请注意zipWtih op (x:xs) (y:xs) = (op x y):zipWith xs ys，这是zipWtih似乎在列表中“移动”的方式。它正在读取元素并吐出总和:



这是更详细的分步评估。 (尽管我将粘贴其中的副本，但内存中只有一个副本。)对于我不愿意写出来的事情，我将使用....。

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列表比当前位置更远的指针(一个和两个位置)。