Ответ 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.
![Evaluating the value (4, [1, 2]) step by step. The first stage is completely unevaluated; all subsequent forms are in WHNF, and the last one is also in normal form.](/img/bdae4535276836613de15acefd847c02.png)