Haskell: Что такое нормальная форма слабой головы?

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

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

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

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

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

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

WHNF = thunk : thunk HNF = 0 : thunk NF = 0 : 1 : 2 : 3 : [] 

Как seq и ($!) Относятся к WHNF и HNF?

Обновить

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

Еще одна путаница в Haskell Wiki, в которой говорится, что seq сводится к 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

    Я попытаюсь дать объяснение в простых выражениях. Как указывали другие, нормальная форма головы не относится к 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 

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

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

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

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

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

    Это происходит, когда вы создаете большое выражение, которое не создает каких-либо конструкторов данных или lambda, пока не будет оценена большая его часть. Они часто вызваны таким использованием 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 xy означает, что всякий раз, когда y оценивается в слабой нормальной форме головы, x также оценивается как слабая нормальная форма головы.

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

     foldl' fa [] = a foldl' fa (x:xs) = let a' = fax in a' `seq` foldl' fa' 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. 

    В разделе « Тонкая и слабая головная нормальная форма» в описании Haskell Wikibooks лень представляет собой очень хорошее описание WHNF наряду с этим полезным изображением:

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

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

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

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

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

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

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

    Программы 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. Иногда люди называют неоценимые выражения «thunks», но я не думаю, что это хороший способ понять это.
    3. Начальная нормальная форма (HNF) не имеет отношения к Haskell. Он отличается от WHNF тем, что тела lambda-выражений также оцениваются в некоторой степени.

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

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

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

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

    оценивает

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

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

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

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

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

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

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

     f $! x = seq x (fx) 
    Interesting Posts

    Я получаю сообщение «java.lang.ClassNotFoundException: com.google.gson.Gson», даже если оно определено в моем пути к classам

    Проблемы с рендерингом в студии

    В Angular, как вы определяете активный маршрут?

    Как использовать событие нажатия клавиши в AngularJS?

    Почему Windows 7 предполагает наличие нового сетевого соединения при подключении к существующей точке доступа?

    Удаление руткита из системы Windows XP Pro

    Как заставить Selenium WebDriver щелкнуть элемент, который в настоящее время не отображается?

    Проверьте, содержит ли строка ни одну из строк из массива

    Можно ли использовать однопоточную программу для использования нескольких ядер?

    Как установить .NET framework 1.1 для Windows 7

    Получить HTML внутри iframe с помощью jQuery

    Как вы отслеживаете, какие пакеты были установлены на Fedora (Linux)?

    Как очистить папку Windows \ Installer в Windows 10?

    Настроить мышь или клавиатуру для имитации левого клика и удержания или быстрого щелчка левой кнопкой мыши в Windows?

    Открыть терминал gnome программно и выполнить команды после выполнения bashrc

    Давайте будем гением компьютера.