Fibonacci sequence generation

Question

I was writing a fibonacci sequence generator, and I was trying to understand the following code in Haskell

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

I understand what zipWith is, but I do not exactly know how the program executes and why it does generate all the fibonacci numbers. I was trying to understand why it does not terminate using the environment concept in functional languages as follows:

Initially, because Haskell's lazy evaluation, the binding in the env should be fibs : [1,1,x], then to evaluate fibs, the interpreter evaluates x which is zipWith (+) fibs (tail fibs) in this case. When evaluating zipWith, it gets fibs : [1,1,2,x], again because of the lazy evaluation of Haskell. And fibs in env is bound to [1,1,2,x] at this time. However, to fully evaluate fibs, it continues to evaluate x and we go back to the previous steps.

Is this correct?

Besides, I noticed that when I ran the program above in ghci, it instantly prompts the fibonacci sequence it currently has computed, why? Shouldn't it print the result once it finishes all the computation?

Answer 1

So, most of your reasoning is correct. In particular, you described correctly how each new element of the list is evaluated in terms of older ones. You are also correct that to fully evaluate fibs would require repeating the steps you outlined and would, in fact, loop forever.

The key ingredient you're missing is that we don't have to fully evaluate the list. A binding like fibs = ... just assigns a name to the expression; it does not require evaluating the whole list. Haskell will only evaluate as much of the list as it needs to run main. So, for example, if our main is

main = print $ fibs !! 100

Haskell will only calculate the first 100 elements of fibs (following the steps you outlined) but will not need any more than that and will not loop forever.

Moreover, even if we are evaluating the whole thing (which will loop forever), we can use the parts we've calculated as we go along. This is exactly what's happening when you see the value of fibs in ghci: it prints as much as it can as each element is being calculated and does not have to wait until the whole list is ready.

Seeing Strictness in GHCi

You can see how much of a list is evaluated in ghci using the :sprint command which will print a Haskell data structure with _ for the parts that haven't been evaluated yet (called "thunks"). You can use this to see how fibs gets evaluated in action:

Prelude> let fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
Prelude> :sprint fibs
fibs = _
Prelude> print $ fibs !! 10
89
Prelude> :sprint fibs
fibs = _

Oops, that's not what we expected! In fact, this is a case where the lack of the monomorphism restriction is a problem! fibs gets a polymorphic type

Prelude> :t fibs
fibs :: Num a => [a]

which means it behaves like a function call each time you use it, not like a normal value. (In the background, GHC implements instantiating the Num type class as passing in a dictionary to fibs; it's implemented like a NumDictionary a -> [a] function.)

To really understand what's going on, we'll need to make fibs monomorphic explicitly. We can do this by loading it from a module where the restriction is active or by giving it an explicit type signature. Let's do the latter:

Prelude> let fibs :: [Integer]; fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
Prelude> :sprint fibs
fibs = _
Prelude> print $ fibs !! 10
89
Prelude> :sprint fibs
fibs = 1 : 1 : 2 : 3 : 5 : 8 : 13 : 21 : 34 : 55 : 89 : _

And there you are: you can see which parts of the list needed to be evaluated and which ones didn't to get the 10th element. You can play around with other lists or other lazy data structures to get a good feel for what's going on in the background.

Also, you can take a look at my blog post about this sort of laziness. It goes into greater detail about the fibs example (with diagrams!) and talks about how to use this approach for general memoization and dynamic programming.