Ответ 1

Я попытаюсь дать объяснение в простых выражениях. Как указывали другие, голова нормальная форма не относится к Haskell, поэтому я не буду здесь ее рассматривать.

Нормальная форма

Выражение в нормальной форме полностью оценивается, и никакое подвыражение не может быть оценено дальше (т.е. не содержит не оцененных разрывов).

Все эти выражения находятся в нормальной форме:

42
(2, "hello")
\x -> (x + 1)

Эти выражения не имеют нормальной формы:

1 + 2                 -- we could evaluate this to 3
(\x -> x + 1) 2       -- we could apply the function
"he" ++ "llo"         -- we could apply the (++)
(1 + 1, 2 + 2)        -- we could evaluate 1 + 1 and 2 + 2

Нормальная форма слабой головки

Выражение в слабой форме головы головы было оценено с помощью внешнего конструктора данных или абстракции лямбда (головы). Подвыражения могут быть или не быть оценены. Поэтому каждое выражение нормальной формы также находится в слабой нормальной форме головы, хотя противоположное вообще не выполняется.

Чтобы определить, находится ли выражение в слабой форме головы, нам нужно только посмотреть на внешнюю часть выражения. Если это конструктор данных или лямбда, он находится в слабой головной нормальной форме. Если это приложение функции, это не так.

Эти выражения находятся в слабой головной нормальной форме:

(1 + 1, 2 + 2)       -- the outermost part is the data constructor (,)
\x -> 2 + 2          -- the outermost part is a lambda abstraction
'h' : ("e" ++ "llo") -- the outermost part is the data constructor (:)

Как уже упоминалось, все выражения нормальной формы, перечисленные выше, также находятся в слабой головной нормальной форме.

Эти выражения не находятся в слабой нормальной форме головы:

1 + 2                -- the outermost part here is an application of (+)
(\x -> x + 1) 2      -- the outermost part is an application of (\x -> x + 1)
"he" ++ "llo"        -- the outermost part is an application of (++)

Переполнение стека

Оценка выражения для нормальной нормальной формы головы может потребовать, чтобы другие выражения сначала оценивались в WHNF. Например, чтобы оценить 1 + (2 + 3) на WHNF, сначала нужно оценить 2 + 3. Если оценка одного выражения приводит к слишком большому числу этих вложенных оценок, результатом является переполнение стека.

Это происходит, когда вы создаете большое выражение, которое не создает никаких конструкторов данных или лямбда, пока не будет оценена большая его часть. Это часто связано с использованием такого рода foldl:

foldl (+) 0 [1, 2, 3, 4, 5, 6]
 = foldl (+) (0 + 1) [2, 3, 4, 5, 6]
 = foldl (+) ((0 + 1) + 2) [3, 4, 5, 6]
 = foldl (+) (((0 + 1) + 2) + 3) [4, 5, 6]
 = foldl (+) ((((0 + 1) + 2) + 3) + 4) [5, 6]
 = foldl (+) (((((0 + 1) + 2) + 3) + 4) + 5) [6]
 = foldl (+) ((((((0 + 1) + 2) + 3) + 4) + 5) + 6) []
 = (((((0 + 1) + 2) + 3) + 4) + 5) + 6
 = ((((1 + 2) + 3) + 4) + 5) + 6
 = (((3 + 3) + 4) + 5) + 6
 = ((6 + 4) + 5) + 6
 = (10 + 5) + 6
 = 15 + 6
 = 21

Обратите внимание, что он должен пройти достаточно глубоко, прежде чем он может получить выражение в слабой форме головы.

Вы можете удивиться, почему Haskell не сокращает внутренние выражения раньше времени? Это из-за ленивости Хаскелла. Поскольку в общем случае нельзя предположить, что потребуется любое подвыражение, выражения оцениваются извне.

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

Это выражение, с другой стороны, абсолютно безопасно:

data List a = Cons a (List a) | Nil
foldr Cons Nil [1, 2, 3, 4, 5, 6]
 = Cons 1 (foldr Cons Nil [2, 3, 4, 5, 6])  -- Cons is a constructor, stop. 

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

seq

seq - это специальная функция, которая используется для принудительного вычисления выражений. Его семантика состоит в том, что seq x y означает, что всякий раз, когда y оценивается в слабой нормальной форме головы, x также оценивается в слабой нормальной форме головы.

Это среди других мест, используемых в определении foldl', строгий вариант foldl.

foldl' f a []     = a
foldl' f a (x:xs) = let a' = f a x in a' `seq` foldl' f a' xs

Каждая итерация foldl' вынуждает аккумулятор к WHNF. Поэтому он избегает создания большого выражения и поэтому избегает.

foldl' (+) 0 [1, 2, 3, 4, 5, 6]
 = foldl' (+) 1 [2, 3, 4, 5, 6]
 = foldl' (+) 3 [3, 4, 5, 6]
 = foldl' (+) 6 [4, 5, 6]
 = foldl' (+) 10 [5, 6]
 = foldl' (+) 15 [6]
 = foldl' (+) 21 []
 = 21                           -- 21 is a data constructor, stop.

Но, как упоминается в примере HaskellWiki, это не спасает вас во всех случаях, так как аккумулятор оценивается только WHNF. В этом примере накопитель представляет собой кортеж, поэтому он будет только принудительно оценивать конструктор кортежа, а не acc или len.

f (acc, len) x = (acc + x, len + 1)

foldl' f (0, 0) [1, 2, 3]
 = foldl' f (0 + 1, 0 + 1) [2, 3]
 = foldl' f ((0 + 1) + 2, (0 + 1) + 1) [3]
 = foldl' f (((0 + 1) + 2) + 3, ((0 + 1) + 1) + 1) []
 = (((0 + 1) + 2) + 3, ((0 + 1) + 1) + 1)  -- tuple constructor, stop.

Чтобы этого избежать, мы должны сделать так, чтобы оценка конструктора кортежа оценивала значение acc и len. Мы делаем это, используя seq.

f' (acc, len) x = let acc' = acc + x
                      len' = len + 1
                  in  acc' `seq` len' `seq` (acc', len')

foldl' f' (0, 0) [1, 2, 3]
 = foldl' f' (1, 1) [2, 3]
 = foldl' f' (3, 2) [3]
 = foldl' f' (6, 3) []
 = (6, 3)                    -- tuple constructor, stop.

Ответ 2

Раздел Thunks and Weak Head Normal Form в Haskell Wikibooks описание лень дает очень хорошее описание WHNF вместе с этим полезным изображением:

Поэтапная оценка значения (4, [1, 2]). Первый этап полностью неоценимый; все последующие формы находятся в WHNF, а последние один также находится в нормальной форме.

Ответ 3

Программы Haskell являются выражениями, и они выполняются путем оценки.

Чтобы оценить выражение, замените все приложения-функции на их определения. Порядок, в котором вы это делаете, не имеет большого значения, но он по-прежнему важен: начните с самого внешнего приложения и продолжайте слева направо; это называется ленивой оценкой.

Пример:

   take 1 (1:2:3:[])
=> { apply take }
   1 : take (1-1) (2:3:[])
=> { apply (-)  }
   1 : take 0 (2:3:[])
=> { apply take }
   1 : []

Оценка останавливается, когда больше нет приложений для замещения. Результат - нормальная форма (или уменьшенная нормальная форма, RNF). Независимо от того, в каком порядке вы оцениваете выражение, вы всегда окажетесь в той же нормальной форме (но только если оценка завершается).

Существует несколько иное описание для ленивой оценки. А именно, в нем говорится, что вы должны все оценивать только в слабой форме головы. Существует всего три случая выражения в WHNF:

• Конструктор: constructor expression_1 expression_2 ...
• Встроенная функция с слишком небольшим количеством аргументов, например (+) 2 или sqrt
• Лямбда-выражение: \x -> expression

Другими словами, глава выражения (т.е. внешнего приложения функции) не может быть оценена дальше, но аргумент функции может содержать неоцененные выражения.

Примеры WHNF:

3 : take 2 [2,3,4]   -- outermost function is a constructor (:)
(3+1) : [4..]        -- ditto
\x -> 4+5            -- lambda expression

Примечания

• "Голова" в WHNF не относится к заголовку списка, а к внешнему функциональному приложению.
• Иногда люди называют неоцененные выражения "thunks", но я не думаю, что это хороший способ понять это.
• Головная нормальная форма (HNF) не имеет отношения к Haskell. Он отличается от WHNF тем, что тела лямбда-выражений также оцениваются в некоторой степени.

Ответ 4

Хорошее объяснение с примерами приведено в http://foldoc.org/Weak+Head+Normal+Form Начальная нормальная форма упрощает даже биты выражения внутри абстракции функции, тогда как "слабая" голова нормальная форма останавливается при абстракциях функций.

Из источника, если у вас есть:

\ x -> ((\ y -> y+x) 2)

который находится в слабой головной нормальной форме, но не соответствует нормальной форме... потому что возможное приложение застревает внутри функции, которая еще не может быть оценена.

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

Ответ 5

WHNF не хочет оценивать тело лямбда, поэтому

WHNF = \a -> thunk
HNF = \a -> a + c

seq хочет, чтобы его первый аргумент находился в WHNF, поэтому

let a = \b c d e -> (\f -> b + c + d + e + f) b
    b = a 2
in seq b (b 5)

оценивается как

\d e -> (\f -> 2 + 5 + d + e + f) 2

вместо того, что будет использовать HNF

\d e -> 2 + 5 + d + e + 2

Ответ 6

В принципе, предположим, что у вас есть какой-то thunk, t.

Теперь, если мы хотим оценить t для WHNF или NHF, которые являются теми же, за исключением функций, мы обнаружили бы, что получаем что-то вроде

t1 : t2 где t1 и t2 - thunks. В этом случае t1 будет вашим 0 (точнее, thunk to 0 без дополнительной распаковки)

seq и $! evalute WHNF. Обратите внимание, что

f $! x = seq x (f x)