在 Haskell 中扩展数据类型

Question

这里是一个Haskell新手。

我编写了一个针对最小汇编语言的求值器。

现在，我想扩展该语言以支持一些语法糖，然后将其编译回只使用原始运算符。我的想法是不想再次修改求值器模块。

按照面向对象的方式，我认为可以通过扩展原始模块来支持语法糖操作，并提供翻译规则。

除此之外，我只能想到重写两个模块中的数据类型构造函数，使它们不会命名冲突，并从那里继续，就好像它们是完全不同的东西，但这意味着有些冗余，因为我必须重复（只是用其他名称）共同的运算符。再次强调，我认为关键字在于扩展。

是否有一种函数式方法可以实现这一点？

感谢您抽出时间阅读这个问题。

- Seymour Kooze

Answer 1

这个问题被Phil Wadler称为“表达式问题”，他的话是：

目标是定义一个可以通过情况来确定数据类型，其中一个可以向数据类型添加新情况和新函数，而不需要重新编译现有代码，并保持静态类型安全性。

实现可扩展数据类型的一种解决方案是使用类型类。

例如，假设我们有一个简单的算术语言：

data Expr = Add Expr Expr | Mult Expr Expr | Const Int

run (Const x) = x
run (Add exp1 exp2)  = run exp1 + run exp2
run (Mult exp1 exp2) = run exp1 * run exp2

例如

ghci> run (Add (Mult (Const 1) (Const 3)) (Const 2))
5

如果我们想以可扩展的方式实现它，我们应该切换到类型类：

class Expr a where
    run :: a -> Int


data Const = Const Int

instance Expr Const where
    run (Const x) = x


data Add a b = Add a b

instance (Expr a,Expr b) => Expr (Add a b) where
    run (Add expr1 expr2) = run expr1 + run expr2


data Mult a b = Mult a b

instance (Expr a, Expr b) => Expr (Mult a b) where
    run (Mult expr1 expr2) = run expr1 * run expr2

现在让我们扩展这种语言，添加减法：

data Sub a b = Sub a b

instance (Expr a, Expr b) => Expr (Sub a b) where
    run (Sub expr1 expr2) = run expr1 - run expr2

例如

ghci> run (Add (Sub (Const 1) (Const 4)) (Const 2))
-1

想要了解更多关于这种方法以及表达式问题的内容，请查看 Ralf Laemmel 在 Channel 9 上的视频1和2。

但是需要注意的是，正如评论所指出的那样，这个解决方案改变了语义。例如，表达式列表不再合法:

[Add (Const 1) (Const 5), Const 6] -- does not typecheck

在函数式珠玑"Data types a la carte"中，提出了一种使用类型签名的余积更普遍的解决方案。请参阅Wadler对该论文的评论。

- Federico Squartini

---

哇，这是非常好的角度！谢谢！ - Seymour Kooze

这改变了程序的含义，即[Expr]不等同于Expr a => [a]。 - alternative

@monadic：太晚了。一开始我不明白你在说什么，所以继续摆弄它。当评估指令列表的时间到来时，它没有通过类型检查，你的评论立即让我明白了。我又回到原点了吗？我只记得使用过Either的列表，但那根本不实用！无论如何，感谢你预期的见解。我只是没能及时理解它。 - Seymour Kooze

@Seymour Kooze 使用存在类型。data ExprE = forall a. Expr a => a 然后 [ExprE] 展示了旧的行为。 - alternative

@monadic：我尝试了你的最后一个建议，但最终我需要为ExprE指定一个构造函数。特别地，除非我将其编写为data ExprE = forall a. Expr a => E a，否则我无法运行你的代码片段。能否像你的示例中那样避免这种情况？ - Seymour Kooze

@Seymour，那只是我的笔误...但是你可以以某种方式将其编码为二阶类型，我想。 - alternative

Answer 2

你可以使用存在类型做一些更类似于OOP的事情:

-- We need to enable the ExistentialQuantification extension.
{-# LANGUAGE ExistentialQuantification #-}

-- I want to use const as a term in the language, so let's hide Prelude.const.
import Prelude hiding (const)

-- First we need a type class to represent an expression we can evaluate
class Eval a where
  eval :: a -> Int

-- Then we create an existential type that represents every member of Eval
data Exp = forall t. Eval t => Exp t

-- We want to be able to evaluate all expressions, so make Exp a member of Eval.
-- Since the Exp type is just a wrapper around "any value that can be evaluated,"
-- we simply unwrap that value and call eval on it.
instance Eval Exp where
  eval (Exp e) = eval e

-- Then we define our base language; constants, addition and multiplication.
data BaseExp = Const Int | Add Exp Exp | Mul Exp Exp

-- We make sure we can evaluate the language by making it a member of Eval.
instance Eval BaseExp where
  eval (Const n) = n
  eval (Add a b) = eval a + eval b
  eval (Mul a b) = eval a * eval b

-- In order to avoid having to clutter our expressions with Exp everywhere,
-- let's define a few smart constructors.
add x y = Exp $ Add x y
mul x y = Exp $ Mul x y
const   = Exp . Const

-- However, now we want subtraction too, so we create another type for those
-- expressions.
data SubExp = Sub Exp Exp

-- Then we make sure that we know how to evaluate subtraction.
instance Eval SubExp where
  eval (Sub a b) = eval a - eval b

-- Finally, create a smart constructor for sub too.
sub x y = Exp $ Sub x y

通过这样做，实际上我们得到了一个可扩展的单一类型，这样您就可以在列表中混合扩展和基本值，例如：

> map eval [sub (const 10) (const 3), add (const 1) (const 1)]
[7, 2]

然而，由于我们现在能够了解到Exp值的唯一事情就是它们是Eval的成员，因此我们不能进行模式匹配或其他任何未在类型类中指定的操作。以OOP术语来说，将Exp视为实现Eval接口的对象。如果您有一个类型为ISomethingThatCanBeEvaluated的对象，显然您不能安全地将其强制转换为更具体的内容；Exp也是如此。

- valderman

---

这实际上解决了单子在使用Federico的策略时注意到的问题。谢谢！ - Seymour Kooze

需要注意的一点是，由于你能对 Exp 唯一能做的事情就是对其进行 eval，因此最好直接处理 Int。通常情况下，存在性可以被一个可用操作的记录（部分）应用于相关值来替换。 - hammar

@hammar，我不会说“一般来说”。例如，对于一个“Num”的存在性，你会怎么做？ - augustss

@augustss：啊，当然。如果类型类包含返回相同类型的函数，则它不起作用，因为您可以从类型类上执行任意组合的其他操作。只要所有类函数都采用一个存在类型的参数并返回某些非存在类型，它就可以正常工作。感谢更正。 - hammar

Answer 3

通常，语法糖由解析器处理；您需要扩展（不是指面向对象的继承）解析器来检测新构造并将其转换为评估器可以处理的结构。

- Fred Foo

---

我明白了。那么，我会硬着头皮重新调整我已经完成的部分。感谢您的见解。 - Seymour Kooze

通常情况下，语法是用抽象语法树表示的。可以很好地在“解糖”抽象语法树的基础上定义“糖衣”的抽象语法树（前者是后者的扩展）。如果我想要添加一种新的字符串文字，我应该能够在AST中保留一个_新的_字符串文字（而不是翻译版本！），而无需复制或改变我的数据结构太多。我希望它例如能够通过糖衣语法产生语义错误。 - n. m.

Answer 4

一个（更简单的）选项是给你的AST添加一个类型，以区分Core和Extended：

data Core = Core
data Extended = Extended

data Expr t 
  = Add (Expr t) (Expr t)
  | Mult (Expr t) (Expr t)
  | Const Int 
  | Sugar t (Expr t) (Expr t)

表达式可以是核心或扩展：编译器将确保它仅包含相同类型的子表达式。

您原始模块中的函数签名需要使用Expr Core（而不仅仅是Expr）

Desugar函数将具有以下类型签名：

Desugar :: Expr Extended -> Expr Core

你可能也会对论文“生长树”中描述的更复杂的方法感兴趣。

- Pierre Carbonnelle