On this page

OCaml GADTs (Generalized Algebraic Data Types)

Published on August 20, 2026

Enrico Hochkoeppler Profile

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​

Found this helpful? Share the knowledge...

... or support this project to keep it alive!

Buy Me a Coffee

Previous

Phantom Types

Next

First-Class Modules