haskell - 在 Haskell 中使用附加数据注释嵌套 ADT

Question

在用 Haskell 编写编译器时，我在处理嵌套数据类型时多次遇到一个特定问题。我将定义一个 ADT，例如

data AST = AST [GlobalDecl]

data GlobalDecl = Func Type Identifier [Stmt] | ...

data Stmt = Assign Identifier Exp | ...

data Exp = Var Identifier | ...

在对 AST 执行一些转换时，我可能想简单地携带一些额外的数据以及表达式中使用的变量。到目前为止，我考虑过的所有执行此操作的选项似乎都相当尴尬。我可以创建一个新的数据类型:

data Exp' = Var' Identifier ExtraInfo | ...

但这意味着我需要一个新的定义Stmt'、GDecl'，以便形成稍微改变的AST'。另一种选择是向原始 Exp 添加另一个数据构造函数，但仅在程序的某个特定部分中使用它:

data Exp = Var Identifier | Var' Identifier ExtraInfo | ...

如果您这样做，类型检查器将无法再防止您在程序的其他部分错误地使用 Var'。第三种选择是始终保留额外信息，即使它与程序的其余部分无关:

data Exp = Var Identifier ExtraInfo | ...

可行，但它很难看，特别是当您只需要短暂的额外信息时。现在，我只是将额外信息放入 Map Indentifier ExtraInfo 中，并通过 AST 显式或通过状态 monad 携带它。例如，如果您需要使用不同的信息来注释同一 Identifier 的不同出现，这可能会很快变得尴尬。

有人有任何优雅的技术来注释嵌套数据类型吗？

Answer 1

用额外数据标记结构的一种选择是使用更高种类的类型参数。如果您只需要标记变量，您可以这样做:

data AST f = AST [GlobalDecl f]
data GlobalDecl f = Func Type Identifier [Stmt f] | ...
data Stmt = Assign Identifier (Exp f) | ...
data Exp f = Var (f Identifier) | ...

这与 Peter 的建议类似，但它并没有使类型完全通用，而是仅参数化您想要更改的部分。

您将使用 AST Identity 获得原始的、未标记的结构，或者您可以拥有类似 AST ((,) ExtraInfo) 的类型，该类型将变成 Var (f 标识符) 转换为 Var (ExtraInfo, Identifier)。

如果您需要使用一些额外信息(例如标记位置)来标记 AST 的每个级别，您甚至可以将数据类型定义为

data AST f = AST [f (GlobalDecl f)]
data GlobalDecl f = Func (f (Type f)) (f (Identifier f)) [f (Stmt f)] | ...
data Stmt f = Assign (f (Identifier f)) (f (Exp f)) | ...
data Exp f = Var (f (Identifier f)) | ...

现在 AST ((,) ExtraInfo) 将在语法树中的每个分支点包含额外信息(当然，使用上述结构会有点麻烦)。