How should I represent an AST annotated with additional information?

haskell

Solution

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

Problem

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

Original source