AST.hs

-- Simple Lambda Calculus
data Body a = Var String | Lam String (Expr a) | Apply (Expr a) (Expr a)
  deriving (Functor, Foldable, Traversable)
data Expr a = Expr (Body a) a
  deriving (Functor, Foldable, Traversable)

Now each sub-expression in (Expr a) has associated data of type "a" which is really useful!


NEXT:

data Body expr = Var String | Lam String expr | Apply Expr expr
  deriving (Functor, Foldable, Traversable)
data Expr a = Expr (Body (Expr a)) a
  deriving (Functor, Foldable, Traversable)

This is also useful, because it lets you easily recurse to all subexpressions, if you use