Postaram się wyjaśnić w prosty sposób. Jak zauważyli inni, Głowa normalna forma nie ma zastosowania do Haskell, więc nie będę rozważać go tutaj.

Postać normalna

Wyrażenie w postaci normalnej jest w pełni oceniane i żadne pod-wyrażenie nie może być dalej oceniane (tzn. nie zawiera nieprzetworzonych thunksów).

Wszystkie te wyrażenia są w postaci normalnej:

42
(2, "hello")
\x -> (x + 1)

Wyrażenia te nie są w postaci normalnej:

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

Słaba Głowa normalna formularz

Wyrażenie w słabym head w postaci normalnej zostało ocenione do najbardziej oddalonego konstruktora danych lub abstrakcji lambda (head ). Wyrażenia podrzędne mogły być oceniane lub nie . W związku z tym każde wyrażenie postaci normalnej jest również w postaci normalnej głowy, choć przeciwieństwo w ogóle nie występuje.

Aby określić, czy wyrażenie jest w postaci normalnej głowy, musimy tylko spojrzeć na zewnętrzną część wyrażenia. Jeśli to dane konstruktor lub lambda, jest w słabej, normalnej formie. Jeśli jest to aplikacja funkcyjna, to nie jest.

Wyrażenia te są w postaci normalnej głowy:

(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 (:)

Jak wspomniano, wszystkie wyrażenia postaci normalnej wymienione powyżej są również w postaci normalnej głowy.

Wyrażenia te nie są w postaci normalnej głowy:

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 (++)

Przepełnienia stosu

Ocena wyrażenia do postaci normalnej słabej głowy może wymagać, aby inne wyrażenia zostały ocenione do WHNF najpierw. Na przykład, aby ocenić 1 + (2 + 3) do WHNF, najpierw musimy ocenić 2 + 3. Jeśli ocena pojedynczego wyrażenia prowadzi do zbyt wielu zagnieżdżonych ocen, wynikiem jest przepełnienie stosu.

Dzieje się tak, gdy tworzy się duże wyrażenie, które nie tworzy żadnych konstruktorów danych ani lambda, dopóki duża ich część nie zostanie oceniona. Są one często spowodowane przez tego rodzaju użycie 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

Zauważ, jak to musi iść dość głęboko, zanim może dostać ekspresja w słabym kształcie głowy.

Możesz się zastanawiać, dlaczego Haskell nie redukuje wewnętrznych wyrażeń z wyprzedzeniem? To z powodu lenistwa Haskella. Ponieważ nie można ogólnie założyć, że każde podwyrażenie będzie potrzebne, wyrażenia są oceniane z zewnątrz w.

(GHC ma analizator ścisłości, który wykryje pewne sytuacje, w których podekspresja jest zawsze potrzebna, a następnie może ją ocenić z wyprzedzeniem. Jest to jednak tylko optymalizacja, i nie powinieneś na niej polegać, aby uchronić Cię przed przepełnieniami).

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. 

Aby uniknąć budowania tych dużych wyrażeń, gdy wiemy, że wszystkie podwyrażenia będą musiały zostać ocenione, chcemy wymusić, aby wewnętrzne części zostały ocenione z wyprzedzeniem.

seq

seq jest specjalną funkcją, która służy do wymuszania wyrażeń do oceny. Jego semantyka jest taka, że seq x y oznacza, że ilekroć y jest jest również oceniana na słabą formę normalną głowy, x jest również oceniana na słabą formę normalną głowy.

Jest między innymi używany w definicji foldl', ścisłego wariantu foldl.

foldl' f a []     = a
foldl' f a (x:xs) = let a' = f a x in a' `seq` foldl' f a' xs

Każda iteracja foldl' zmusza akumulator do whnf. W związku z tym unika się budowania dużej ekspresji, a tym samym unika przepełnienia stosu.

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.

Ale jak wspomina przykład na HaskellWiki, to nie oszczędza cię we wszystkich przypadkach, ponieważ akumulator jest tylko oceniony na WHNF. W przykładzie akumulator jest krotką, więc wymusi tylko ocenę konstruktora krotki, a nie acc lub 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.

Aby tego uniknąć, musimy uczynić to tak, aby ocena konstruktora krotki wymusiła ocenę acc i len. Robimy to za pomocą 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.