[Haskell] space behaviour of lazy recursive lists

Ben Rudiak-Gould Benjamin.Rudiak-Gould at cl.cam.ac.uk
Sun Jan 30 12:09:01 EST 2005


Axel Jantsch wrote:

 >Consider:
 >
 >>gibs = 1 : 1 : (zipWith f gibs (tail gibs))
 >>       where f x y = min (x + y) 10
 >
 >[...] how can I force the garbage collector to reclaim the
 >memory of the head of the list after I have processed it, since I will
 >never ever reference it again?

There's no entirely satisfactory way to do this. The language standard 
doesn't specify caching behavior, so you have to rely on the way that 
actual implementations handle caching.

I think it's safe in practice to assume that a binding inside a function 
won't be cached across call boundaries, even if the value of the binding 
doesn't depend on the function argument. I.e. you should be able to 
solve your problem with

    makeGibs () = gibs where
      gibs = 1 : 1 : (zipWith f gibs (tail gibs))
      f x y = min (x + y) 10

In principle a compiler could float the definition of gibs outside the 
function makeGibs and cache it across calls, but I don't think any 
compiler will actually do this, precisely because it makes this trick 
stop working.

A more elegant variation which definitely won't be cached is

    gibsFrom a b = gibs where
      gibs = a : b : (zipWith f gibs (tail gibs))
      f x y = min (x + y) 10

-- Ben



More information about the Haskell mailing list