113

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?

Ryan
  • 2,378
  • 1
  • 19
  • 29
  • 11
    You want to compose those `id`s. In VIM, with the cursor on the definition of `f`, do this: `:s/id id/id . id ./g`. – Tobias Brandt May 19 '14 at 20:53
  • @TobiasBrandt It doesn't have to be a composition because `id . id` and `id id` do the same thing. Of course, I'm guessing that composition would consume less memory during compilation. – QuantumWiz Jun 07 '22 at 08:03

1 Answers1

137

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.

Dietrich Epp
  • 205,541
  • 37
  • 345
  • 415
  • I remember Okasaki running into some similar trouble when he wrote an RPN calculator embedded in Haskell. – dfeuer May 19 '14 at 21:11
  • 3
    The question, perhaps, is whether GHC should find a way to handle this sort of thing more gracefully. In particular, the type is very large when written out in full, but there's a tremendous amount of duplication—could sharing be used to compress such things? Is there an efficient way to process them? – dfeuer May 19 '14 at 21:15
  • 5
    @dfeuer Try asking for the type in ghci. You'll see by the speed of the response that it must be doing the appropriate sharing. I suspect this sharing is lost--for obvious reasons--once you translate to some other intermediate representation (e.g. core). – Daniel Wagner May 19 '14 at 21:24
  • 4
    This means that if `id` is repeated `n` times, the space of its type is proportional to `2^n`. The type inferred in Ryan's code would need `2^27` references to its type variable in addition to the other structure needed to represent the type, which is probably a lot bigger than you'd expect most types to be. – David Young May 19 '14 at 21:47
  • @DanielWagner, the implicit sharing would have to become explicit, with each component of the type named. I guess the GHC developers don't want to deal with that headache. – dfeuer May 19 '14 at 22:15
  • @dfeuer I think that analysis is basically right, especially considering how uncommon the benefit would be. – Daniel Wagner May 19 '14 at 22:18
  • 58
    Doing type inference naively is double exponential, by cleverly using sharing in the type expressions you can bring it down to just exponential. But not matter what you do, there will be some rather simple expressions that will make the type checker explode. Luckily, these do not occur in practical programming. – augustss May 19 '14 at 22:24