[Haskell] space behaviour of lazy recursive lists

[Adrian Hey]

On Sunday 30 Jan 2005 4:00 pm, Axel Jantsch wrote:
> Hi,
>
> How can I get constant space behaviour for lazy, recursive streams?
>
> Consider:
> > gibs = 1 : 1 : (zipWith f gibs (tail gibs))
> >        where f x y = min (x + y) 10
>
> This is derived from the fibs text book example, modified to bound the
> memory requirement for each list element.
>
> Evaluating gibs should require constant amount of memory, since the
> computed parts of the list are not needed any more and can be reclaimed.
>
> However, hugs says:
>
> Main> nth 100 fibs
>   10
>   (2818 reductions, 3730 cells, 1 garbage collection)

I think maybe you need a strict version of zipWith, otherwise
even if gibs itself is garbage collected as expected you will
still get 98 lazy applications of f (thunks) before the actual
value of f is demanded. When it is eventually demanded you'll
get a lot of stack use (and maybe an overflow in some situations)
because f is strict in it's arguments. Maybe something like this
would fix the problem..

zipWith' f (x:xs) (y:ys) = let z = f x y
                           in z `seq` (z : zipWith' f xs ys)
zipWith' _ _      _      = []

(Haven't tried it though). Actually this kind of problem worries
the me a lot. Dunno if I'm being unduly anal, but I usually end
up writing strict and lazy versions of most of my HOFs to deal
with this kind of problem, but this isn't a terribly satifactory
solution IMO.

Regards
--
Adrian Hey