了解Haskell中的递归斐波那契函数 [英] Understanding recursive fibonacci function in Haskell

问题描述

尽管此线程可用，但我不允许在答案下(由于声誉得分)问我的问题，因此我不得不为此创建一个新问题. (我只是stackoverflow中的新手而已:)

Although this thread were available, I wasn't allowed to ask my question under the answers (due to reputation points) therefore I had to create a new question for that regard. (I am just new in stackoverflow :)

关于以下fibs函数的工作原理，我并不清楚:

I didn't clearly understand one point regarding how following fibs function works

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

在此 stackoverflow线程

nichijou在我从nichijou引用的这里的线程下面逐步解释了这个问题:

nichijou has step by step explained below the thread here I quoted from nichijou:

首先，我们有第三个和第三个有尾巴的纤维.

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

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

现在，我们知道第三个是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, ?

现在是第五名:

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

以此类推..

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

我的问题是，在第二步之后，我们如何摆脱列表中的重复项?我期望看到第二步应该生成一个列表，

Here my question is, after the second step how did we get rid of the duplicates in the list? I was expecting to see the second step should generate a list as

[1, 1, 2, 2, 3] 

下一步继续进行，依此类推...

same goes in the next step and so on...

推荐答案

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

Let's write this out with some more labels:

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

然后，开始步骤"是

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

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

Now, as the computation marches on, the runtime don't move anything or whatever, it merely tries to fill in ? signs with concrete values. Remember, everything in Haskell is immutable; when I write ? I just mean I don't know yet what the value there is, but in principle it's already predetermined.

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

In this case, the runtime knows that the first ? in fibs comes from the head of sumft, whose exact value is known by now:

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

现在，此2在tfi中也被称为:

Now, this 2 is also known in tfi:

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

...因此我们可以执行下一个添加:

...and thus we can perform the next addition:

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

因此，也可以在其中使用另一个数字，即sumft的另一个元素，它是fibs的一部分.但是它仍然出现在相对于sumft 头的位置，即在2之后.

So, another number, i.e. another element of sumft that, being part of fibs, can also be used there. But it still occurs at the same place relative to the head of sumft – i.e. after the 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, ?, ?,

...等等，依此类推.

...and so on and so on.

这篇关于了解Haskell中的递归斐波那契函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！