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