data Term t where
Num :: Integer -> Term Integer
Bool :: Integer -> Term Integer
Add :: Term Integer -> Term Integer -> Term Integer
IsZero :: Term Integer -> Term Bool
IfThenElse :: Term Bool -> Term a -> Term a -> Term a
With this AST, you can express well-typed programs like `Add (Num 2) (Num 3)`, but the Haskell type system will stop if you express an incorrectly-typed program like `Add (Num 2) (Bool False)`.The "Trees That Grow" paper, on the other hand, is about reusing the same AST but gradually adding more information to the nodes as you progress through the compiler. For example, you might want to start with variable names being raw strings (so that a term corresponding to `lambda x: lambda x: x` looks like `Lam "x" (Lam "x" (Var "x"))`) but eventually replace them with unique symbols so that shadowed names are non-identical (so that under the hood it looks more like `Lam 1 (Lam 2 (Var 2))`, although in practice you'd want to keep the old name around somewhere for debugging.)
One way to accomplish this is to introduce an explicit type-level notion of compiler phases, give your terms a type parameter which corresponds to the phase, and use the phase to choose different representations for the same nodes:
data CompilerPhase = Parsed | Resolved
data Expr (phase :: CompilerPhase)
= Lam (Name phase) (Expr phase)
| App (Expr phase) (Expr phase)
| Var (Name phase)
type family Name (t :: CompilerPhase) :: *
type instance Name Parsed = String
type instance Name Resolved = Int
Using this example, an `Expr Parsed` will contain variables that are just strings, while an `Expr Resolved` will contain variables that are integers, and you can write a pass `resolve :: Expr Parsed -> Expr Resolved` which just modifies the AST. (This is a toy example: in a real compiler, you'd probably want to create a new type for resolved variables that still keeps a copy of the name around and maybe some location information that points to the place the variable was introduced.)