14

Haskell定义说：

一个表达式是弱头范式（WHNF），如果它是：

  • 一个构造函数（最终应用于参数），例如 True、Just (square 42) 或 (:) 1
  • 一个内置函数应用于太少的参数（可能没有），如 (+) 2 或 sqrt。
  • 或 lambda 抽象 \x -> 表达式。

为什么内置函数会受到特殊对待？根据 lambda 演算，部分应用函数与任何其他函数之间没有区别，因为最后我们只有一个参数函数。

4

2 回答 2

22

应用于参数的普通函数，如下所示：

(\x y -> x + 1 : y) 1

可以减少，给出：

\y -> 1 + 1 : y

在第一个表达式中，“最外层”的东西是一个应用程序，所以它不在 WHNF 中。其次，最外层的东西是 lambda 抽象，所以它在 WHNF 中（尽管我们可以在函数体内做更多的归约）。

现在让我们考虑一个内置（原始）函数的应用：

(+) 1

因为这是一个内置函数，所以没有函数体可以替代1第一个参数。评估者“只知道”如何评估完全“饱和”的应用程序(+)，例如(+) 1 2. 但是使用部分应用的内置程序无法完成任何事情。我们所能做的就是生成一个数据结构，描述“将 (+) 应用于 1 并等待另一个参数”，但这正是我们试图减少的东西。所以我们什么也不做。

内置函数很特殊，因为它们不是由 lambda 演算表达式定义的，因此归约过程无法“看到内部”它们的定义。因此，与普通函数应用程序不同，内置函数应用程序必须通过累积参数来“减少”，直到它们完全“饱和”（在这种情况下，减少到 WHNF 是通过运行内置函数的任何神奇实现） . 无法进一步减少不饱和的内置应用程序，WHNF 中已经如此。

于 2014-06-27T09:02:21.193 回答
3

考虑

前奏> 让 fn = [(+x) | x <- [1..]] !! n
Prelude> let g = f 20000000 :: Int -> Int

g目前不在 WHNF 中！您可以通过评估来看到这一点，例如g 3，这需要一个明显的滞后，因为在应用参数之前您需要 WHNF。那是遍历列表以搜索正确的内置函数的时候。但之后，这个选择是固定的，g是 WHNF （实际上是 NF：这对于 lambdas 是一样的，也许你的问题是什么意思），因此任何后续调用都会立即给出结果。

于 2014-06-27T08:56:46.097 回答