Why OCaml GADTs Matter: A Practical Guide to Type‑Safe Pattern Matching

Concrete Problem: Untyped ASTs and Runtime Errors

When building a compiler or interpreter in OCaml, a common pattern is to represent expressions as an algebraic data type (ADT). A naïve ADT might look like this:

type expr = Int of int | Bool of bool | Add of expr * expr | And of expr * expr

Pattern matching on expr forces the programmer to manually cast values to the expected type inside each branch. If a mistake slips through, the program crashes at runtime with a Match_error or a type‑unsafe cast.

Thesis: GADTs Encode Invariants at the Type Level

Generalized Algebraic Data Types (GADTs) lift the power of ordinary ADTs by allowing each constructor to refine the type parameters. This refinement lets the compiler track the exact type of the expression tree, eliminating the need for unsafe casts and ensuring exhaustive pattern matching.

1. What Are GADTs?

A GADT is defined with an explicit type parameter and constructor signatures that can specify a more precise type. The syntax is similar to normal ADTs but includes the :` operator to refine the type. For example:

type _ expr =
  | Int : int -> int expr
  | Bool : bool -> bool expr
  | Add : int expr * int expr -> int expr
  | And : bool expr * bool expr -> bool expr

Here _ expr means the type carries an unknown type parameter that each constructor will instantiate. The Int constructor, for instance, produces an int expr, while Bool produces a bool expr. The compiler enforces that the arguments match these refined types.

2. GADTs in Action: A Typed Expression Tree

Let’s build a small evaluator that only accepts well‑typed expressions. The type system guarantees that we can’t add an int to a bool or evaluate a boolean expression as an integer.

type _ expr =
  | Int : int -> int expr
  | Bool : bool -> bool expr
  | Add : int expr * int expr -> int expr
  | And : bool expr * bool expr -> bool expr

let rec eval : type a. a expr -> a = function
  | Int n -> n
  | Bool b -> b
  | Add (e1, e2) -> eval e1 + eval e2
  | And (e1, e2) -> eval e1 && eval e2

Notice the type a. annotation on eval. It tells the compiler that eval works for any type parameter a. Inside the match, the compiler knows the exact type of the result, so eval e1 + eval e2 is type‑correct only if e1 and e2 are int expr.

Exhaustiveness Checking

If we omit the And branch, the compiler emits an error:

Error: This pattern match may not be exhaustive.
Missing patterns: And of bool expr * bool expr

Thus, GADTs turn runtime pattern‑matching bugs into compile‑time errors.

3. Trade‑offs & Limitations

• Verbosity: GADT definitions require explicit type annotations on constructors, which can be more verbose than plain ADTs.
• Compile Time: Complex GADT hierarchies can increase compilation times, especially in large codebases.
• Learning Curve: The refined type syntax and the need to understand the type a. polymorphic function syntax can be confusing for newcomers.
• Overuse: In scenarios where invariants are trivial, a plain ADT can be clearer and easier to maintain.

Despite these caveats, the safety benefits—no unsafe casts, guaranteed exhaustiveness, and clearer intent—often outweigh the costs for medium‑to‑large projects.

4. Practical Tips for Using GADTs

1. Start Small: Introduce GADTs for modules that truly need strong invariants (e.g., ASTs, heterogeneous collections).
2. Document Constructor Refinements: Add comments explaining the type refinement to aid readability.
3. Leverage Type Inference: In many cases, the compiler infers the GADT type, so you can omit explicit annotations in function arguments.
4. Use type a. Polymorphic Functions: This syntax lets you write functions that work for any GADT instance without exposing the type parameter externally.
5. Check Compile Errors Early: When adding new constructors, run ocamlc -c module.ml to catch missing pattern branches before runtime.

Actionable Closing

If you’re refactoring an existing codebase, start by identifying a module that currently relies on unsafe casts or has many pattern‑match warnings. Replace that module with a GADT, run the compiler, and verify that all pattern matches are exhaustive. Over time, you’ll see a measurable drop in runtime errors and a clearer contract between modules.

Remember: GADTs are a tool, not a silver bullet. Use them where the type system can enforce invariants that would otherwise require runtime checks.