4

现在，我有一个表达式的 AST，它在递归类型上是多态的：

data Expr a = Const Int
            | Add a a

这非常有用，因为它允许我使用一种类型进行普通递归 ( Fix Expr) 并在我需要附加额外信息时使用另一种类型 ( Cofree Expr ann)。

当我想在此递归方案中引入另一种类型时，会出现此问题：

data Stmt a = Compound [a]
            | Print (Expr ?)

Expr如果不引入额外的类型变量并破坏与我已经编写的所有通用函数的兼容性，我不确定该术语的含义。

可以做到这一点，如果可以，这是一个有用的模式吗？

4

1 回答 1

6

递归方案的观点是将递归类型视为函子的固定点。表达式的类型是以下函子的不动点：

data ExprF expr = Const Int
                | Add expr expr

更改变量名称的目的是明确表明它是实际表达式类型的占位符，否则将定义为：

data Expr = Const Int | Add Expr Expr

在Stmt中，有两种递归类型，Expr和Stmt它本身。所以我们放了两个洞/未知数。

data StmtF expr stmt = Compound [stmt]
                     | Print expr

Fix当我们用or取一个固定点时Cofree，我们现在正在求解一个由两个方程组成的系统（一个代表Expr，一个代表Stmt），并且带有一些样板。

我们没有直接应用Fixor Cofree，而是将这些固定点组合子 ( Fix, Cofree, Free) 作为构造表达式和语句的参数进行概括：

type Expr_ f = f ExprF
type Stmt_ f = f (StmtF (Expr_ f))

现在我们可以说Expr_ Fix或Stmt_ Fix对于未注释的树，and Expr_ (Flip Cofree ann)，Stmt_ (Flip Cofree ann)。不幸的是，我们必须支付另一笔 LOC 费用才能使类型匹配，并且类型变得更加复杂。

newtype Flip cofree a f b = Flip (cofree f a b)

（这也假设我们想在同一时间使用相同的Fix或Cofree无处不在的。）

要考虑的另一种表示是（现在称为 HKD）：

data Expr f = Const Int
            | Add (f Expr) (f Expr)

data Stmt f = Compount [f Stmt]
            | Print (f (Expr f))

您只能从注释/无注释（f = Identity或(,) ann）中抽象，而不是从递归中抽象。

于 2018-06-28T01:50:45.647 回答