Why is there a space leak here?

[David Bakin]

Why is there a space leak in foo1 but not in foo2?  (I.e., in Hugs Nov '99) foo1 eats cells (and eventually runs out) where foo2 doesn't.   That is, if I do (length (foo1 1000000)) I eventually run out of cells but (length (foo2 1000000)) runs fine (every GC returns basically the same amount of space).  Something must be wrong in flatten but it follows the pattern of many functions in the prelude (which I'm trying to learn from).   I have been puzzling over this for nearly a full day (getting this reduced version from my own code which wasn't working).  In general, how can I either a) analyze code looking for a space leak or b) experiment (e.g., using Hugs) to find a space leak?  Thanks!  -- Dave   -- This has a space leak, e.g., when reducing (length (foo1 1000000)) foo1 m   = take m v     where       v = 1 : flatten (map triple v)       triple x = [x,x,x]   -- This has no space leak, e.g., when reducing (length (foo2 1000000)) foo2 m   = take m v     where       v = 1 : flatten (map single v)       single x = [x]   -- flatten a list-of-lists flatten :: [[a]] -> [a] flatten []             = [] flatten ([]:xxs)       = flatten xxs flatten ((x':xs'):xxs) = x' : flatten' xs' xxs flatten' [] xxs        = flatten xxs flatten' (x':xs') xxs  = x': flatten' xs' xxs