9

我对 Haskell 还是很陌生，我正试图弄清楚斐波那契数列的惰性表达是如何工作的。

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

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

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

我理解以下内容：

  1. zipWith从字面上将两个列表压缩在一起
  2. tail抓取列表中除第一个元素之外的所有元素
  3. Haskell 将“未来”计算数据引用为thunks.

据我了解，它首先添加[0,1,<thunk>]并[1,<thunk>]使用zipWith (+)to give [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>？

4

2 回答 2

13

这个中间步骤是错误的，因为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
     :
于 2014-11-10T12:28:41.523 回答
2

如何可视化正在发生的事情。 

  1 1 2 3  5  8 13 21 ...   <----fibs
  1 2 3 5  8 13 21 ...      <----The tail of fibs
+_________________________  <----zipWith (+) function
  2 3 5 8 13 21 34 ...

 Finally, add [1, 1] to the beginning
 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
于 2017-01-29T02:48:26.770 回答