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