Haskell 中的 beta 减少策略

Question

这是我第一次学习函数式编程。我确实了解减少 beta 的工作原理。

例如：

(\x->2*x)5

表示您将 xs 替换为 5。

2*5=10

然而，其他例子让我感到困惑

(\f->f(f 0))(\x->x+1)

我们已经了解了一些评估策略，头范式和弱头范式。

根据我的笔记，我了解到 head 范式意味着没有 redex 表达式，而弱 head 范式意味着有 lambda 抽象。

这对我来说没有任何意义。两者之一是否适用于最后一个示例？如果是这样，其他策略的例子是什么？

Answer 1

术语

(\f -> f (f 0)) (\x -> x+1)

既不是头部正常形态也不是弱头部正常形态。该术语是将 lambda（具体为 \f -> f (f 0)）应用于术语（具体为 \x -> x+1），因此：

有一个 redex。回想一下，redex 被定义为将 lambda 应用于术语。由于表达式中某处有一个 redex ——特别是在最顶层，在这种情况下——这不是头部范式。
术语的顶层是一个应用程序，而不是 lambda，因此这不是弱头范式。

"head normal form"和"weak head normal form"都不是评估策略。形式是描述术语的形容词；评估策略，一般来说，是描述如何将一个词变成另一个词的动词。

beta reduction strategies in Haskell