Skip to content

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.