Что означает Нормальная Форма Слабой Головы (WHNF)? Что означает нормальная форма головы (HNF) и нормальная форма (NF)?

Реальный мир Haskell утверждает:

Привычная функция seq вычисляет выражение к тому, что мы называем нормальной головой (сокращенно HNF). Он останавливается, как только достигает самого внешнего конструктора («головы»). Это отличается от нормальной формы (NF), в которой выражение полностью оценивается.

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

Я прочитал несколько ресурсов и определений ( Haskell Wiki и Список рассылки Haskell и Бесплатный словарь ), но я не понимаю. Может ли кто-нибудь привести пример или дать определение непрофессионала?

Я предполагаю, что это будет похоже на:

WHNF = thunk : thunk

HNF = 0 : thunk 

NF = 0 : 1 : 2 : 3 : []

Как seqи ($!)связаны с WHNF и HNF?

Обновить

Я все еще в замешательстве. Я знаю, что некоторые ответы говорят, чтобы игнорировать HNF. Из прочтения различных определений кажется, что нет никакой разницы между обычными данными в WHNF и HNF. Тем не менее, кажется, что есть разница, когда дело доходит до функции. Если не было разницы, зачем это seqнужно foldl'?

Другая путаница seqсвязана с тем, что Haskell Wiki утверждает, что сводится к WHNF, и ничего не будет делать в следующем примере. Тогда они говорят, что они должны использовать, seqчтобы форсировать оценку. Разве это не принуждает его к HNF?

Общий код переполнения стека новичков:

myAverage = uncurry (/) . foldl' (\(acc, len) x -> (acc+x, len+1)) (0,0)

Люди, которые понимают seq и нормальную форму слабой головы (whnf), могут сразу понять, что здесь не так. (acc + x, len + 1) уже находится в whnf, поэтому seq, который уменьшает значение до whnf, ничего не делает для этого. Этот код будет создавать thunks точно так же, как и в оригинальном примере foldl, они просто будут внутри кортежа. Решение состоит в том, чтобы просто заставить компоненты кортежа, например,

myAverage = uncurry (/) . foldl' 
          (\(acc, len) x -> acc `seq` len `seq` (acc+x, len+1)) (0,0)

- Haskell Wiki на Stackoverflow

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

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

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

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

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.

В разделе « Нормальная форма Thunks и Weak Head» в описании лени на Haskell Wikibooks приводится очень хорошее описание WHNF вместе с этим полезным описанием:

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

Программы на 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

Ноты

1. «Заголовок» в WHNF относится не к заголовку списка, а к самому внешнему приложению функций.
2. Иногда люди называют недооцененные выражения «громкими», но я не думаю, что это хороший способ понять это.
3. Нормальная форма головы (HNF) не имеет значения для Haskell. Он отличается от WHNF тем, что тела лямбда-выражений также оцениваются в некоторой степени.

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

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

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

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

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

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

В принципе, у вас есть какое - то стук, t.

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

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

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

f $! x = seq x (f x)