Why is there a space leak here?

[David Bakin]

Ah, thank you for pointing out concat to me.  (Oddly, without knowing about
concat, I had tried foldr1 (++) and also foldl1 (++) but got the same space
problem and so tried to 'factor it out'.)

OK, now I see what's going on - your explanation is good, thanks.

Which of the various tools built-in or added to Hugs, GHC, NHC, etc. would
help me visualize what's actually going on here?  I think Hood would (using
a newer Hugs, of course, I'm going to try it).  What else?

-- Dave


----- Original Message -----
From: "Tom Pledger" <Tom.Pledger@peace.com>
To: "David Bakin" <davidbak@cablespeed.com>
Cc: <haskell-cafe@haskell.org>
Sent: Monday, May 28, 2001 1:59 PM
Subject: Why is there a space leak here?


> David Bakin writes:
>  :
>  | 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
>
> a) Look at how much of the list needs to exist at any one time.
>
>  | -- 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]
>
> When you consume the (3N)th cell of v, you can't yet garbage collect
> the Nth cell because it will be needed for generating the (3N+1)th,
> (3N+2)th and (3N+3)th.
>
> So, as you proceed along the list, about two thirds of it must be
> retained in memory.
>
>  | -- 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]
>
> By contrast, when you consume the (N+1)th cell of this v, you free up
> the Nth, so foo2 runs in constant space.
>
>  | -- flatten a list-of-lists
>  | flatten :: [[a]] -> [a]
>  :
>
> Rather like concat?
>
> Regards,
> Tom
>