Haskell Fibonacci Explanation

问题:

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

回答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
     :

回答2:

How to visualize what's going on.

  1 1 2 3  5  8  13  <----fibs
  1 2 3 5  8 13      <----The tail of fibs
+________________    <----zipWith (+) function
  2 3 5 8 13 21      <----New fibs.  13 drops out --nothing to zip with

 finally, add [1, 1] to beginning
 1, 1, 2, 3, 5, 8, 13, 21