Haskell Fibonacci解释

对于Haskell来说，我还很陌生，我正试图绕过斐波那契序列的惰性表达如何工作。

我知道以前已经有人问过这个问题，但是没有一个答案能解决我在可视化结果时遇到的问题。

该代码是使用zipWith的规范代码

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

我了解以下内容:

zipWith从字面上将两个列表压缩在一起

tail捕获列表

列表中除第一个元素以外的所有元素

Haskell将“将来”的计算数据引用为thunks。

根据我的理解，它首先使用[0,1,<thunk>]添加[1,<thunk>]和zipWith (+)来提供[1,<thunk>]。所以现在你有了

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

然后，我在Google上搜索的许多引用资料就开始将上面的行“可视化”为

fibs = 0 : 1 : 1 : zipWith (+) [1,1,<thunk>] ([1,<thunk>]).

我的问题是这样的:

为什么上一行中的 fibs 组件仅对应于 [1,1,<thunk>] 而不是 [0,1,1,<thunk>] ？
fibs是否应包含整个列表以及<thunk>？

最佳答案

此中间步骤是错误的，因为zipWith已经处理了第一对项目:

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

记忆一下zipWith在一般情况下的作用:

zipWith f (x:xs) (y:ys) = (f x y) : zipWith f xs ys

如果直接应用定义，则会得到以下扩展:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)                # fibs=[0,1,...]
     = 0 : 1 : zipWith (+) [0,1,...] (tail [0,1,...])      # tail fibs=[1,...]
     = 0 : 1 : zipWith (+) [0,1,...] [1,...]               # apply zipWith
     = 0 : 1 : (0+1 : zipWith (+) [1,0+1,...] [0+1,...])
     = 0 : 1 : 1 : zipWith (+) [1,1,...] [1,...]           # apply zipWith
     = 0 : 1 : 1 : (1+1 : zipWith (+) [1,1+1,...] [1+1,...])
     = 0 : 1 : 1 : 2 : zipWith (+) [1,2,...] [2,...]       # apply zipWith
     = 0 : 1 : 1 : 2 : (1+2 : zipWith (+) [2,1+2,...] [1+2,...])
     = 0 : 1 : 1 : 2 : 3 : zipWith (+) [2,3...] [3,...]    # apply zipWith
     :