CODEWITHSUNDEEP
haskellfibonacci
Aydin Yasar
Aydin Yasar

Reputation: 23

Understanding recursive fibonacci function in Haskell

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 :)

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

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

In this stackoverflow thread

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

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)

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

Upvotes: 2

Views: 265

Answers (1)

leftaroundabout
leftaroundabout

Reputation: 120751

Let's write this out with some more labels:

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

Then, the “starting step” is

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

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.

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

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

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

That gets again used in tfi

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

...and so on and so on.

Upvotes: 7

Related Questions