GADTs through a small typed expression evaluator
// status: seedling
The most useful way I have found to understand a Generalized Algebraic Data Type (GADT) is to stop starting with the acronym. Start with a tiny expression language and ask a plain question: can the evaluator accept an expression whose branches do not agree on their type?
An ordinary algebraic data type can describe the shape of an expression tree. A GADT adds a relationship between that shape and a type index. Each constructor is allowed to choose the result type of the indexed value. Pattern matching then recovers that relationship in the corresponding branch.
That sounds abstract until the evaluator becomes almost boring:
The function is total over the constructors we permit, and its result type follows the expression. A Expr Int evaluates to Int; a Expr Bool evaluates to Bool. The evaluator does not return a dynamically typed Value and then hope a later cast succeeds.
The ordinary AST first
An untyped expression tree is familiar:
data UntypedExpr
= IntLiteral Int
| BoolLiteral Bool
| Add UntypedExpr UntypedExpr
| Equal UntypedExpr UntypedExpr
| If UntypedExpr UntypedExpr UntypedExprThis shape is useful for parsing source text. It also admits nonsense: Add (BoolLiteral True) (IntLiteral 2) and If (IntLiteral 1) ... ... are representable. A dynamic interpreter can reject those cases at runtime; a typed language implementation needs a type-checking phase before evaluation.
The type of the tree does not yet say what any node returns. UntypedExpr is one set containing all expressions.
Index the result with a GADT
With GADT syntax enabled, the result type becomes part of each constructor's contract:
data Expr a where
LitInt :: Int -> Expr Int
LitBool :: Bool -> Expr Bool
Add :: Expr Int -> Expr Int -> Expr Int
Equal :: Expr Int -> Expr Int -> Expr Bool
If :: Expr Bool -> Expr a -> Expr a -> Expr aThe constructors do not all return the generic Expr a with an unconstrained a:
LitIntconstructs anExpr Int.LitBoolconstructs anExpr Bool.Addaccepts only integer expressions and returns an integer expression.Equalaccepts integer expressions and returns a boolean expression.Ifaccepts a boolean condition and two branches with the same result typea.
The type checker now rejects the bad shapes at construction time:
goodNumber = Add (LitInt 20) (LitInt 22)
goodCondition = Equal (LitInt 20) (LitInt 22)
goodBranch = If goodCondition (LitInt 1) (LitInt 0)
-- Does not type-check:
-- badCondition = If (LitInt 1) (LitInt 2) (LitInt 3)
-- badAdd = Add (LitBool True) (LitInt 2)The benefit is not that the compiler knows arithmetic. It is that the constructors make the shape of legal arithmetic and branching explicit, so the evaluator never needs a case for an integer used as a condition.
Evaluation is type refinement
eval (LitInt n) = n
eval (LitBool b) = b
eval (Add x y) = eval x + eval y
eval (Equal x y) = eval x == eval y
eval (If c t f) = if eval c then eval t else eval fThe important line is not eval (Add x y). It is the type signature plus pattern matching. In the LitInt branch, the constructor's result type tells GHC that the index a is Int; returning n is therefore valid. In the LitBool branch, a is Bool. In the If branch, the condition is known to be Expr Bool, and both branches are known to be Expr a for the same a.
This is what “type refinement” means here: pattern matching adds a local equation about the index. The equation is valid inside the branch; it does not turn every Expr a into an integer expression globally.
An annotation on eval is important. GHC's GADT documentation points out that refinement depends on a user-supplied type signature; without one, inference can lose the information needed to type a branch and produce confusing errors.
The same evaluator in OCaml
OCaml's GADT syntax expresses the same indexed relationship with an underscore parameter and explicit constructor result types:
n
b
eval x + eval y
eval x = eval y
if eval c then eval yes_branch else eval no_branchThe type a. annotation introduces a locally abstract type. Without it, the type checker cannot generally express that eval is polymorphic in the index while each pattern refines that index. This is one of the cases behind the “GADTs in anger” item in OCaml - learning log.
OCaml and Haskell are close in this example, but not identical. They differ in syntax, inference details, warning behaviour, and how existential variables are named. The shared idea is the indexed constructor result and branch-local refinement, not a promise that every GADT program ports line for line.
What did we gain over a dynamic Value?
The dynamic evaluator would usually look like:
and then return Result<Value, EvalError>. That is a sound and useful design for an untyped interpreter such as Monkey language interpreter made in Rust. The evaluator can report TypeMismatch when an addition receives a boolean or a condition receives an integer.
The GADT evaluator moves those particular checks earlier. There is no Add constructor that can contain a boolean expression, so there is no TypeMismatch branch for integer addition in eval. The remaining failures are different kinds of failures: division by zero, an unbound variable, a missing file, or a malformed external input still need a result type or an effectful boundary.
This is a key distinction: a GADT can make a family of values well-typed, but it does not make a whole program total. It encodes selected invariants; it does not replace error handling.
A typed evaluator is not a parser
The GADT above is excellent once we already know the type of each expression. A parser reading source text does not know that from the spelling alone. There are two common pipelines:
source → untyped AST → type checker/elaborator → indexed Expr → evaluatoror, for a language whose syntax carries enough annotations:
source → parser that constructs indexed Expr directly → evaluatorThe first pipeline is usually easier for a language with variables, overloaded operators, and useful error recovery. The second can work for a small language or a typed DSL. Trying to make an arbitrary parser return Expr a without deciding what a is leads directly to existential types.
Existentials: storing expressions of unknown result type
If a list should contain both integer and boolean expressions, the element type cannot be Expr a for one fixed a. Wrap each expression in an existential constructor:
data SomeExpr where
SomeExpr :: Expr a -> SomeExpr
program =
[ SomeExpr (Add (LitInt 20) (LitInt 22))
, SomeExpr (Equal (LitInt 1) (LitInt 2))
]The wrapper says “there exists some a, but the caller does not know which one.” We may inspect or pretty-print such a value if we carry a type witness or constrain the existential with a class, but we cannot write a general function that turns every SomeExpr into one String-free a. The hidden type must not escape its scope.
A type witness makes the runtime representation explicit:
data Type a where
TInt :: Type Int
TBool :: Type Bool
data TypedExpr where
TypedExpr :: Type a -> Expr a -> TypedExpr
showTyped (TypedExpr TInt e) = "Int expression: " ++ show (eval e)
showTyped (TypedExpr TBool e) = "Bool expression: " ++ show (eval e)This is a small example of a broader pattern: the type index is erased from the runtime unless the program stores a witness such as TInt or TBool. If a debugger, serializer, or FFI boundary needs to recover the type at runtime, design that representation deliberately.
What Rust can encode instead
Rust's ordinary enums are excellent for the untyped AST/value split in What Building an Interpreter Teaches About Type Design. They do not let each enum constructor declare a different instantiation of the same generic enum in the way LitInt :: Expr Int and LitBool :: Expr Bool do. A generic Rust enum has one type parameter chosen for the whole value, and its variants do not refine that parameter through pattern matching.
For a tiny language, Rust can encode selected invariants by splitting the syntax into indexed-looking families:
This is clear, but adding a polymorphic If means deciding how to represent a family of result types: duplicate constructors, introduce a trait/type-level encoding, or use a dynamic Value. Rust's ownership and trait systems provide useful building blocks, but this particular constructor-result refinement is not the same feature as a GADT.
That is not a weakness in the language; it is a design choice. The split-enum encoding can be easier to read, and a dynamic AST is often the right boundary for a parser. Use a GADT when the indexed invariant buys enough downstream simplicity to justify its more demanding inference and representation story.
GADTs and type design
The evaluator suggests a practical checklist:
- What property varies with the value? Here it is the result type of an expression.
- Can constructors enforce the property locally?
AddandIfcan constrain their inputs. - Will consumers benefit from the invariant?
evalbecomes simpler and cannot see malformed combinations. - Where does unknown type information live? Existential wrappers or type witnesses are needed at heterogeneous boundaries.
- What remains dynamic? External input, names, runtime resources, and partial operations still need error handling.
GADTs are especially good for typed interpreters, instruction sets, protocol states, heterogeneous syntax trees, and witnesses for type equality. They are not automatically a better representation for every AST. If the source is untyped and the program needs friendly diagnostics, an ordinary AST plus a separate type checker may be the more maintainable architecture.
Things that tripped me up
- GADT syntax is not enough. The return type of a constructor must actually constrain an index. An ordinary ADT written with explicit constructor signatures is not necessarily a GADT.
- The evaluator needs a signature. In both GHC and OCaml, annotations give the checker the locally abstract index it must refine.
- Refinement is branch-local. Matching
LitInttells mea ~ Intin that branch; it does not make an arbitraryExpr aan integer everywhere else. - Existentials cannot escape. A heterogeneous
SomeExprpackage hides its result type on purpose. To print or compare it, carry a witness or a suitable constraint. - A GADT is not a type checker. It describes already-typed terms. Parsing and elaborating untyped source is a separate phase.
- Runtime values may still be needed. Debuggers, serializers, plugin boundaries, and FFI code often need explicit type witnesses after static indices are erased.
- OCaml's
type a.is not decorative syntax. It introduces the local abstract type required for a polymorphic GADT evaluator. - Rust's split-enum encoding is not a GADT. It can enforce the same small example, but a generic indexed family and constructor-level result refinement are different tools.
- Total evaluation has limits. A well-typed
Divexpression can still divide by zero; static shape guarantees do not remove domain errors.
References
- GHC User's Guide — Generalised Algebraic Data Types
- GHC User's Guide — GADT-style constructor signatures
- OCaml manual — Generalized algebraic datatypes tutorial
- OCaml manual — GADT language extension
- The Rust Programming Language — Enums and pattern matching
- Rust Reference — Enumerations
- Xi, Chen, and Chen — Simple unification-based type inference for GADTs (primary paper)
- Monkey language interpreter made in Rust
- OCaml - learning log
Back to Notes · see also What Building an Interpreter Teaches About Type Design · Algebraic Effects in OCaml 5, From a Haskell and Rust Perspective · Home.