有没有更好的方法可以将属性字段添加到哈斯克尔的 AST 中?

起初，我有一个像这样的原始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

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

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

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

您可以"提升"Expr的类型，例如：

data Expre= LitI Int | LitB Bool | Addee

现在我们可以定义一个数据类型，如下所示：

data ExprAttr a = ExprAttr {
expression :: Expr(ExprAttr a),
attribute :: a
}

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

因此，您可以处理ExprAttrs，即ExprAttrs 的 AST。如果要使用"简单"AST，可以定义如下类型：

newtype SimExpr = SimExpr (Expr SimExpr)

在将递归的概念抽象为 f 代数之后，您可能想看看fCofree的递归数据类型，a将是您的注释类型。

内特·福比恩(Nate Faubion)就这种方法和类似的方法进行了非常容易理解的演讲，您可以在此处观看： https://www.youtube.com/watch?v=eKkxmVFcd74

相关内容