How should I represent an AST annotated with additional information?

Question

Let's say I have a simple data type representing an AST in some language:

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

(In reality it would obviously have more constructors than this.)

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

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

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

(If I didn't mind changing the patterns, I could use record syntax or view patterns, of course.)

Answer 1

Why not represent the AST polymorphically

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

then your orignal Term type is

newtype SimplTerm = SimplTerm (Term (SimplTerm))

and you can easily do what you want with view patterns

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 making view 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 wish there was a way to get view patterns to appear in a monad, but that is life (which you could do if the view function were done in cps and so took the continuation as an argument rather than returning a value).