[Haskell] space behaviour of lazy recursive lists

[Simon Marlow]

On 30 January 2005 17:09, Ben Rudiak-Gould wrote:

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

Actually, GHC can garbage collect top-level definitions, and it also
floats things out to the top-level precisely because doing so doesn't
affect the space behaviour (any more than floating in general, that is).

Unfortunately in this case, laziness is the culprit.  Each element of
the list is a thunk that refers to the previous two elements of the
list, which are thunks that refer to the previous two elements... and so
on.  So even if you drop the front of the list, each element keeps the
whole list alive until it is evaluated.

Try this:

gibs = 1 : 1 : f gibs (tail gibs)
       where f (x:xs) (y:ys) = z `seq` z : f xs ys
		where z = min (x + y) 10

main = print (head (drop 1000000 gibs))

Cheers,
	Simon