弱主部正規形(WHNF) とはどういう意味ですか?主部正規形(HNF) と正規形(NF) とはどういう意味ですか?
よく知られている 関数は、ヘッド正規形
seq(略して HNF) と呼ばれる形式で式を評価します 。最も外側のコンストラクタ (「ヘッド」) に到達すると停止します。これは 、式が完全に評価される正規形(NF) とは異なります 。また、Haskell プログラマーが弱頭部正規形 (WHNF)について言及しているのを耳にすることもあるでしょう 。通常のデータの場合、弱頭部正規形は頭部正規形と同じです。違いは関数の場合にのみ発生するため、ここではあまりに難解なので考慮しません。
私はいくつかのリソースと定義を読みました（ハスケルウィキそしてHaskell メール リストそして無料辞書) ですが、理解できません。誰か例を挙げたり、わかりやすい定義をしてもらえませんか?
次のような感じになると思います:
WHNF = thunk : thunk
HNF = 0 : thunk
NF = 0 : 1 : 2 : 3 : []
WHNF と HNF はどのように関係しているのseqでしょうか?($!)
アップデート
まだ混乱しています。回答の中には、HNF を無視するようにと書かれているものもあります。さまざまな定義を読むと、WHNF と HNF の通常のデータには違いがないようです。ただし、関数に関しては違いがあるようです。違いがないとしたら、seqに が必要なのはなぜですかfoldl'?
もう一つの混乱点は Haskell Wiki にあります。Haskell Wiki では、 はseqWHNF に還元され、次の例には何も影響しないと述べられています。その後、評価を強制するには を使用する必要があると述べていますseq。これは HNF に強制するのではないのでしょうか?
初心者によくあるスタックオーバーフローコード:
myAverage = uncurry (/) . foldl' (\(acc, len) x -> (acc+x, len+1)) (0,0)seq と弱頭部正規形 (whnf) を理解している人は、ここで何が間違っているのかすぐに理解できるでしょう。 は
(acc+x, len+1)すでに whnf に含まれているので、seq( の定義内のfoldl') は値を whnf に減らしますが、これには何もしません。 このコードは元の例と同じようにサンクを構築しfoldl、それらはタプル内にあります。 解決策は、タプルのコンポーネントを強制することです。例:myAverage = uncurry (/) . foldl' (\(acc, len) x -> acc `seq` len `seq` (acc+x, len+1)) (0,0)
ベストアンサー1
簡単に説明してみます。他の人が指摘しているように、頭部正規形は 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
弱頭部正規形
弱頭部正規形の式は、最も外側のデータ コンストラクタまたはラムダ抽象化 (頭部)まで評価されています。部分式は評価されている場合もされていない場合もあります。したがって、すべての正規形式は弱頭部正規形でもありますが、その逆は一般には当てはまりません。
式が弱頭部正規形であるかどうかを判断するには、式の最も外側の部分を見るだけで済みます。データ コンストラクターまたはラムダの場合は、弱頭部正規形です。関数適用の場合は、そうではありません。
これらの式は弱頭部正規形です:
(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'これは、 の厳密な変形である の定義でも使用されています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 にのみ評価されるため、これはすべてのケースで役立つわけではありません。以下の例では、アキュムレータはタプルであるため、タプル コンストラクターの評価のみが強制され、accorは強制されません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.