在學(xué)習(xí)《real world Haskell》時對NF、WHNF的概念有些困惑，于是去stackoverflow查了查。本文來源于stackoverflow上的一個提問，大意就是怎么理解Haskell中的WHNF、HNF以及NF。譯文是該提問下票數(shù)最高的回答。
I'll try to give an explanation in simple terms. As others have pointed out, head normal form does not apply to Haskell, so I will not consider it here.
我將試著用一些簡單的術(shù)語來解釋它們。另外，由于Haskell中并沒有用到HNF，所以在這里我就不解釋了。
Normal form
范式
An expression in normal form is fully evaluated, and no sub-expression could be evaluated any further (i.e. it contains no un-evaluated thunks).
These expressions are all in normal form:
42
(2, "hello")
\x -> (x + 1)
一個NF的表達式是可以完全被求值的，并且不存在需要進一步求值的子表達式（包括不可求值的部分）。
這些表達是都是NF的：
42
(2, "hello")
\x -> (x + 1)
These expressions are not in normal form:
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
這些表達式都不是NF的：
1 + 2 -- 我們可以把它求值為 3
(\x -> x + 1) 2 -- 我們可以應(yīng)用這個函數(shù)
"he" ++ "llo" -- 我們可以應(yīng)用 (++)
(1 + 1, 2 + 2) -- 我們可以對 1 + 1 以及 2 + 2求值
Weak head normal form
弱頭范式
An expression in weak head normal form has been evaluated to the outermost data constructor or lambda abstraction (the head). Sub-expressions may or may not have been evaluated. Therefore, every normal form expression is also in weak head normal form, though the opposite does not hold in general.
我們說一個表達式是WHNF（弱頭范式）的，意味著它可以被求值為最外層的值構(gòu)造器或匿名函數(shù)（lambda）抽象（所謂的頭head）。子表達式或許不能被求值。因此，所有NF表達式都滿足WHNF，盡管反對方一般不這么認為。
To determine whether an expression is in weak head normal form, we only have to look at the outermost part of the expression. If it's a data constructor or a lambda, it's in weak head normal form. If it's a function application, it's not.
判斷一個表達式是否滿足WHNF，我們只需要看最外層的表達式。如果是一個值構(gòu)造器或一個匿名函數(shù)，那它就滿足WHNF。如果是一個函數(shù)調(diào)用，那它就不是。
These expressions are in weak head normal form:
(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 (:)
這些表達式是滿足WHNF的：
(1 + 1, 2 + 2) -- 最外層是一個值構(gòu)造器 (,)
\x -> 2 + 2 -- 最外層是一個匿名函數(shù)的抽象
'h' : ("e" ++ "llo") -- 最外層是一個值構(gòu)造器 (:)
As mentioned, all the normal form expressions listed above are also in weak head normal form.
These expressions are not in weak head normal form:
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 (++)
就像之前所提到的，所有以上列出的NF表達式都是符合WHNF的。以下表達式不符合WHNF：
1 + 2 -- 最外層是 (+) 函數(shù)的調(diào)用
(\x -> x + 1) 2 -- 最外層是匿名函數(shù) (\x -> x + 1) 的調(diào)用
"he" ++ "llo" -- 最外層是 (++) 函數(shù)的調(diào)用
Stack overflows
棧溢出
Evaluating an expression to weak head normal form may require that other expressions be evaluated to WHNF first. For example, to evaluate 1 + (2 + 3) to WHNF, we first have to evaluate 2 + 3. If evaluating a single expression leads to too many of these nested evaluations, the result is a stack overflow.
把一個表達式轉(zhuǎn)換為WHNF可能需要先對其他表達式求值使其成為WHNF。舉個栗子，把1+（2+3）轉(zhuǎn)化為WHNF，我們首先必須要對2+3求值。如果一個表達式的求值需要對許多內(nèi)嵌的（子表達式）求值，那么將會導(dǎo)致棧溢出。
This happens when you build up a large expression that does not produce any data constructors or lambdas until a large part of it has been evaluated. These are often caused by this kind of usage of 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
當(dāng)你展開一個大型表達式時，不會打開任何值構(gòu)造器或lambda表達式，直到它的其他部分都已被求值。foldl函數(shù)經(jīng)常被這樣使用：
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
Notice how it has to go quite deep before it can get the expression into weak head normal form.
我們注意到，在表達式轉(zhuǎn)換為WHNF之前，它嵌套的非常之深。
You may wonder, why does not Haskell reduce the inner expressions ahead of time? That is because of Haskell's laziness. Since it cannot be assumed in general that every subexpression will be needed, expressions are evaluated from the outside in.
你可能會奇怪，為什么Haskell不提前減少內(nèi)嵌的表達式呢？因為Haskell是惰性的。一般情況下你并不能假定所有子表達式都需要被求值，表達式的求值是由外而內(nèi)的。
(GHC has a strictness analyzer that will detect some situations where a subexpression is always needed and it can then evaluate it ahead of time. This is only an optimization, however, and you should not rely on it to save you from overflows).
（GHC有一個嚴(yán)格的分析，它會檢測哪些子表達式是必需的，然后提前計算它。但那只是一個優(yōu)化，你不應(yīng)該指望它來保證你的代碼免于棧溢出）
This kind of expression, on the other hand, is completely safe:
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.
換句話說，這類表達式是完全安全的：
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 是一個構(gòu)造器, 停止.
To avoid building these large expressions when we know all the subexpressions will have to be evaluated, we want to force the inner parts to be evaluated ahead of time.
為了避免構(gòu)建這類巨大的表達式，當(dāng)我們知道所有子表達式都將會被求值時，我們必須強制提前對內(nèi)部進行求值。
seq
seq函數(shù)
seq is a special function that is used to force expressions to be evaluated. Its semantics are that seq x y means that whenever y is evaluated to weak head normal form, x is also evaluated to weak head normal form.It is among other places used in the definition of foldl', the strict variant of foldl.
foldl' f a [] = a
foldl' f a (x:xs) = let a' = f a x in a' `seq` foldl' f a' xs
seq是一個特殊的函數(shù)，它用來強制表達式提前被求值。seq x y意味著無論是否y能被求值為WHNF，x都會被轉(zhuǎn)換為WHNF。它在其他地方被使用，例如在foldl'函數(shù)（foldl的一個變體）的定義中
foldl' f a [] = a
foldl' f a (x:xs) = let a' = f a x in a' `seq` foldl' f a' xs
Each iteration of foldl'
foldl' 的每一次迭代
forces the accumulator to WHNF. It therefore avoids building up a large expression, and it therefore avoids overflowing the stack.
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.
強制把累加器轉(zhuǎn)換為WHNF。因此它可以避免構(gòu)建一個巨大的表達式，也因此避免了棧溢出。
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 是一個值構(gòu)造器, 停止.
But as the example on HaskellWiki mentions, this does not save you in all cases, as the accumulator is only evaluated to WHNF. In the example, the accumulator is a tuple, so it will only force evaluation of the tuple constructor, and not acc 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.
但是Haskell維基中提到的一個例子，并不是所有情況都能由此解決，當(dāng)累加器可以求值為WHNF時。比如在那個例子中，累加器是一個元組，因此，它只強制求值到元組的構(gòu)造器，而不是其中的acc和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) -- 元組的構(gòu)造器, 停止.
To avoid this, we must make it so that evaluating the tuple constructor forces evaluation of acc
and len. We do this by using 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.
為了避免這種情況，我們必須強制對元組構(gòu)造器的求值，然后強制對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) -- 元組構(gòu)造器，停止.
