什么是弱头标准型(WHNF) ?Head Normal form (HNF)和Normal form (NF)是什么意思?

Real World Haskell声明:

我们熟悉的seq函数将表达式求值为 呼叫头标准型(简称HNF)。它一旦到达就会停止 最外层的构造函数(“head”)。这与正常情况不同 形式(NF),其中表达式被完全求值。 您还会听到Haskell程序员提到弱头正常 表单(WHNF)。对于正规数据,弱头正规形式与 头部正常形式。这种差异只出现在函数中,也是如此 这里涉及到我们的深奥。

我读了一些资源和定义(Haskell维基和Haskell邮件列表和免费字典),但我不明白。谁能举个例子或者给出一个外行的定义?

我猜它会类似于:

WHNF = thunk : thunk

HNF = 0 : thunk 

NF = 0 : 1 : 2 : 3 : []

seq和($!)如何与WHNF和HNF相关?

更新

我还是很困惑。我知道有些答案说忽略HNF。从各种定义来看,WHNF和HNF中的常规数据似乎没有区别。然而,当涉及到函数时,似乎确实有区别。如果没有区别,为什么seq是必要的foldl'?

另一个混淆点来自Haskell Wiki,它声明seq简化为WHNF,并且不会对下面的示例执行任何操作。然后他们说他们必须使用seq来强制求值。这不是强迫它去HNF吗?

Common newbie stack overflowing code: myAverage = uncurry (/) . foldl' (\(acc, len) x -> (acc+x, len+1)) (0,0) People who understand seq and weak head normal form (whnf) can immediately understand what goes wrong here. (acc+x, len+1) is already in whnf, so the seq (in the definition of foldl'), which reduces a value to whnf, does nothing to this. This code will build up thunks just like the original foldl example, they'll just be inside a tuple. The solution is just to force the components of the tuple, e.g. myAverage = uncurry (/) . foldl' (\(acc, len) x -> acc `seq` len `seq` (acc+x, len+1)) (0,0)

-Haskell Wiki在Stackoverflow上


当前回答

头部正常形式意味着没有头部redex

(λx (y(λ。y + x) b)) b

简化为:R,代表redex(是的,它里面还有另一个redex,但这是不相关的)。这是一个头部redex,因为它是最左边的redex(唯一的redex),在它之前没有lambda项(变量或lambda表达式(应用或抽象)),只有0到n个抽象者(如果R是一个redex (λx. a)B, R的抽象者是λx),在这种情况下是0。

因为有一个头部索引,它不在HNF中,因此也不在NF中,因为有一个索引。

WHNF意味着它是一个lambda抽象或在HNF中。上述内容不在HNF中,也不是lambda抽象,而是一个应用程序,因此不在WHNF中。

λx.((λy.y+x)b)b在WHNF中

它是λ抽象,但不是在HNF中因为有一个头部λx。Rb

还原到λx.((b+x)b)。没有redex,所以是正常形式。

考虑λx.(λy.zyx)b),化简为λx。R,所以不在HNF中。λx.(k(λy.zyx)b)化简为λx。因此它是在HNF中,而不是在NF中。

所有的NF均为HNF和WHNF。所有HNF均为WHNF。

其他回答

WHNF不希望对lambdas的主体进行计算,因此

WHNF = \a -> thunk
HNF = \a -> a + c

seq希望它的第一个参数在WHNF中,因此

let a = \b c d e -> (\f -> b + c + d + e + f) b
    b = a 2
in seq b (b 5)

计算结果为

\d e -> (\f -> 2 + 5 + d + e + f) 2

而不是,什么会使用HNF

\d e -> 2 + 5 + d + e + 2

Haskell Wikibooks对懒惰的描述中关于坦克和弱头正常形式的部分提供了对WHNF的非常好的描述,以及以下有用的描述:

逐步计算值(4,[1,2])。第一阶段是 完全未鉴定的;所有随后的形式都在WHNF中,而最后 一个也是正形式。

头部正常形式意味着没有头部redex

(λx (y(λ。y + x) b)) b

简化为:R,代表redex(是的,它里面还有另一个redex,但这是不相关的)。这是一个头部redex,因为它是最左边的redex(唯一的redex),在它之前没有lambda项(变量或lambda表达式(应用或抽象)),只有0到n个抽象者(如果R是一个redex (λx. a)B, R的抽象者是λx),在这种情况下是0。

因为有一个头部索引,它不在HNF中,因此也不在NF中,因为有一个索引。

WHNF意味着它是一个lambda抽象或在HNF中。上述内容不在HNF中,也不是lambda抽象,而是一个应用程序,因此不在WHNF中。

λx.((λy.y+x)b)b在WHNF中

它是λ抽象,但不是在HNF中因为有一个头部λx。Rb

还原到λx.((b+x)b)。没有redex,所以是正常形式。

考虑λx.(λy.zyx)b),化简为λx。R,所以不在HNF中。λx.(k(λy.zyx)b)化简为λx。因此它是在HNF中,而不是在NF中。

所有的NF均为HNF和WHNF。所有HNF均为WHNF。

我试着用简单的语言解释一下。正如其他人指出的那样,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标准形式的表达式已经被求值到最外层的数据构造函数或lambda抽象(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。如果对单个表达式求值会导致太多这样的嵌套求值,则会导致堆栈溢出。

当您构建一个大型表达式时,该表达式直到对其中的大部分进行了计算才会产生任何数据构造函数或lambda,就会发生这种情况。这通常是由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不提前减少内心的表达?那是因为哈斯克尔的懒惰。由于不能一般地假定每个子表达式都需要,所以表达式是由外向内求值的。

(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意味着每当y被求为弱头标准形式时,x也被求为弱头标准形式。

它是用于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。在下面的例子中,累加器是一个元组,因此它只强制求元组构造函数的值,而不是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)  -- 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.

http://foldoc.org/Weak+Head+Normal+Form上给出了一个很好的例子解释,头部范式甚至简化了函数抽象中的表达式位,而“弱”头部范式则止步于函数抽象。

从源头看,如果你有:

\ x -> ((\ y -> y+x) 2)

这是弱头部正常形式,但不是头部正常形式……因为可能的应用程序被卡在一个还不能求值的函数中。

实际的头部标准形式将难以有效地实现。这需要在函数内部进行操作。因此,弱头标准形式的优点是,您仍然可以将函数作为不透明类型来实现,因此它与编译语言和优化更加兼容。