Tom Moertel wrote:
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
Tom, I don't know if this approach is the *right* way but it's one way. This approach is very brute force, and I'm sure there are experts out there who can think and reason at a much higher level than this. But the brute force approach is this: Start evaluating your program symbolically You can do this at the source level using a CBN (call-by-need) calculus. If the program (the program in CBN includes the "heap") starts growing in size faster than expected then you have a space leak. Simple, but a bit tedious. It would be great if we had a tool that could output such a trace. - Mark