How should I submit AST with additional information?

Question

Say I have a simple data type representing an AST in some language:

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

(In reality, he would obviously have more constructors than that.)

I can use this to write a simple evaluation function that matches the AST structure:

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

Can I annotate AST with information like line numbers without changing how template matching works?

(If I did not mind changing the templates, I could use the syntax of the entry or the presentation templates, of course.)

Answer 1

Why not imagine AST polymorphically

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

then your type is orignal Term

 newtype SimplTerm = SimplTerm (Term (SimplTerm)) 

and you can easily do what you want with viewing templates

 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) 

or make it look polymorphic

 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) 

for error handling. I would like for presentation templates to appear in the monad, but this is life (what could you do if the view function was executed in cps and therefore took continuation as an argument, rather than returning a value).