# Why is there a space leak here?

Tom Pledger Tom.Pledger@peace.com
Tue, 29 May 2001 08:59:04 +1200

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

```