Why does Haskell's "do nothing" function, id, consume tons of memory?

Question

Haskell has an identity function which returns the input unchanged. The definition is simple: ``` id :: a -> a id x = x ``` So for fun, this should output `8`: ``` f = id id id id id id id id id id id id id id id id id id id id id id id id id id id main = print $ f 8 ``` After a few seconds (and about 2 gb of memory according to Task Manager), compilation fails with `ghc: out of memory`. Similarly, the interpreter says `ghci: out of memory`. Since `id` is a pretty simple function, I wouldn't expect it to be a memory burden at run time or compile time. What is all the memory being used for?

Accepted Answer

We know the type of `id`,

```
id :: a -> a
```

And when we specialize this for `id id`, the left copy of `id` has type:

```
id :: (a -> a) -> (a -> a)
```

And then when you specialize this again for the leftmost `id` in `id id id`, you get:

```
id :: ((a -> a) -> (a -> a)) -> ((a -> a) -> (a -> a))
```

So you see each `id` you add, the type signature of the leftmost `id` is twice as large.

Note that types are deleted during compilation, so this will only take up memory in GHC. It won't take up memory in your program.

Why does Haskell's "do nothing" function, id, consume tons of memory?

Solution

Problem