haskell - 有没有更好的方法将属性字段添加到 Haskell 的 AST 中？

Question

起初，我有一个像这样的原始 AST 定义:

data Expr = LitI Int | LitB Bool | Add Expr Expr

我想概括它，以便每个 AST 节点都可以包含一些额外的属性:

data Expr a = LitI Int a | LitB Bool a | Add (Expr a) (Expr a) a

通过这种方式，我们可以轻松地将属性附加到 AST 的每个节点中:

type ExprWithType = Expr TypeRep
type ExprWithSize = Expr Int

但这种方案使得访问属性字段变得困难，我们必须使用模式匹配并逐个处理:

attribute :: Expr a -> a
attribute e = case e of
    LitI _ a -> a
    LitB _ a -> a
    Add _ _ a -> a

我们可以想象，如果我们可以通过原始 AST 的产品类型和指示属性的类型变量来定义我们的 AST:

type ExprWithType = (Expr, TypeRep)
type ExprWithSize = (Expr, Int)

那么我们可以像这样简化属性访问函数:

attribute = snd

但我们知道，来自最外层产品类型的属性不会递归出现在子树中。

那么，这个问题有没有更好的解决方案呢？

一般来说，当我们要提取递归和类型的不同情况的公共(public)字段时，我们会遇到这个问题。

Answer 1

您可以“提升”Expr 的类型，例如:

data Expr <b>e</b> = LitI Int | LitB Bool | Add <b>e</b> <b>e</b>

现在我们可以定义一个数据类型:

data ExprAttr a = ExprAttr {
    expression :: Expr <b>(ExprAttr a)</b>,
    attribute :: a
  }

所以这里的 ExprAttr 有两个参数，expression，因此它是一个 Expression 有 ExprAttr a在树中，属性是一个a。

因此，您可以处理 ExprAttr，它是 ExprAttr 的 AST。如果你想使用一个“简单的”AST，你可以定义一个类型:

newtype SimExpr = SimExpr (Expr SimExpr)