# Why is there a space leak here?

Michal Gajda mg169780@students.mimuw.edu.pl
Mon, 28 May 2001 23:25:21 +0200 (CEST)

```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*

```