[Haskell] space behaviour of lazy recursive lists

[Adrian Hey]

On Sunday 30 Jan 2005 7:40 pm, Adrian Hey wrote:
> 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.
-----------^

Erm, that should be the value of the nth element of course.

Regards
--
Adrian Hey