在Haskell中扩展数据类型

Question

Haskell新手在这里.

我为一个最小的类汇编语言写了一个评估器.

现在,我想扩展该语言以支持一些语法糖,然后我将编译回来仅使用原始运算符.意思是我不想再次触及评估模块.

我认为,在OO的做事方式中,可以扩展原始模块以支持语法糖操作符,在此提供翻译规则.

除此之外,我只能考虑重写两个模块中的数据类型构造函数,以便它们不会发生名称冲突,并从那里继续,好像它们是完全不同的东西,但这意味着一些冗余,因为我必须重复(仅与其他名称)共同的运营商.同样,我认为这里的关键字是extend.

有没有一种功能性的方法来实现这一目标？

感谢您抽出宝贵时间阅读此问题.

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

有关此方法的更多信息,以及关于表达式问题的更多信息,请查看第9频道上的Ralf Laemmel的视频1和2.

但是,正如评论中所注意到的,此解决方案会更改语义.例如,表达式列表不再合法:

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

使用类型签名的副产品的更一般的解决方案在功能珍珠"数据类型单点"中给出.另见Wadler 对论文的评论.

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 exp值视为实现Eval接口的对象.如果你有一个ISomethingThatCanBeEvaluated类型的对象,显然你不能安全地把它变成更具体的东西; 同样适用于Exp.