Lambda 表达式的替换函数

Question

我目前正在编写函数，但无法解决第 4 种情况，即：

(E1 E2)[v->E] = E1[v->E] E2[v -> E]

我已经定义了前 3 个（常量和变量），但这对我来说有点棘手。

然而，函数签名是：

sub :: LExpr -> String -> LExpr -> LExpr

我首先对如何表示参数 (E1 E2) 感到困惑，后来又对如何表示 E1[v->E] E2[v -> E] 部分感到困惑。我认为 ++ 在这里不起作用，因为结果必须是 lambda 表达式而不是字符串。

data LExpr 的定义是 "common" Haskell 的定义，并使用 Eq 和 Show。如果需要，我可以提供它，但它非常基础，您必须非常熟悉它。

Answer 1

嗯，定义只是重写了

(E1 E2)[v->E] = E1[v->E] E2[v -> E]

变成 Haskell 语法。首先我们使用 sub 而不是 [v -> E] 符号。

sub (E1 E2) v E = (sub E1 v E) (sub E2 v E)

然后我们在 LExpr 之间显式地应用句法。

sub (App E1 E2) v E = App (sub E1 v E) (sub E2 v E)

最后，我们对变量使用小写名称，因为 Haskell 为构造函数保留大写名称。

sub (App e1 e2) v e = App (sub e1 v e) (sub e2 v e)

Substitution function for Lambda expression