了解 Haskell 中的递归斐波那契函数

Question

尽管此线程可用，但不允许我在答案下提出我的问题（由于声誉点），因此我不得不为此创建一个新问题。（我只是 Whosebug 的新手:)

关于 following fibs 函数的工作原理，我有一点没弄清楚

fibs :: [Integer]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

在这个Whosebug thread

nichijou 已在我引用自 nichijou 的线程下面逐步解释：

at first, with fibs and tail fibs, we can get the 3rd:

fibs                        : [1, 1, ?
tail fibs                   : [1, ?
zipWith (+) fibs (tail fibs): [2, ?

now, we know the 3rd is 2, we can get the 4th:

fibs                        : [1, 1, 2, ?
tail fibs                   : [1, 2, ?
zipWith (+) fibs (tail fibs): [2, 3, ?

now the 5th:

fibs                        : [1, 1, 2, 3, ?
tail fibs                   : [1, 2, 3, ?
zipWith (+) fibs (tail fibs): [2, 3, 5, ?

and so on ..

fibs :: [Integer]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

这里我的问题是，在第二步之后我们如何去除列表中的重复项？我期待看到第二步应该生成一个列表 as

[1, 1, 2, 2, 3]

下一步同理……

Answer 1

让我们用更多标签写出来：

fibs :: [Integer]
fibs = 1 : 1 : sumft
 where sumft = zipWith (+) fibs tfi
       tfi = tail fibs

那么，“开始步骤”就是

           ╭── tfi ───────┈┄··
fibs : [1, 1, ?, ?, ...
              ╰── sumft ──┈┄··
tfi  : [1, ?, ?, ?, ... 
sumft: [2, ?, ?, ?,

现在，随着计算的进行，运行时不会移动任何东西 或其他任何东西，它只是尝试用具体值填充? 符号。请记住，Haskell 中的所有内容都是不可变的；当我写 ? 时，我的意思是我还不知道那里有什么价值，但原则上它已经预先确定了。

在这种情况下，运行时知道 fibs 中的第一个 ? 来自 sumft 的头部，现在知道其确切值：

           ╭─── tfi ──────┈┄··
fibs : [1, 1, 2, ?, ...
              ╰─◀ sumft ──┈┄··
tfi  : [1, ?, ?, ?, ... 
sumft: [2, ?, ?, ?,

现在，这个 2 在 tfi 中也为人所知：

           ╭──▶ tfi ──────┈┄··
fibs : [1, 1, 2, ?, ...
              ╰── sumft ──┈┄··
tfi  : [1, 2, ?, ?, ... 
sumft: [2, ?, ?, ?,

...因此我们可以执行下一个加法：

           ╭─── tfi ──────┈┄··
fibs : [1, 1, 2, ?, ...
              ╰── sumft ──┈┄··
tfi  : [1, 2, ?, ?, ... 
sumft: [2, 3, ?, ?,

因此，另一个数字，即 sumft 的另一个元素，作为 fibs 的一部分，也可以在那里使用。但它仍然出现在 相对于 sumft 头部的相同位置 – 即在 2.

之后

           ╭─── tfi ──────┈┄··
fibs : [1, 1, 2, 3, ...
              ╰─◀ sumft ──┈┄··
tfi  : [1, 2, ?, ?, ... 
sumft: [2, 3, ?, ?,

在 tfi

中再次使用

           ╭──▶ tfi ──────┈┄··
fibs : [1, 1, 2, 3, ...
              ╰── sumft ──┈┄··
tfi  : [1, 2, 3, ?, ... 
sumft: [2, 3, ?, ?,

...等等等等。

Understanding recursive fibonacci function in Haskell