Lazy evaluation of terms in an infinite list in Haskell

Question

I am curious about the runtime performance of an infinite list like the one below:

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

This will create an infinite list of the fibonacci sequence.

My question is that if I do the following:

takeWhile (<5) fibs 

how many times does fibs evaluate each term in the list? It seems that since takeWhile checks the predicate function for each item in the list, the fibs list will evaluate each term multiple times. The first 2 terms are given for free. When takeWhile wants to evaluate (<5) on the 3rd element, we will get:

1 : 1 : zipWith (+) [(1, 1), (1)] => 1 : 1 : 3 

Now, once takeWhile wants to evaluate (<5) on the 4th element: the recursive nature of fibs will construct the list again like the following:

1 : 1 : zipWith (+) [(1, 2), (2, 3)] => 1 : 1 : 3 : 5 

It would seem that the 3rd element needs to be computed again when we want to evaluate the value of the 4th element. Furthermore, if the predicate in takeWhile is large, it would indicate the function is doing more work that is needed since it is evaluating each preceding element in the list multiple times. Is my analysis here correct or is Haskell doing some caching to prevent multiple evaluations here?

Answer 1

This is a self-referential, lazy data structure, where "later" parts of the structure refer to earlier parts by name.

Initially, the structure is just a computation with unevaluated pointers back to itself. As it is unfolded, values are created in the structure. Later references to already-computed parts of the structure are able to find the value already there waiting for them. No need to re-evaluate the pieces, and no extra work to do!

The structure in memory begins as just an unevaluated pointer. Once we look at the first value, it looks like this:

> take 2 fibs 

(a pointer to a cons cell, pointing at '1', and a tail holding the second '1', and a pointer to a function that holds references back to fibs, and the tail of fibs.

Evaluating one more step expands the structure, and slides the references along:

And so we go unfolding the structure, each time yielding a new unevaluated tail, which is a closure holding references back to 1st and 2nd elements of the last step. This process can continue infinitely :)

And because we're referring to prior values by name, GHC happily retains them in memory for us, so each item is evaluated only once.

Answer 2

Illustration:

module TraceFibs where  import Debug.Trace  fibs :: [Integer] fibs = 0 : 1 : zipWith tadd fibs (tail fibs)   where     tadd x y = let s = x+y                in trace ("Adding " ++ show x ++ " and " ++ show y                                    ++ "to obtain " ++ show s)                         s 

Which produces

*TraceFibs> fibs !! 5 Adding 0 and 1 to obtain 1 Adding 1 and 1 to obtain 2 Adding 1 and 2 to obtain 3 Adding 2 and 3 to obtain 5 5 *TraceFibs> fibs !! 5 5 *TraceFibs> fibs !! 6 Adding 3 and 5 to obtain 8 8 *TraceFibs> fibs !! 16 Adding 5 and 8 to obtain 13 Adding 8 and 13 to obtain 21 Adding 13 and 21 to obtain 34 Adding 21 and 34 to obtain 55 Adding 34 and 55 to obtain 89 Adding 55 and 89 to obtain 144 Adding 89 and 144 to obtain 233 Adding 144 and 233 to obtain 377 Adding 233 and 377 to obtain 610 Adding 377 and 610 to obtain 987 987 *TraceFibs>