On Tue, 29 May 2001, Tom Pledger wrote:
David Bakin writes:
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.
Last sentence seems false. You free up Nth cell of v when you finish with 3Nth cell of result.
| -- This has no space leak, e.g., when reducing (length (foo2 1000000)) | foo1 m (...the only difference below:) | single x = [x]
Greetings :-) Michal Gajda korek@icm.edu.pl *knowledge-hungry student*