Почему функция Haskell "ничего не делает", id, потребляет тонны памяти?

Haskell имеет функцию тождества, которая возвращает вход без изменений. Определение прост:

id :: a -> a
id x = x

Итак, для удовольствия это должно выводить 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

Через несколько секунд (и около 2 ГБ памяти в соответствии с диспетчером задач) компиляция завершается с ghc: out of memory. Точно так же интерпретатор говорит ghci: out of memory.

Так как id - довольно простая функция, я бы не ожидал, что это будет памятью во время выполнения или времени компиляции. Для чего используется вся память?

Ответ 1

Мы знаем тип id,

id :: a -> a

И когда мы специализируемся на этом для id id, левая копия id имеет тип:

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

И затем, когда вы снова специализируетесь на самом левом id в id id id, вы получите:

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

Итак, вы видите каждый добавленный id, подпись типа самого левого id в два раза больше.

Обратите внимание, что типы удаляются во время компиляции, поэтому в GHC будет занимать только память. Это не займет память в вашей программе.