使用其他数据在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 | ... 

如果你这样做，typechecker再也不能阻止你在错误地使用Var'该计划的其他部分。 第三个选择是简单地保持周围所有的时间额外的信息，即使它没有相关的程序的其余部分：

data Exp = Var Identifier ExtraInfo | ... 

可行的，但它的丑陋，尤其是如果你只需要额外的信息简要。现在，我刚把Map Indentifier ExtraInfo中的额外信息加上AST，明确地或通过状态monad。例如，如果您需要使用不同的信息注释同一个Identifier的不同发生，这可能会变得很尴尬。

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

Answer 1

如果你把所有类型的多种多晶，像这样：

data AST a = AST a 
data GlobalDecl t i s = Func t i [s] | ... 
data Stmt i e = Assign i e | ... 
data Exp a = Var a | ... 

，那么你可以暂时用一个元组实例化它们 - 例如Exp (Int, Identifier) - 用于中间计算。如有必要，您可以为上述具体类型制作newtype，方便起见。

Answer 2

用额外数据标记结构的一种方法是使用较高的kinded类型参数。如果您只需要标记变量，则可以执行

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

这类似于彼得建议，但而不是使的类型完全通用的，只parametricizes你想改变的部分。

你会得到你原来，无标记与AST Identity结构或者你可以有一个像类型其中AST ((,) ExtraInfo)会变成Var (f Identifier)为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)将在每个分支点包含额外的信息语法树（授予，与上述结构一起工作会变得有点麻烦）。