Spróbuję wyjaśnić w prosty sposób. Jak zauważyli inni, głowa w normalnej formie nie dotyczy Haskella, więc nie będę tego tutaj rozważał.
Normalna forma
Wyrażenie w normalnej formie jest w pełni oceniane i żadne podwyrażenie nie może być dalej oceniane (tj. Nie zawiera niezbadanych zespołów).
Wszystkie te wyrażenia są w normalnej formie:
42
(2, "hello")
\x -> (x + 1)
Te wyrażenia nie są w normalnej formie:
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 forma
Wyrażenie w postaci normalnej słabej głowy zostało ocenione do najbardziej zewnętrznego konstruktora danych lub abstrakcji lambda ( głowa ). Podwyrażenia mogły, ale nie musiały być ocenione . Dlatego każde wyrażenie normalnej formy jest również w słabej formie normalnej głowy, chociaż odwrotnie nie ma to miejsca w ogóle.
Aby ustalić, czy wyrażenie ma słabą głowę w normalnej formie, musimy spojrzeć tylko na najbardziej zewnętrzną część wyrażenia. Jeśli jest to konstruktor danych lub lambda, ma on normalną słabą głowę. Jeśli jest to aplikacja funkcyjna, nie jest.
Te wyrażenia są w normalnej formie słabej 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 wyżej wymienione wyrażenia w postaci normalnej są również w słabej postaci normalnej.
Te wyrażenia nie są w normalnej formie słabej 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łnienie stosu
Ocena wyrażenia do postaci normalnej słabej głowy może wymagać uprzedniej oceny innych wyrażeń w WHNF. Na przykład, aby ocenić 1 + (2 + 3)WHNF, musimy najpierw ocenić 2 + 3. Jeśli ocena pojedynczego wyrażenia prowadzi do zbyt wielu z tych zagnieżdżonych ocen, wynikiem jest przepełnienie stosu.
Dzieje się tak, gdy budujesz duże wyrażenie, które nie generuje żadnych konstruktorów danych ani lambd, dopóki duża jego 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
Zwróć uwagę, jak musi sięgać dość głęboko, zanim zdoła uzyskać wyraz w normalnej formie słabej głowy.
Możesz się zastanawiać, dlaczego Haskell nie zmniejsza z wyprzedzeniem wewnętrznych wyrażeń? Wynika to z lenistwa Haskella. Ponieważ ogólnie nie można założyć, że każde podwyrażenie będzie potrzebne, wyrażenia są oceniane z zewnątrz w.
(GHC ma analizator dokładności, który wykryje pewne sytuacje, w których podwyrażenie jest zawsze potrzebne, i może następnie ocenić je z wyprzedzeniem. Jest to jednak tylko optymalizacja i nie powinieneś na nim polegać, aby uchronić Cię przed przepełnieniem).
Z drugiej strony tego rodzaju wyrażenie jest całkowicie bezpieczne:
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 zmusić wewnętrzne części do oceny przed czasem.
seq
seqto specjalna funkcja używana do wymuszania oceny wyrażeń. Jego semantyka seq x yoznacza, że ilekroć yjest oceniana jako słaba głowa w normalnej formie, xjest również oceniana w postaci słabej głowa w normalnej formie.
Jest to między innymi miejsca stosowane 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 ten sposób unika się tworzenia dużego wyrażenia, a zatem unika się 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 w HaskellWiki, nie oszczędza cię to we wszystkich przypadkach, ponieważ akumulator jest oceniany tylko do WHNF. W tym przykładzie akumulator jest krotką, więc wymusi jedynie ocenę konstruktora krotki, a nie acclub 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 sprawić, aby ocena konstruktora krotek wymusiła ocenę acci 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.
![Szacowanie wartości (4, [1, 2]) krok po kroku. Pierwszy etap jest całkowicie nieoceniony; wszystkie kolejne formy są w WHNF, a ostatnia jest również w normalnej formie.](https://i.stack.imgur.com/1leiT.png)