Elegant way in Haskell to output Fibonacci numbers using zipWith

Question

I saw this implementation of the Fibonacci numbers in Haskell and I am still trying to figure out why this works properly. So apperently, the Fibonacci numbers can be written in a very compact way using the zipWith function. The implementation looks like the following

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

To understand better what is happening here I looked at the documentation of the zipWith function. This function adds two lists [a], [b] together using the given function (a -> b -> c). In our case the function is a simple addition. If the two lists [a] and [b] have different length (in our case list [b] is always one element shorted than list [a]) zipWith simply starts at the beginning of both lists and adds them. If the end of one list is reached it just stops no matter if the end of the other list is already reached.

In the first step of the recursion zipWith is called with [0,1] and tail[0,1] = [1]. This leads to another 1 => [0, 1, 1]. In the second step of the recursion zipWith gets called with [0,1,1] and [1,1] resulting in [0+1,1+1] = [1,2]. So for me it is clear that the recursion creates the right fibonacci numbers but I don't fully understand why only the last number after the zipWith step is added to the result and not the whole list. Maybe someone can explain it to me. That would be super helpful. Thank you very much.

Your `[b]` list is not shorter. Both sides have infinite length. — bitmask, Sep 03 '19 at 10:24
Related: https://stackoverflow.com/q/37243102/4942760 and https://stackoverflow.com/q/26843529/4942760 — Dan Robertson, Sep 03 '19 at 10:32

score 5 · Accepted Answer · edited Sep 03 '19 at 10:52

The entire list is added eventually. In Haskell you do not assign a value to a variable. You declare a variable, and you can not change the value of a variable since these are immutable. The list is thus not [0, 1], it is [0, 1, …], with … something that is at that moment not evaluated yet.

Initially the list thus looks like:

    ┌───────────────────────────────────┐
    │           ┌─────────────────────┐ │
    ▼           ▼                     | │
┌---┼---┐   ┌---┼---┐   ┌-----------┐ | │
| ∙ | ∙────▶| ∙ | ∙────▶|  zipWith  | | │
└-│-┴---┘   └-│-┴---┘   ├-----------┤ | │
  ▼           ▼         |(+)| ∙ | ∙ | | │
  0           1         └-----│---│-┘ | │
                              │   └───┘ │
                              └─────────┘

If you later decide to evaluate the next item of the list, zipWith will calculate the sum of the heads of the lists to which it refers, so [0,1,…] and [1,…], which is one. It will thus emit 1, and recurse on the tails of the two lists:

                ┌───────────────────────────────────┐
                │           ┌─────────────────────┐ │
                ▼           ▼                     | │
┌---┬---┐   ┌---┼---┐   ┌---┼---┐   ┌-----------┐ | │
| ∙ | ∙────▶| ∙ | ∙────▶| ∙ | ∙────▶|  zipWith  | | │
└-│-┴---┘   └-│-┴---┘   └-│-┴---┘   ├-----------┤ | │
  ▼           ▼           ▼         |(+)| ∙ | ∙ | | │
  0           1           1         └-----│---│-┘ | │
                                          │   └───┘ │
                                          └─────────┘

So now the list is [0,1,1,…]. If we then force the system to evaluate the next item, it will again sum up the heads of the lists, so [1,1,…] and [1,…], which is 2:

                            ┌───────────────────────────────────┐
                            │           ┌─────────────────────┐ │
                            ▼           ▼                     | │
┌---┬---┐   ┌---┬---┐   ┌---┼---┐   ┌---┼---┐   ┌-----------┐ | │
| ∙ | ∙────▶| ∙ | ∙────▶| ∙ | ∙────▶| ∙ | ∙────▶|  zipWith  | | │
└-│-┴---┘   └-│-┴---┘   └-│-┴---┘   └-│-┴---┘   ├-----------┤ | │
  ▼           ▼           ▼           ▼         |(+)| ∙ | ∙ | | │
  0           1           1           2         └-----│---│-┘ | │
                                                      │   └───┘ │
                                                      └─────────┘

and so on. The list is thus an infinite list, but the tail is evaluated lazily.

score 3 · Answer 2 · answered Sep 03 '19 at 10:28

The lists don’t have changing lengths. The length is always infinity, we just don’t know about most of the elements.

First recall that the following are equivalent:

[1,2,3]
1:2:3:[]

In this case we will write ... for the tail of the list which has not yet been evaluated. So initially we have

fibs = 0 : 1 : ...

And to inspect the ... (to see if it is [] or something that looks like n : ...), we evaluate some of the call to zipWith

Now consider what zipWith will do:

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

But note, of course, that these evaluation steps only happen as one iterates through the elements of fibs (e.g. evaluating take 5 fibs will evaluate the first steps)

Elegant way in Haskell to output Fibonacci numbers using zipWith

2 Answers2