Haskell Fibonacci Explanation

Question

I am quite new to Haskell and I'm trying to wrap my head around how the lazy expression of Fibonacci sequences work.

I know this has been asked before, but none of the answers have addressed an issue I'm having with visualising the result.

The code is the canonical one using zipWith

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

I understand the following:

1. zipWith literally zips two lists together
2. tail grabs all but the first element of a list
3. Haskell references 'to-be' computed data as thunks.

From my understanding, it first adds [0,1,<thunk>] and [1,<thunk>] using zipWith (+) to give [1,<thunk>]. So now you have

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

A lot of references I've Googled have then proceeded to "visualise" the line above as

fibs = 0 : 1 : 1 : zipWith (+) [1,1,<thunk>] ([1,<thunk>]).

My question is this:

Why is the fibs component in the line above only corresponding to [1,1,<thunk>] instead of [0,1,1,<thunk>]?

Shouldn't fibs contain the entire list plus <thunk>?

Tantrum

good way to understand such definitions is to name the interim values that come into existence as we progressively access them (e.g. in take 3 fibs). That way there's no confusion between same piece of data accessed twice (through the same name), or two equal pieces of data (each having its own name). – Doiron

here's an answer with nice pictures illustrating the workings of this definition. – Doiron

"so now you have" code is wrong. it should be fibs = 0 : 1 : 1 : zipWith (+) (drop 1 $ fibs) (drop 1 $ tail fibs), because at this point we have advanced one notch along the list. and therein lies the answer to your question. – Doiron

Answer 1

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
     :

Unroll

+1 Thank you for the explanation, @Joni. I think I am starting to understand it now, but I still have one more question which sort of links to my original question. In your fourth line where you have fibs = 0 : 1 : 1 : zipWith(+) [1,1,...] [1,...], how come the list after zipWith(+) only has [1,1,...] instead of the entire list? – Tantrum

zipWith takes takes a pair of items, applies a function to them, and recurses on the tails of the input lists.. maybe I should expand that further – Unroll

if you wouldn't mind expanding on that, I would greatly appreciate it! I'm very new to Haskell and this has got my head in a loop (no pun intended). – Tantrum

thank you very much for elaborating upon your answer. Much appreciated! Unfortunately, I don't have 15 reputation so I can't upvote your answer :( – Tantrum

@Tantrum I've given a similar explanation before that might give you a slightly different perspective on it to increase your understanding. Joni's answer is quite good, though. – Egidius

@Egidius Thank you for linking me. I will check it out :) – Tantrum

Answer 2

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

Vent