I have been playing around with this definition of fib with a colleague:

fib n = fibs !! n where fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

My initial expectation was that this should take linear time and constant space, but this proved not to be the case: it leaks (a linear amount of) space. We fixed this by replacing (!!) with a version that is strict in the head of its first argument, effectively forcing the list to be strict as far as is needed.

With that fix we could quite happily do { print $ fib 1000000 } and all was well, so I tried to write a Criterion benchmark to show that the time taken was linear in n. And the space leak reappeared!

Looking at the core, I think what had happened was that GHC had spotted that the inner definition of fibs didn't depend on n and floated it out to the top level so it could be shared between calls. Normally a good move, but in this case it's a disaster as it's much quicker to recalculate the list as needed than to keep it around for next time, for sufficiently large values of n.

Now I'm a bit stuck: how do you prevent this from happening? Obviously here we could just implement fibs differently, but as a more general question, how would you prevent unwanted sharing from taking place?

Cheers,

David