Я постараюсь дать объяснение в простых терминах. Как уже отмечали другие, нормальная форма головы не относится к Хаскеллу, поэтому я не буду ее здесь рассматривать.
Нормальная форма
Выражение в нормальной форме полностью вычисляется, и никакое подвыражение не может быть оценено в дальнейшем (то есть оно не содержит необработанных блоков).
Все эти выражения в нормальной форме:
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
Слабая голова, нормальная форма
Выражение в нормальной форме со слабой головой было оценено для самого внешнего конструктора данных или лямбда-абстракции ( head ). Подвыражения могут оцениваться или не оцениваться . Поэтому каждое выражение нормальной формы также находится в нормальной форме со слабой головой, хотя в общем случае обратное не имеет места.
Чтобы определить, находится ли выражение в нормальной форме со слабой головой, нам нужно только взглянуть на крайнюю часть выражения. Если это конструктор данных или лямбда, то у него слабая нормальная форма. Если это функциональное приложение, это не так.
Эти выражения в нормальной голове слабые:
(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
Обратите внимание, как оно должно пройти достаточно глубоко, прежде чем оно сможет привести выражение в нормальную форму слабой головы.
Вы можете задаться вопросом, почему Хаскелл не сокращает внутренние выражения раньше времени? Это из-за лени Хаскелла. Поскольку в общем случае нельзя предполагать, что каждое подвыражение будет необходимо, выражения оцениваются извне в.
(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.