Je vais essayer de donner une explication en termes simples. Comme d'autres l'ont souligné, la forme normale de tête ne s'applique pas à Haskell, je ne l'examinerai donc pas ici.
Forme normale
Une expression sous forme normale est entièrement évaluée, et aucune sous-expression ne peut être évaluée plus loin (c'est-à-dire qu'elle ne contient pas de thunks non évalués).
Ces expressions sont toutes sous forme normale :
42
(2, "hello")
\x -> (x + 1)
Ces expressions ne sont pas sous forme normale :
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
Forme normale de la tête faible
Une expression en forme normale de tête faible a été évaluée jusqu'au constructeur de données ou à l'abstraction lambda le plus éloigné (l'élément tête ). Sous-expressions peut ou non avoir été évalué . Par conséquent, toute expression de forme normale est également en forme normale de tête faible, bien que l'inverse ne soit pas vrai en général.
Pour déterminer si une expression est en forme normale de tête faible, il suffit de regarder la partie la plus extérieure de l'expression. S'il s'agit d'un constructeur de données ou d'un lambda, il est en forme normale de tête faible. Si c'est une application de fonction, elle ne l'est pas.
Ces expressions sont en forme normale de tête faible :
(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 (:)
Comme mentionné, toutes les expressions en forme normale énumérées ci-dessus sont également en forme normale de tête faible.
Ces expressions ne sont pas dans la forme normale de la tête faible :
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 (++)
Débordements de pile
L'évaluation d'une expression en forme normale de tête faible peut nécessiter que d'autres expressions soient évaluées en WHNF d'abord. Par exemple, pour évaluer 1 + (2 + 3) à WHNF, nous devons d'abord évaluer 2 + 3 . Si l'évaluation d'une seule expression entraîne un trop grand nombre de ces évaluations imbriquées, il en résulte un dépassement de pile.
Cela se produit lorsque vous construisez une grande expression qui ne produit pas de constructeurs de données ou de lambdas avant qu'une grande partie de celle-ci n'ait été évaluée. Ces problèmes sont souvent causés par ce type d'utilisation de la fonction 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
Remarquez comment il doit aller assez loin avant de pouvoir transformer l'expression en forme normale de tête faible.
Vous vous demandez peut-être pourquoi Haskell ne réduit pas les expressions internes à l'avance ? C'est à cause de la paresse de Haskell. Puisque l'on ne peut pas supposer en général que chaque sous-expression sera nécessaire, les expressions sont évaluées de l'extérieur vers l'intérieur.
(GHC a un analyseur de rigueur qui détectera certaines situations où une sous-expression est toujours nécessaire et il peut alors l'évaluer à l'avance. Il ne s'agit cependant que d'une optimisation, et vous ne devriez pas compter sur elle pour vous sauver des débordements).
Ce type d'expression, en revanche, est totalement sûr :
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.
Pour éviter de construire ces grandes expressions lorsque nous savons que toutes les sous-expressions devront être évaluées, nous voulons forcer les parties internes à être évaluées à l'avance.
seq
seq est une fonction spéciale qui est utilisée pour forcer les expressions à être évaluées. Sa sémantique est la suivante seq x y signifie que chaque fois que y est évalué en forme normale de tête faible, x est également évalué en forme normale de tête faible.
Il est entre autres utilisé dans la définition de foldl' la variante stricte de foldl .
foldl' f a [] = a
foldl' f a (x:xs) = let a' = f a x in a' `seq` foldl' f a' xs
Chaque itération de foldl' force l'accumulateur à WHNF. Cela évite donc de construire une grande expression, et donc de faire déborder la pile.
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.
Mais comme le mentionne l'exemple sur HaskellWiki, cela ne vous sauve pas dans tous les cas, car l'accumulateur n'est évalué qu'en WHNF. Dans l'exemple, l'accumulateur est un tuple, donc cela ne forcera que l'évaluation du constructeur de tuple, et pas de acc ou 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.
Pour éviter cela, nous devons faire en sorte que l'évaluation du constructeur de tuple force l'évaluation de acc et len . Pour ce faire, nous utilisons 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.
1 votes
On parle généralement de WHNF et de RNF. (RNF étant ce que vous appelez NF)
5 votes
@monadic Que signifie le R de RNF ?
7 votes
@dave4420 : Réduit
0 votes
De nos jours, le WFH est aussi une chose.