什么是弱头正常形式？

Question

什么是弱头正常形式？什么是弱头范式（WHNF）是什么意思？什么是头标准型（HNF）和范式（NF）是什么意思？真实世界Haskell说：熟悉的seq函数将表达式计算为我们称之为head normal form（缩写为HNF）的表达式。它一旦到达最外面的构造函数（“头部”）就会停止。这与正常形式（NF）不同，其中表达式被完全评估。您还将听到Haskell程序员引用弱头正常形式（WHNF）。对于正常数据，弱头正常形式与头部正常形式相同。差异只出现在功能上，而且我们在这里无关紧要。我已经阅读了一些资源和定义（Haskell Wiki和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吗？常见的新手堆栈溢出代码：myAverage = uncurry (/) . foldl' (\(acc, len) x -> (acc+x, len+1)) (0,0)了解seq和弱头正常形式（whnf）的人可以立即理解这里出了什么问题。（acc + x，len + 1）已经在whnf中，所以seq将值减少到whnf，对此无效。这段代码将像原始的foldl示例一样构建thunks，它们只是在元组内部。解决方案只是强制元组的组件，例如myAverage = uncurry (/) . foldl'            (\(acc, len) x -> acc `seq` len `seq` (acc+x, len+1)) (0,0)- Stackoverflow上的Haskell Wiki

Answer 1

Haskell中关于Thunks和Weak Head Normal Form的部分Wikibooks 对懒惰的描述提供了对WHNF的非常好的描述以及这个有用的描述：

逐步评估值（4，[1,2]）。第一阶段完全没有评估; 所有后续表格都在WHNF中，最后一个表格也是正常形式。

Answer 2

Haskell程序是表达式，它们通过执行评估来运行。

要评估表达式，请按其定义替换所有函数应用程序。你这样做的顺序并不重要，但它仍然很重要：从最外面的应用程序开始，从左到右进行; 这称为懒惰评估。

例：

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

当没有更多功能应用程序需要更换时，评估停止。结果是正常形式（或缩小的正常形式，RNF）。无论您评估表达式的顺序如何，您总是会以相同的正常形式结束（但仅在评估终止时）。

懒惰评估的描述略有不同。也就是说，它表示你应该只评估所有的弱头正常形式。在WHNF中，表达式恰好有三种情况：

• 构造函数： constructor expression_1 expression_2 ...

• 一个内置函数，参数太少，比如(+) 2或sqrt

• lambda表达式： \x -> 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. 头部正规形式（HNF）与Haskell无关。它与WHNF的不同之处在于，lambda表达式的实体也在某种程度上得到了评估。