- Courses
- 💻Programming Languages
- 🐫OCaml (WIP)
- Advanced Type System
- GADTs
On this page
OCaml GADTs (Generalized Algebraic Data Types)
Published on August 20, 2026
By Enrico Hochkoeppler
Web Developer & TutoriaLibre Founder
An ordinary variant type forces every one of its constructors to build the exact same shape of type — a 'a option is always 'a option, regardless of whether it came from Some or None. A generalized algebraic data type relaxes this: each constructor can specify its own particular instantiation of the type's parameters, through an explicit return type, rather than every constructor sharing one uniform result. This single relaxation is what makes it possible to encode real, per-case invariants directly into a type, and have the compiler enforce them before a program ever runs.
The Problem GADTs Solve
Consider trying to represent a small typed expression language — integers, addition, a zero-check, and a conditional — using an ordinary variant. Every constructor of an ordinary variant type produces the exact same type, so there's nothing to stop a value like "add an integer to a boolean" from being constructed, even though it's nonsensical:
type expr =
| Lit of int
| Add of expr * expr
| Is_zero of expr
| If of expr * expr * expr
Add (Lit 1, Is_zero (Lit 0)) compiles perfectly well under this definition, even though Is_zero (Lit 0) conceptually represents a boolean, not something that should be addable to an integer. Catching this kind of mistake would require writing a runtime type checker over the expr tree, defeating a large part of the point of using a statically typed language to represent the expressions in the first place.
GADT Syntax: Constructors With Their Own Return Type
A GADT fixes this by letting each constructor specify exactly what the overall type looks like when that specific constructor is used, via an explicit return type after a colon:
type _ expr =
| Lit : int -> int expr
| Add : int expr * int expr -> int expr
| Is_zero : int expr -> bool expr
| If : bool expr * 'a expr * 'a expr -> 'a expr
The underscore in type _ expr stands in for the type parameter, left anonymous here since each constructor pins it down individually rather than sharing one name across the whole definition. Reading each constructor's return type is what carries the actual meaning: Lit produces an int expr; Add requires two int expr arguments and produces an int expr; Is_zero takes an int expr and produces a bool expr, reflecting that checking for zero is fundamentally a different kind of operation than the arithmetic it operates on; If is polymorphic in 'a, since a conditional can return any type, as long as its two branches agree.
With this definition, the earlier mistake is no longer expressible at all:
# Add (Lit 1, Is_zero (Lit 0));;
Error: This expression has type bool expr
but an expression was expected of type int expr
Is_zero (Lit 0) genuinely has type bool expr, and Add genuinely requires int expr arguments — the compiler rejects the mismatch directly, using exactly the same type-checking machinery used everywhere else, just applied per constructor instead of uniformly across an entire type.
Writing an Evaluator That Can't Go Wrong
The real payoff shows up when writing a function that consumes this type. An evaluator can return the specific, correct type for each case, rather than a single type shared awkwardly across every possible kind of expression:
let rec eval : type a. a expr -> a = function
| Lit n -> n
| Add (x, y) -> eval x + eval y
| Is_zero x -> eval x = 0
| If (cond, t, f) -> if eval cond then eval t else eval f
Matching on Lit n inside this function doesn't just extract n — it also tells the compiler, for that branch only, that a must be int, since Lit's return type fixes it that way. That's why eval x + eval y type-checks inside the Add branch (both sides are known to be int there) while eval cond inside If is known to be bool, and the whole function's return type, a, correctly comes out as int for eval (Lit 1) and bool for eval (Is_zero (Lit 0)) — a single function, returning a genuinely different, correctly-tracked type depending on which expression was actually passed in.
Why type a. Is Required
The type a. annotation appearing right after eval : is not optional decoration — it declares that eval is being defined with explicit polymorphic recursion, which GADT-consuming recursive functions generally need. Without it, let rec eval e = ... written the ordinary way would try to infer one single, fixed type for eval before type-checking its body, but the whole reason eval type-checks correctly is that its return type is refined differently in each branch, as different instantiations of a — a genuinely polymorphic relationship that OCaml's usual, simpler treatment of let rec isn't set up to discover on its own. Writing type a. explicitly tells the compiler this function needs to work generically across every possible instantiation of a, checked separately in each branch, rather than needing to guess one from the outside.
Existential Types: When a Constructor's Argument Isn't in Its Return Type
A GADT constructor can also mention a type variable in its argument that never appears in its return type at all — this is what makes that variable existentially quantified, meaning "some type exists here, but the function using this value doesn't get to know which one":
type any = Any : 'a -> any
Any can wrap a value of literally any type, and the resulting any value carries no information at all about what that original type was — from the outside, all that's known is "some type existed at the point this was wrapped." Trying to smuggle that hidden type back out is rejected directly by the compiler, since doing so would let a value's real type escape the narrow scope where it was still known:
let escape (Any x) = x
Error: This expression has type $Any_'a but an expression was expected of type 'a
The type constructor $Any_'a would escape its scope
This existential behavior is a natural consequence of the same mechanism that makes GADTs work for the expression-language example above — a type variable that only shows up in a constructor's argument, and not in its return type, simply isn't something the rest of the program can ever pin down concretely again once it's wrapped.
A Small But Genuinely Useful Bonus: Provable Exhaustiveness
Because GADT pattern matching refines what the compiler knows about a type in each branch, it can sometimes prove that a particular combination of patterns is outright impossible, rather than merely unlikely. In those situations, that branch can be written with a single dot, ., instead of a body, explicitly marking it as a case the compiler has already established can never actually occur — a small but genuine expressiveness gain over ordinary pattern matching, where every reachable-looking case still needs a real body even if it happens to never actually be hit in practice.
When to Reach for a GADT
GADTs earn their place specifically in situations where a type needs to carry different, provably-correct information depending on which constructor built it — small interpreters and typed abstract syntax trees, like the expr example here, are the textbook case, but the same technique extends to data structures whose internal invariants vary by shape, such as balancing information embedded directly in a tree's own type. For data that's genuinely uniform across every constructor — where an ordinary ADT like option or a plain list already fits without any constructor needing a specialized return type — a GADT adds complexity without buying back anything, and an ordinary variant remains the simpler, equally correct choice.
Key Takeaways
- A GADT lets each constructor specify its own return type, rather than forcing every constructor of a type to produce the exact same, uniform shape.
- This makes it possible to encode per-constructor invariants directly into a type — such as a typed expression language where mismatched operand types are rejected at construction, not caught later by a runtime check.
- Matching on a GADT constructor refines what the compiler knows about the type's parameter for that specific branch, which is what lets a single evaluator function return a genuinely different, correctly-typed result depending on which case matched.
- Writing a recursive function over a GADT generally requires the explicit
type a.polymorphic recursion annotation, since the function's return type is refined differently per branch rather than fixed once for the whole function. - A type variable appearing in a constructor's argument but not its return type becomes existentially quantified, and the compiler prevents that hidden type from escaping the scope where it's still known.
- GADTs are the right tool specifically when different constructors of a type need to carry provably different, refined information; for uniformly-shaped data, an ordinary variant remains the simpler choice.
Found this helpful? Share the knowledge...
... or support this project to keep it alive!
Previous
Phantom Types
Next
First-Class Modules
- The Problem GADTs Solve
- GADT Syntax: Constructors With Their Own Return Type
- Writing an Evaluator That Can't Go Wrong
- Why type a. Is Required
- Existential Types: When a Constructor's Argument Isn't in Its Return Type
- A Small But Genuinely Useful Bonus: Provable Exhaustiveness
- When to Reach for a GADT
- Key Takeaways
