使用其他數據在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)將在每個分支點包含額外的信息語法樹（授予，與上述結構一起工作會變得有點麻煩）。