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

112

В 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это довольно простая функция, я бы не ожидал, что это будет нагрузка на память во время выполнения или компиляции. Для чего используется вся память?

haskell ghc Райан
источник
11
Вы хотите составить те ids. В VIM, с курсором на определение f, сделайте следующее: :s/id id/id . id ./g.
Тобиас Брандт

Ответы:

135

Мы знаем тип 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. Это не займет память в вашей программе.

Дитрих Эпп
источник
Я помню, как Окасаки столкнулся с похожей проблемой, когда написал калькулятор RPN, встроенный в Haskell.
dfeuer
3
Вопрос, возможно, в том, следует ли GHC найти способ более изящно справляться с подобными вещами. В частности, тип очень большой при полном написании, но существует огромное количество дублирований - можно ли использовать совместное использование для сжатия таких вещей? Есть ли эффективный способ их обработки?
dfeuer
5
@dfeuer Попробуйте запросить тип в ghci. По скорости ответа вы увидите, что он должен делать соответствующий обмен. Я подозреваю, что это совместное использование теряется - по очевидным причинам - после перевода в какое-то другое промежуточное представление (например, ядро).
Даниэль Вагнер
4
Это означает, что если idповторяется несколько nраз, пространство его типа пропорционально 2^n. Типу, выведенному в коде Райана, потребуются 2^27ссылки на его переменную типа в дополнение к другой структуре, необходимой для представления типа, которая, вероятно, намного больше, чем вы ожидаете от большинства типов.
Дэвид
58
Наивное выполнение вывода типов - это двойная экспоненциальная зависимость, умело используя совместное использование в выражениях типов, вы можете свести его к просто экспоненциальному. Но независимо от того, что вы делаете, будут несколько довольно простых выражений, которые заставят средство проверки типов взорваться. К счастью, в практическом программировании этого не происходит.
augustss