[Haskell] space behaviour of lazy recursive lists
ahey at iee.org
Sun Jan 30 14:44:31 EST 2005
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.
More information about the Haskell