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"
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