GADTs and typed little languages¶
19 February 2026 ยท OCaml 5.3
In an ordinary variant, every constructor produces the same type 'a expr. A
generalized algebraic data type (GADT) lets each constructor refine that
type parameter, so Int builds an int expr, Eq builds a bool expr, and
ill-typed expressions like adding a boolean to an integer can't be represented
at all.
type _ expr =
| Int : int -> int expr
| Bool : bool -> bool expr
| Add : int expr * int expr -> int expr
| Eq : int expr * int expr -> bool expr
| If : bool expr * 'a expr * 'a expr -> 'a expr
let rec eval : type a. a expr -> a = function
| Int n -> n
| Bool b -> b
| Add (x, y) -> eval x + eval y
| Eq (x, y) -> eval x = eval y
| If (cond, yes, no) -> if eval cond then eval yes else eval no
let () =
let term = If (Eq (Add (Int 2, Int 2), Int 4), Int 42, Int 0) in
assert (eval term = 42)
Notice eval needs no runtime value tag (VInt of int | VBool of bool) and no
"impossible" error branch: in the Add arm, the compiler knows a is int, so
eval x + eval y has the right return type directly. The type a. annotation,
a locally abstract type, is what lets OCaml refine a differently inside each
branch of the match.