簡単な言葉で説明しようと思います。他の人が指摘しているように、head の正規形は Haskell には適用されないため、ここでは考慮しません。
通常形
通常の形式の式は完全に評価され、サブ式はそれ以上評価できません (つまり、未評価のサンクは含まれません)。
これらの式はすべて通常の形式です。
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 正規形の式は、最も外側のデータ コンストラクターまたはラムダ抽象化 ( 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
式を弱い頭の標準形にする前に、かなり深くまで行かなければならないことに注意してください。
なぜ Haskell は事前に内部式を簡約しないのでしょうか? それは Haskell の怠惰さによるものです。一般に、すべての部分式が必要になるとは想定できないため、式は外側から内側に評価されます。
(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れるたびに、も弱い頭部標準形に評価されることを意味します。yx
foldl'これは、 の厳密な変形であるの定義で使用される他の場所の 1 つです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以下の例では、accumulator はタプルであるため、 orではなく、タプル コンストラクターの評価のみを強制し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これを回避するには、タプルコンストラクターを評価するとandの評価が強制されるようにする必要があり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.
![値 (4, [1, 2]) を段階的に評価します。 最初の段階はまったく評価されていません。 後続のすべての形式は WHNF であり、最後の形式も通常の形式です。](https://i.stack.imgur.com/1leiT.png)