哈斯克尔:什么是弱头范式?

弱头范式 (WHNF)是什么意思? 头正常forms (HNF)和正常forms (NF)是什么意思?

真实世界哈斯克尔说:

熟悉的seq函数将expression式评估为我们称之为头标准forms(简称HNF)的expression式。 它一旦到达最外层的构造函数(“头”)就会停下来。 这不同于正常forms(NF),其中expression被完全评估。

你也会听到Haskell程序员提到弱头标准格式(WHNF)。 对于正常的数据,弱头标准forms与头标准forms相同。 function上的区别只在于,在这里关心我们是太深奥了。

我已经阅读了一些资源和定义( 哈斯克尔Wiki和哈斯克尔邮件列表和自由字典 ),但我不明白。 有人可以举一个例子或提供一个外行的定义?

我猜测它会类似于:

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?

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

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

了解seq和弱头正常forms(whnf)的人可以立即明白这里出了什么问题。 (acc + x,len + 1)已经在,所以seq,它减less了一个值,而对此没有任何作用。 这个代码将像原来的foldl例子一样构buildthunk,它们只是在一个元组中。 解决scheme只是强制元组的组件,例如

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

– Stackoverflow上的Haskell Wiki

我会尽量简单地解释一下。 正如其他人指出的,头标准forms不适用于Haskell,所以我不会在这里考虑它。

正常forms

正常forms的expression式得到了充分的评估,没有任何子expression式可以被进一步评估(即它不包含未评估的thunk)。

这些expression式都是正常的forms:

 42 (2, "hello") \x -> (x + 1) 

这些expression式不是正常forms:

 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 

弱头正常forms

弱头标准forms的expression式已经被评估为最外面的数据构造器或lambda抽象( 头部 )。 子expression式可能已经或可能没有被评估 。 因此,每一个正常forms的expression也是处于弱头范式,尽pipe相反并不普遍。

为了确定一个expression式是否处于弱头标准forms,我们只需要看expression式的最外面的部分。 如果它是一个数据构造函数或一个lambda,它是在弱头正常forms。 如果它是一个函数应用程序,它不是。

这些expression式是弱头正常的forms:

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

如上所述,上面列出的所有正常forms的expression式也是弱头标准forms。

这些expression式并不是弱头常态:

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

堆栈溢出

评估一个expression弱头正常forms可能需要其他expression式先评估WHNF。 例如,要评估1 + (2 + 3)到WHNF,我们首先必须评估2 + 3 。 如果评估单个expression式会导致太多的嵌套评估,则结果是堆栈溢出。

当你build立一个大的expression式时,会产生这种情况,除非大部分的expression式被评估,否则不会产生任何数据构造函数或lambdaexpression式。 这些往往是由这种使用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 

注意它是如何进入相当深的,才能将expression式变为弱头标准forms。

你可能会想,为什么Haskell提前减less内部expression呢? 那是因为哈斯克尔的懒惰。 由于一般不能假定每个子expression式都是需要的,所以expression式是从外部进行评估的。

(GHC有一个严格性分析器,它可以检测出总是需要子expression式的情况,然后可以提前对它进行评估,但这只是一种优化,不应该依赖它来避免溢出)。

另一方面,这种expression是完全安全的:

 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. 

为了避免在我们知道所有的子expression式必须被评估的时候build立这些大的expression式,我们要强制内部的部分被提前评估。

seq

seq是一个特殊的函数,用于强制expression式进行评估。 它的语义是seq xy表示当y被评估为弱头标准forms时, x也被评估为弱头标准forms。

它是foldl'定义中使用的其他地方, foldl'的严格变体。

 foldl' fa [] = a foldl' fa (x:xs) = let a' = fax in a' `seq` foldl' fa' xs 

foldl'每次迭代都强制累加器进入WHNF。 因此避免了build立一个大的expression式,因此避免了堆栈溢出。

 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。 在这个例子中,累加器是一个元组,所以它只会强制评估元组的构造函数,而不是acclen

 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. 

为了避免这种情况,我们必须使得评估元组构造器对acclen评估。 我们通过使用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. 

关于懒惰的Haskell Wikibooks 描述中关于Thunks 和Weak Head Normal Form的章节提供了对WHNF的一个很好的描述以及这个有用的描述:

逐步评估值(4,[1,2])。第一阶段完全没有评价;所有后来的形式都在WHNF,最后一个也是正常形式。

逐步评估值(4,[1,2])。 第一阶段完全没有评价; 所有后来的forms都在WHNF,最后一个也是正常forms。

Haskell程序是expression式 ,它们通过执行评估来运行。

为了评估一个expression式,用它们的定义replace所有的函数应用。 这样做的顺序并不重要,但仍然很重要:从最外层的应用程序开始,从左到右进行; 这被称为懒惰评价

例:

  take 1 (1:2:3:[]) => { apply take } 1 : take (1-1) (2:3:[]) => { apply (-) } 1 : take 0 (2:3:[]) => { apply take } 1 : [] 

当没有更多function应用程序需要更换时,评估停止。 结果是正常forms (或简化forms ,RNF)。 无论按照什么顺序评估一个expression式,总是会以相同的标准forms结束(但只有在评估结束时)。

懒惰的评估有一个稍微不同的描述。 也就是说,你应该评估一切只有弱头正常forms 。 在WHNF中有一个expression式恰好有三种情况:

  • 构造函数: constructor expression_1 expression_2 ...
  • (+) 2sqrt参数太less的内置函数
  • 一个lambdaexpression式: \x -> expression

换句话说,expression式的头部(即最外面的函数应用程序)不能被进一步评估,但函数参数可能包含未评估的expression式。

WHNF的例子:

 3 : take 2 [2,3,4] -- outermost function is a constructor (:) (3+1) : [4..] -- ditto \x -> 4+5 -- lambda expression 

笔记

  1. WHNF中的“头”不是指列表的头部,而是指最外面的函数应用程序。
  2. 有时候,人们称之为“thunk”,但我不认为这是理解它的好方法。
  3. 头标准forms (HNF)与Haskell无关。 它不同于WHNF,lambdaexpression式的主体也在一定程度上被评估。

http://foldoc.org/Weak+Head+Normal+Form中给出了一个很好的例子说明。头标准forms简化了函数抽象中expression式的位,而“弱”头标准forms在函数抽象。;

从源头上看,如果你有:

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

那就是弱头正常forms,而不是头正常forms…因为可能的应用程序被卡在一个无法评估的函数中。

实际的头部正常forms将难以有效实施。 这将需要在function的内部戳动。 所以弱头标准forms的好处在于,你仍然可以将函数作为一个不透明的types来实现,因此它与编译语言和优化更加兼容。

WHNF不希望lambda的身体被评估,所以

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

seq希望它的第一个参数在WHNF,所以

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

评估

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

而不是,什么将使用HNF

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

基本上,假设你有一些thunk, t

现在,如果我们想要评估t到WHNF或者NHF,除了函数,它们是相同的,我们会发现我们得到了类似

t1 : t2其中t1t2是thunk。 在这种情况下, t1将会是你的0 (或者说,没有额外的拆箱)

seq$! 评估WHNF。 注意

 f $! x = seq x (fx) 
Interesting Posts