haskell - Haskell 中表达式的 'outermost part' 是什么意思

Question

这里是真正的初学者，我正在阅读 NF 和 WHNF 之间的差异，以及我遇到的定义之一

To determine whether an expression is in weak head normal form, we only have to look at the outermost part of the expression.

我不确定应用什么标准来确定“最外面”的部分是什么。例如(来自@hammer 的堆栈溢出答案):

'h' : ("e" ++ "llo") -- the outermost part is the data constructor (:)
(1 + 1, 2 + 2)       -- the outermost part is the data constructor (,)
\x -> 2 + 2          -- the outermost part is a lambda abstraction

尤其是在第一个示例中，(:) 运算符位于 'h' 和另一个表达式的中间，那么它如何位于最外面的部分？

一般而言，在查看表达式时，如何确定最外层是什么？

Answer 1

好问题。此处，“最外层”(或“最顶层”)根据表达式的一种标准抽象 View 来描述位置，该 View 可能与其实际语法不同。例如，这两个表达式:

(1, 2)
(,) 1 2

在 Haskell 中具有相同的含义。事实证明，在这两种情况下，构造函数 (,) 是表达式的最外层部分，即使表达式具有不同的句法形式，逗号出现在句法中的不同物理位置。

一般来说，Haskell 的“标准语法”涉及以下形式的函数应用:

fexpr expr1 .. exprn

但是，该语言还允许其他类型的语法:

1 + 2                -- infix operators
(3, 4)               -- tuples
[5,6,7,8]            -- lists
"abc"                -- strings

这些替代语法可以转换为标准语法，如下所示:

1 + 2   ==>   (+) 1 2
(3, 4)  ==>   (,) 3 4
[5,6,7,8]   ==>  (:) 5 ((:) 6 ((:) 7 ((:) 8 [])))
"abc"   ==>   (:) 'a' ((:) 'b' ((:) 'c' []))

虽然远不明显，但 (+) 是一个变量，其值是一个函数(如 sqrt )；而 (,) 和 (:) 是构造函数(就像 True 或 Just )。更令人困惑和更明显的是，即使 [1,2,3] 是特殊语法，空列表 [] 也是一个(一元)构造函数!这就是为什么我仍然在我的标准语法版本的右侧使用空列表的原因。

无论如何，一旦转换为标准语法，表达式将成为构造函数应用程序，例如以下之一:

True               -- a nullary constructor
(,) (1+2) (2+3)    -- constructor expecting two args and fully applied
(:) 5              -- constructor partially applied and expecting one more arg

我们说表达式的“最外面的部分”是这个构造函数应用程序，或者它将是一个未应用的 lambda 抽象:

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

我们说表达式的“最外面的部分”是这个未应用的 lambda 抽象，或者它会是别的东西:

w                    -- a variable
(\x -> x) 10         -- an applied lambda abstraction
(f x) y ((*) 2 z)    -- some other function application
(+) 10 (length (1:[]))  -- another function application

我们说表达式的“最外层”是变量引用或函数应用程序或其他任何东西。

无论如何，如果最外面的部分是构造函数应用程序或未应用的 lambda 抽象，那么它被称为弱头范式。如果是别的东西，那就不是。

所以， Just (5+6) 在 WHNF 中，因为最外层是构造函数 Just 的应用。另一方面， sqrt (5+6) 在 WHNF 中是 而不是 因为最外层是变量 sqrt 的应用，而变量不是构造函数。

类似地， 5+6 本身不在 WHNF 中，因为最外层是变量 (+) 对 5 和 6 的应用，而 [5,6] 在 WHNF 中，因为最外层是(隐含的)构造函数 (:) 对 5 和 [6] 的应用。