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

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

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

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

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

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

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

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

этот вид выражения, с другой стороны, совершенно безопасен:

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.