且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事

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

更新时间:2023-02-27 08:56:38

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

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, ?, ?, ?,

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

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.