Haskell斐波那契数列解释

Question

我对Haskell还比较新，试图理解Fibonacci数列的惰性表达方式。

我知道这个问题以前已经问过了，但是没有一个答案涉及到我遇到的可视化结果的问题。

代码使用 zipWith 是标准的。

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

我理解如下：

1. zipWith 直接将两个列表合并成一个列表。
2. tail 获取除了列表中第一个元素以外的所有元素。
3. Haskell将“待计算”数据称为 thunks。

从我的理解来看，它首先使用 zipWith (+) 将 [0,1,<thunk>] 和 [1,<thunk>] 相加，得到 [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>吗？

- MikamiHero

---

理解这些定义的好方法是命名中间值，随着我们逐步访问它们（例如，在“take 3 fibs”中）。这样就不会混淆两次访问相同数据（通过相同名称），或者两个相等的数据片段（每个都有自己的名称）。 - Will Ness

这里有一个答案，其中有漂亮的图片说明了这个定义的工作原理。 - Will Ness

“so now you have” 代码是错误的。正确的应该是 fibs = 0 : 1 : 1 : zipWith (+) (drop 1 $ fibs) (drop 1 $ tail fibs)，因为此时我们已经沿着列表前进了一步。这就是你问题的答案所在。 - Will Ness

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
     :

- Joni

---

+1 谢谢您的解释，@Joni。我想我现在开始明白了，但我还有一个问题，它与我的原始问题有些联系。在你的第四行中，你有 fibs = 0 : 1 : 1 : zipWith(+) [1,1,...] [1,...]，为什么在 zipWith(+) 后面的列表只有 [1,1,...] 而不是整个列表呢？ - MikamiHero

zipWith接受一对项目，对它们应用函数，并在输入列表的尾部上递归。也许我应该进一步扩展这个概念。 - Joni

如果您不介意详细解释一下，我将非常感激！我对Haskell非常陌生，这让我感到困惑（无意冒犯）。 - MikamiHero

非常感谢您详细解答我的问题。非常感激！不幸的是，我没有15个声望，所以无法为您的回答点赞 :( - MikamiHero

@MikamiHero 我之前已经给出了类似的解释，可能会让你对此有一个稍微不同的理解。Joni的回答也很好。 - bheklilr

@bheklilr 谢谢你的链接。我会去看看 :) - MikamiHero

Answer 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, ...

- Nick Ziebert