haskell - 如何在 Haskell 中计算表达式

Question

我了解如何创建和评估简单的数据类型 Expr。例如像这样:

data Expr = Lit Int | Add Expr Expr | Sub Expr Expr | [...]

eval :: Expr -> Int
eval (Lit x) = x
eval (Add x y) = eval x + eval y
eval (Sub x y) = eval x - eval y

所以这是我的问题:如何将变量添加到这个 Expr 类型，应该对其赋值进行评估？它应该如下所示:

data Expr = Var Char | Lit Int | Add Expr Expr [...]
type Assignment = Char -> Int

eval :: Expr -> Assignment -> Int

我现在如何为 (Var Char) 和 (Add Expr Expr) 执行我的 eval 函数？我想我已经想出了最简单的方法，如何为 Lit 做到这一点。

eval (Lit x) _ = x

对于 (Var Char) 我尝试了很多，但我无法从作业中得到一个 Int .. 认为它会像这样工作:

eval (Var x) (varname number) = number

Answer 1

好吧，如果您将环境建模为

type Env = Char -> Int

那么你所拥有的只有

eval (Var c) env = env c

但这并不是真正的“正确”。一方面，未绑定(bind)的变量会发生什么？所以也许更准确的类型是

type Env = Char -> Maybe Int
emptyEnv = const Nothing

现在我们可以看到一个变量是否未绑定(bind)

eval (Var c) env = maybe handleUnboundCase id (env c)

现在我们可以使用 handleUnboundCase做一些事情，比如分配一个默认值，炸毁程序，或者让猴子从你的耳朵里爬出来。

最后要问的问题是“变量是如何绑定(bind)的？”。如果你在寻找我们在 Haskell 中的“let”语句，那么我们可以使用一种称为 HOAS(高阶抽象语法)的技巧。

data Exp = ... | Let Exp (Exp -> Exp)

HOAS 位是 (Exp -> Exp)。本质上，我们使用 Haskell 的名称绑定(bind)来实现我们的语言。现在评估 let我们做的表达

eval (Let val body) = body val

这让我们躲开 Var和 Assignment通过依赖 Haskell 来解析变量名。

这种风格的示例 let 语句可能是

 Let 1 $ \x -> x + x
 -- let x = 1 in x + x

这里最大的缺点是建模可变性是一件非常痛苦的事情，但是在依赖 Assignment 时已经是这种情况了。类型与具体 map 。