Haskell Fibonacci解释

Question

我对Haskell很陌生,我试图围绕Fibonacci序列的懒惰表达如何工作.

我知道之前已经问过这个问题,但是没有一个答案解决了我在查看结果时遇到的问题.

代码是使用的规范 zipWith

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

我理解以下内容:

1. zipWith 字面上将两个列表拉到一起
2. tail 抓取除列表的第一个元素之外的所有元素
3. Haskell将'to-be'计算数据引用为thunks.

从我的理解,它首先添加[0,1,<thunk>]和[1,<thunk>]使用zipWith (+)给予[1,<thunk>].所以现在你有

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

我用谷歌搜索过的很多参考文献都开始将上面的线"可视化"为

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

我的问题是:

为什么 fibs 上面一行中 的组件只对应[1,1,<thunk>] 而不是 [0,1,1,<thunk>]？

不应该fibs包含整个列表加<thunk>？

Answer 1

这个中间步骤是错误的,因为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
     :