As you've apparently discovered, the trick is to be lazy but not too lazy. That is, you want to generate the list lazily but compute a partial result (i.e., the running total of that part of the list processed so far) strictly.
Thanks for all reactions. Now my simplified examples indeed run in constant space. Unfortunatelly, my original code still suffer from the same problem and even '-O2' does not help.
More importantly, understand how foldl' works and be ready to apply the same analysis and fix to any similar function.
This is what I cannot do for the moment. How do I find out what is really going on. Any pointers to a relevant articles/literature? As an example, here is my earlier attempt to define strictFoldl1: strictFoldl1' f (a:b:c) = let strictFoldl1' f a (b:c) = let fab = seq a $ seq b $ f a b in case c of [] -> fab otherwise -> seq fab (strictFoldl1' f fab c) in strictFoldl1' f a (b:c) However, it does not seem to do the trick, why Alastair's code does it: foldl' :: (a -> b -> a) -> a -> [b] -> a foldl' f a [] = a foldl' f a (x:xs) = (foldl' f $! f a x) xs foldl1' f (x:xs) = foldl' f x xs Thanks. Jan -- ------------------------------------------------------------------------- Jan Kybic <kybic@ieee.org> Odyssee, INRIA, Sophia-Antipolis, France or <Jan.Kybic@sophia.inria.fr>,tel. work +33 492 38 7589, fax 7845 http://www-sop.inria.fr/robotvis/personnel/Jan.Kybic/