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