<div dir="ltr"><span style="font-family:arial,helvetica,sans-serif;color:rgba(0,0,0,0.870588);font-size:14px;line-height:19px;white-space:pre-wrap;background-color:rgb(250,250,250)">I have been playing around with this definition of fib with a colleague:</span><font face="arial, helvetica, sans-serif"><br style="color:rgba(0,0,0,0.870588);font-size:14px;line-height:19px;white-space:pre-wrap;background-color:rgb(250,250,250)"></font><font face="monospace, monospace"><br style="color:rgba(0,0,0,0.870588);font-size:14px;line-height:19px;white-space:pre-wrap;background-color:rgb(250,250,250)"><span style="color:rgba(0,0,0,0.870588);font-size:14px;line-height:19px;white-space:pre-wrap;background-color:rgb(250,250,250)">fib n = fibs !! n where fibs = 0 : 1 : zipWith (+) fibs (tail fibs)</span></font><font face="arial, helvetica, sans-serif"><br style="color:rgba(0,0,0,0.870588);font-size:14px;line-height:19px;white-space:pre-wrap;background-color:rgb(250,250,250)"><br style="color:rgba(0,0,0,0.870588);font-size:14px;line-height:19px;white-space:pre-wrap;background-color:rgb(250,250,250)"></font><span style="font-family:arial,helvetica,sans-serif;color:rgba(0,0,0,0.870588);font-size:14px;line-height:19px;white-space:pre-wrap;background-color:rgb(250,250,250)">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 </span><span style="color:rgba(0,0,0,0.870588);font-size:14px;line-height:19px;white-space:pre-wrap;background-color:rgb(250,250,250)"><font face="monospace, monospace">(!!)</font></span><span style="font-family:arial,helvetica,sans-serif;color:rgba(0,0,0,0.870588);font-size:14px;line-height:19px;white-space:pre-wrap;background-color:rgb(250,250,250)"> 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.</span><font face="arial, helvetica, sans-serif"><br style="color:rgba(0,0,0,0.870588);font-size:14px;line-height:19px;white-space:pre-wrap;background-color:rgb(250,250,250)"><br style="color:rgba(0,0,0,0.870588);font-size:14px;line-height:19px;white-space:pre-wrap;background-color:rgb(250,250,250)"></font><span style="font-family:arial,helvetica,sans-serif;color:rgba(0,0,0,0.870588);font-size:14px;line-height:19px;white-space:pre-wrap;background-color:rgb(250,250,250)">With that fix we could quite happily </span><span style="color:rgba(0,0,0,0.870588);font-size:14px;line-height:19px;white-space:pre-wrap;background-color:rgb(250,250,250)"><font face="monospace, monospace">do { print $ fib 1000000 }</font></span><span style="font-family:arial,helvetica,sans-serif;color:rgba(0,0,0,0.870588);font-size:14px;line-height:19px;white-space:pre-wrap;background-color:rgb(250,250,250)"> 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!</span><font face="arial, helvetica, sans-serif"><br style="color:rgba(0,0,0,0.870588);font-size:14px;line-height:19px;white-space:pre-wrap;background-color:rgb(250,250,250)"><br style="color:rgba(0,0,0,0.870588);font-size:14px;line-height:19px;white-space:pre-wrap;background-color:rgb(250,250,250)"></font><span style="font-family:arial,helvetica,sans-serif;color:rgba(0,0,0,0.870588);font-size:14px;line-height:19px;white-space:pre-wrap;background-color:rgb(250,250,250)">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.</span><font face="arial, helvetica, sans-serif"><br style="color:rgba(0,0,0,0.870588);font-size:14px;line-height:19px;white-space:pre-wrap;background-color:rgb(250,250,250)"><br style="color:rgba(0,0,0,0.870588);font-size:14px;line-height:19px;white-space:pre-wrap;background-color:rgb(250,250,250)"></font><span style="font-family:arial,helvetica,sans-serif;color:rgba(0,0,0,0.870588);font-size:14px;line-height:19px;white-space:pre-wrap;background-color:rgb(250,250,250)">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?</span><font face="arial, helvetica, sans-serif"><br style="color:rgba(0,0,0,0.870588);font-size:14px;line-height:19px;white-space:pre-wrap;background-color:rgb(250,250,250)"><br style="color:rgba(0,0,0,0.870588);font-size:14px;line-height:19px;white-space:pre-wrap;background-color:rgb(250,250,250)"></font><span style="font-family:arial,helvetica,sans-serif;color:rgba(0,0,0,0.870588);font-size:14px;line-height:19px;white-space:pre-wrap;background-color:rgb(250,250,250)">Cheers,</span><font face="arial, helvetica, sans-serif"><br style="color:rgba(0,0,0,0.870588);font-size:14px;line-height:19px;white-space:pre-wrap;background-color:rgb(250,250,250)"><br style="color:rgba(0,0,0,0.870588);font-size:14px;line-height:19px;white-space:pre-wrap;background-color:rgb(250,250,250)"></font><span style="font-family:arial,helvetica,sans-serif;color:rgba(0,0,0,0.870588);font-size:14px;line-height:19px;white-space:pre-wrap;background-color:rgb(250,250,250)">David</span><br></div>