我对 Haskell 还很陌生,我正试图弄清楚斐波那契数列的惰性表达式是如何工作的。
我知道以前有人问过这个问题,但没有一个答案能解决我在可视化结果时遇到的问题。
该代码是使用 zipWith
的规范代码。
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
我理解以下内容:
zipWith
从字面上将两个列表压缩在一起tail
抓取列表中除第一个元素之外的所有元素 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>
?
最佳答案
这个中间步骤是错误的,因为 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
:
关于Haskell 斐波那契解释,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26843529/