[Haskell-cafe] Preventing sharing

[David Turner]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20151218/699ab5a5/attachment.html>