haskell - 我应该如何表示带有附加信息注释的 AST？

Question

假设我有一个用某种语言表示 AST 的简单数据类型：

data Term = Var String
          | Num Integer
          | Expr [Term]

（实际上它显然会有比这更多的构造函数。）

我可以使用它来编写一个与 AST 结构匹配的简单评估函数：

eval :: Term -> Result
eval (Var name)   = lookup name
eval (Num n)      = return n
eval (Expr exprs) = ...

我可以在不改变模式匹配工作方式的情况下使用行号等信息来注释 AST 吗？

（如果我不介意改变模式，我当然可以使用记录语法或视图模式。）

Answer 1

为什么不以多态方式表示 AST

data Term term = Var String
      | Num Integer
      | Expr [term]

那么你的原始Term类型是

newtype SimplTerm = SimplTerm (Term (SimplTerm))

你可以很容易地用视图模式做你想做的事

data AtLine = AtLine (Term AtLine) Integer

view :: AtLine -> Term AtLine
view (AtLine x _) = x

eval (view -> Var name) = lookup name
eval (view -> Num n) = numResult n
eval (view -> Expr expr) = listResult (map eval expr)

或使视图多态

class AST t where
   term :: t -> Term t
instance AST SimplTemr where
   term (SimplTemr x) = x
instance AST AtLine where
   term (AtLine x _) = x

eval :: AST t => t -> Result
eval (view -> Var name) = lookup name
eval (view -> Num n) = numResult n
eval (view -> Expr expr) = listResult (map eval expr)

对于错误处理，我希望有一种方法可以让视图模式出现在 monad 中，但这就是生命（如果view函数在 cps 中完成，你可以这样做，因此将延续作为参数而不是返回值）。