Почему встроенная функция применяется к слишком небольшому числу аргументов, которые считаются находящимися в нормальной форме со слабой головой?
Определение Хаскелла гласит:
Выражение в слабой нормальной форме головы (WHNF), если оно либо:
- конструктор (в конечном итоге применяется к аргументам), как True, Just (квадрат 42) или (:) 1
- встроенная функция применяется к слишком малому количеству аргументов (возможно, ни к одному), например (+) 2 или sqrt.
- или лямбда-абстракция \x -> выражение.
Почему встроенные функции получают специальную обработку? Согласно лямбда-исчислению, нет разницы между частично примененной функцией и любой другой функцией, потому что в конце мы имеем только один аргумент функции.
2 ответа
Обычная функция, примененная к аргументу, например:
(\x y -> x + 1 : y) 1
Можно уменьшить, чтобы дать:
\y -> 1 + 1 : y
В первом выражении "самой внешней" вещью было приложение, поэтому оно не было в WHNF. Во-вторых, самая внешняя вещь - это лямбда-абстракция, поэтому она есть в WHNF (хотя мы могли бы сделать больше сокращений внутри тела функции).
Теперь давайте рассмотрим применение встроенной (примитивной) функции:
(+) 1
Поскольку это встроенная функция, в ней нет тела функции, в котором мы можем заменить 1
для первого параметра. Оценщик "просто знает", как оценить полностью "насыщенные" приложения (+)
, лайк (+) 1 2
, Но ничего нельзя сделать с частично примененным встроенным; все, что мы можем сделать, - это создать структуру данных, описывающую "применить (+) к 1 и ждать еще один аргумент", но это именно то, что мы пытаемся уменьшить. Так что мы ничего не делаем.
Встроенные модули являются особыми, потому что они не определены выражениями лямбда-исчисления, поэтому процесс сокращения не может "заглянуть внутрь" их определения. Таким образом, в отличие от приложений с обычными функциями, приложения встроенных функций необходимо "сокращать", просто накапливая аргументы до тех пор, пока они не станут полностью "насыщенными" (в этом случае сокращение до WHNF происходит путем запуска любой магической реализации встроенной функции)., Ненасыщенные встроенные приложения не могут быть сокращены дальше, и поэтому уже в WHNF.
Рассматривать
Прелюдия> let f n = [(+x) | х <- [1..]]!! N
Prelude> let g = f 20000000:: Int -> Int
g
на данный момент не в WHNF! Вы можете увидеть это, оценив, скажем, g 3
, который занимает заметную задержку, потому что вам нужно WHNF, прежде чем вы можете применить аргумент. Именно тогда список просматривается в поисках правильной встроенной функции. Но потом этот выбор затем фиксируется, g
это WHNF (и действительно NF: то же самое для лямбд, возможно, то, что вы имели в виду с вашим вопросом), и поэтому любые последующие вызовы немедленно дадут результат.