8

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

duplode
  • 33,731
  • 7
  • 79
  • 150
MikamiHero
  • 299
  • 2
  • 6
  • good way to understand such definitions is to [name the interim values](http://stackoverflow.com/a/20978114/849891) 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). – Will Ness Nov 11 '14 at 12:46
  • here's [an answer](https://stackoverflow.com/a/37243672/849891) with nice pictures illustrating the workings of this definition. – Will Ness Sep 02 '19 at 21:06
  • "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. – Will Ness Sep 02 '19 at 21:13

2 Answers2

13

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
     :
Joni
  • 108,737
  • 14
  • 143
  • 193
  • +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? – MikamiHero Nov 10 '14 at 12:39
  • 2
    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 – Joni Nov 10 '14 at 12:45
  • 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). – MikamiHero Nov 10 '14 at 12:47
  • 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 :( – MikamiHero Nov 10 '14 at 12:53
  • @MikamiHero [I've given a similar explanation before](http://stackoverflow.com/a/24705697/839246) that might give you a slightly different perspective on it to increase your understanding. Joni's answer is quite good, though. – bheklilr Nov 10 '14 at 14:15
  • @bheklilr Thank you for linking me. I will check it out :) – MikamiHero Nov 10 '14 at 14:18
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, ...
Nick Ziebert
  • 1,258
  • 1
  • 9
  • 17