具有多种类型的递归方案

Question

现在，我有一个针对递归类型的多态表达式的 AST：

data Expr a = Const Int
            | Add a a

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

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

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

我不确定在不引入额外的类型变量和破坏与我已经编写的所有通用函数的兼容性的情况下为 Expr 术语添加什么。

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

Answer 1

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

data ExprF expr = Const Int
                | Add expr expr

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

data Expr = Const Int | Add Expr Expr

在Stmt中有两种递归类型，Expr和Stmt本身。所以我们放两个 holes/unknowns.

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

当我们用 Fix 或 Cofree 取不动点时，我们现在正在求解一个由两个方程组成的系统（一个用于 Expr，一个用于 Stmt），并且附带了一些样板文件。

我们不是直接应用Fix或Cofree，而是将那些定点组合器（Fix、Cofree、Free）作为参数进行概括表达式和语句的构造：

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

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

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

（这还假设我们希望同时在所有地方使用相同的 Fix 或 Cofree。）

要考虑的另一种表示是 (called HKD nowadays):

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

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

你只从 annotation/no-annotation（f = Identity 或 (,) ann）而不是从递归中抽象。

Recursion schemes with several types