haskell - 具有多种类型的递归方案

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本身。所以我们放了两个洞/未知数。

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))

您仅从注释/无注释( f = Identity 或 (,) ann )中抽象而不是从递归中抽象。