什么是弱头范式? [英] What is Weak Head Normal Form?

问题描述

弱头范式(WHNF)是什么意思? Head Normal form (HNF)和 Normal Form (NF)是什么意思?

What does Weak Head Normal Form (WHNF) mean? What does Head Normal form (HNF) and Normal Form (NF) mean?

真实世界的Haskell 状态:

熟悉的seq函数将表达式计算为我们称为head的表达式 正常形式(缩写为HNF).一旦到达最外面，它就会停止 构造函数(头").这与正常形式(NF)不同， 完全评估了一个表达式.

The familiar seq function evaluates an expression to what we call head normal form (abbreviated HNF). It stops once it reaches the outermost constructor (the "head"). This is distinct from normal form (NF), in which an expression is completely evaluated.

您还将听到Haskell程序员提到弱头正常形式 (WHNF).对于普通数据，弱磁头正常形式与磁头相同 正常形式.差异仅出现在功能上，也是如此 在这里请关注我们.

You will also hear Haskell programmers refer to weak head normal form (WHNF). For normal data, weak head normal form is the same as head normal form. The difference only arises for functions, and is too abstruse to concern us here.

我已经阅读了一些资源和定义( Haskell Wiki 和 Haskell邮件列表和

I have read a few resources and definitions (Haskell Wiki and Haskell Mail List and Free Dictionary) but I don't get it. Can someone perhaps give an example or provide a layman definition?

我猜这将类似于:

WHNF = thunk : thunk

HNF = 0 : thunk 

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

seq和($!)与WHNF和HNF有何关系?

How do seq and ($!) relate to WHNF and HNF?

我还是很困惑.我知道一些答案说可以忽略HNF.通过阅读各种定义，似乎WHNF和HNF中的常规数据之间没有区别.但是，在功能上似乎确实有所不同.如果没有差异，为什么foldl'需要seq?

I am still confused. I know some of the answers say to ignore HNF. From reading the various definitions it seems that there is no difference between regular data in WHNF and HNF. However, it does seem like there is a difference when it comes to a function. If there was no difference, why is seq necessary for foldl'?

Haskell Wiki还有另一个令人困惑的地方，它指出seq简化为WHNF，并且对以下示例没有任何作用.然后他们说必须使用seq来强制执行评估.那不是强迫它使用HNF吗?

Another point of confusion is from the Haskell Wiki, which states that seq reduces to WHNF, and will do nothing to the following example. Then they say that they have to use seq to force the evaluation. Is that not forcing it to HNF?

常见的新手堆栈溢出代码:

Common newbie stack overflowing code:

myAverage = uncurry (/) . foldl' (\(acc, len) x -> (acc+x, len+1)) (0,0)

了解seq和弱头范式(whnf)的人可以 立即了解这里出了什么问题. (acc + x，len + 1)已经 在whnf中，因此seq(将值减为whnf)对此没有任何作用. 就像原始的foldl范例一样，这段程式码会堆积很多东西， 他们只会在一个元组中.解决方案只是强制 元组的组成部分，例如

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 seq, 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)

-有关Stackoverflow的Haskell Wiki

推荐答案

我将尝试用简单的术语进行解释.正如其他人指出的那样，头部范式不适用于Haskell，因此在这里我将不考虑它.

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.

正常形式的表达式将被完全求值，任何子表达式都无法进行进一步求值(即，它不包含未求值的thunk).

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)

这些表达式的格式不正确:

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

弱头范式

弱头正态形式的表达式已被评估为最外面的数据构造函数或lambda抽象( head ).子表达式可能已评估或未评估.因此，尽管通常情况并非相反，但每个范式表达式也都具有弱头范式.

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.

要确定表达式是否为弱头正态形式，我们只需要查看表达式的最外层部分即可.如果它是数据构造函数或lambda，则为弱头普通形式.如果是功能应用程序，则不是.

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.

这些表达形式为弱头正常形式:

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 (:)

如上所述，上面列出的所有范式表达式也都是弱头范式.

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 (++)

堆栈溢出

将表达式评估为弱头正常形式可能需要先对WHNF评估其他表达式.例如，要对WHNF评估1 + (2 + 3)，我们首先必须评估2 + 3.如果对单个表达式求值导致这些嵌套求值过多，则结果是堆栈溢出.

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.

当您构建一个较大的表达式时，这种情况会发生，直到不对它的很大一部分进行评估之前，它都不会产生任何数据构造函数或lambda.这些通常是由于foldl的这种用法引起的:

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

请注意在使表达式变为弱头范式之前必须要深入很多.

Notice how it has to go quite deep before it can get the expression into weak head normal form.

您可能想知道，为什么Haskell不提前减少内部表达式?那是因为Haskell的懒惰.由于通常不能假定需要每个子表达式，因此从外部开始对表达式求值.

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.

(GHC有一个严格性分析器，可以检测某些始终需要子表达式的情况，然后它可以提前对其进行评估.但这只是一种优化，但是，您不应依赖它来避免溢出).

(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).

另一方面，这种表达是完全安全的:

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. 

为避免在我们知道必须对所有子表达式进行求值时构建较大的表达式，我们想强制内部部件提前求值.

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.

seq是一个特殊函数，用于强制对表达式求值.它的语义是seq x y表示，每当y被评估为弱头法线形式时，x也会被评估为弱头法线形式.

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.

它是foldl'的严格定义的foldl'定义中使用的其他地方.

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

foldl'的每次迭代都将累加器强制为WHNF.因此，它避免了构建大型表达式，并因此避免了堆栈溢出.

Each iteration of 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.

但是正如HaskellWiki上的示例所提到的，这并不能在所有情况下都为您省钱，因为累加器仅被评估为WHNF.在此示例中，累加器是一个元组，因此它将仅强制评估元组构造函数，而不是acc或len.

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.

为避免这种情况，我们必须做到这一点，以便评估元组构造函数会强制评估acc和len.我们通过使用seq来实现.

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.

这篇关于什么是弱头范式?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！