Why is there a space leak here?

Tom Moertel tom-list-haskell@moertel.com
Tue, 05 Jun 2001 18:08:44 -0400


Mark Tullsen wrote:
> 
> You have to realize that Alastair Reid is one of the truly
> great Haskell programmers on planet earth.  I'm serious.
> So, when he says "incredibly subtle space leak" I wouldn't
> expect the solution to be simple.

Whoops.  Now don't I feel foolish.

> As far as I can tell, your argument would also apply to foo2,
> which doesn't have a space leak.

Hmmm...  Let's see.

foo2 m 
  = take m v
    where
      v = 1 : flatten (map single v)
      single x = [x]

v = 1 : flatten (map single v)
  = 1 : flatten (map single (1 : flatten (map single v)))
  = 1 : flatten (single 1 : map single (flatten (map single v)))
  = 1 : flatten ([1] : map single (flatten (map single v)))
  = 1 : 1 : flatten (map single (flatten (map single v)))
  = Aaaarrggggh!  You're right.

Now don't I feel double foolish.  :P

Okay, then, what is the *right* way to reason about these things?

Cheers,
Tom