[Haskell] space behaviour of lazy recursive lists

[Axel Jantsch]

Hi,

Both variants of the strict zipWith solved the gibs problem I posed:

   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
   by Simon MArlow

and 

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

However, they do not directly solve my problem in the bigger program which
still has the same linearly growing memory requirement. The problem seems to be
very, very hard to find. I suspect it is related to lazyness as in the gibs
example, but I just cannot put my finger on the code that needs to be
changed. Is there any good method to track down this kind of problem? (I
tried all the ghc memory profiling techniques, that seemed promising to
me.)

Thanks to all that responded to my question!
--Axel

Axel Jantsch writes:
 > 
 > 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)
 > 
Main> nth 200 fibs
 >   10
 >   (5618 reductions, 7430 cells, 1 garbage collection)
 > 
 > which suggests linear space behaviour. Also, ghc shows the same behaviour
 > with a linearly growing stack size as shown by the profiler (+RTS -hc -xt)
 > and sooner or later the program runs out of memory with a stack overflow. 
 > 
 > It seems the entire list up to the last evaluated element is stored. Since
 > I want to use lazy streams to simulate process networks, I want to run the
 > simulation arbitrarily long without *ever* running out of memory. 
 > 
 > So my question is, how can I process recursive, lazy streams in constant
 > space? 
 > 
 > Or, in other words, 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?
 > 
 > With best regards
 > Axel Jantsch
 > 
 > 
 > ---
 > Phone: +46 8 790 4124, Email: axel at imit.kth.se, Web: www.imit.kth.se/~axel
 > _______________________________________________
 > Haskell mailing list
 > Haskell at haskell.org
 > http://www.haskell.org/mailman/listinfo/haskell
 > 
 > 

---
Phone: +46 8 790 4124, Email: axel at imit.kth.se, Web: www.imit.kth.se/~axel