Haskell Fibonacci Explanation
This intermediate step is wrong because zipWith
has already processed the first pair of items:
fibs = 0 : 1 : 1 : zipWith (+) fibs (tail fibs)
Recall what zipWith does in the general case:
zipWith f (x:xs) (y:ys) = (f x y) : zipWith f xs ys
If you apply the definition directly you get this expansion:
fibs = 0 : 1 : zipWith (+) fibs (tail fibs) # fibs=[0,1,...]
= 0 : 1 : zipWith (+) [0,1,...] (tail [0,1,...]) # tail fibs=[1,...]
= 0 : 1 : zipWith (+) [0,1,...] [1,...] # apply zipWith
= 0 : 1 : (0+1 : zipWith (+) [1,0+1,...] [0+1,...])
= 0 : 1 : 1 : zipWith (+) [1,1,...] [1,...] # apply zipWith
= 0 : 1 : 1 : (1+1 : zipWith (+) [1,1+1,...] [1+1,...])
= 0 : 1 : 1 : 2 : zipWith (+) [1,2,...] [2,...] # apply zipWith
= 0 : 1 : 1 : 2 : (1+2 : zipWith (+) [2,1+2,...] [1+2,...])
= 0 : 1 : 1 : 2 : 3 : zipWith (+) [2,3...] [3,...] # apply zipWith
:
How to visualize what's going on.
1 1 2 3 5 8 13 21 ... <----fibs
1 2 3 5 8 13 21 ... <----The tail of fibs
+_________________________ <----zipWith (+) function
2 3 5 8 13 21 34 ...
Finally, add [1, 1] to the beginning
1, 1, 2, 3, 5, 8, 13, 21, 34, ...