[Haskell] space behaviour of lazy recursive lists

karczma at info.unicaen.fr karczma at info.unicaen.fr
Sun Jan 30 12:35:23 EST 2005


Ben Rudiak-Gould writes: 

> Axel Jantsch wrote:

> >>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

In both cases Hugs seems to consume the memory at the same rate as the
original program. 

Jerzy Karczmarczuk 




More information about the Haskell mailing list