Skip to content
Tutorials Center
My learning

Topics

Lesson 26 of 40 ยท Variants and Pattern Matching

Polymorphic Variants and GADTs: Advanced Variant Types

Go beyond ordinary variants. Learn OCaml polymorphic variants with backtick tags, open and closed types, and GADTs that let the type checker track what each expression returns.

Ordinary variants are nominal: a constructor belongs to exactly one declared type. OCaml offers two more variant features for situations where that is too rigid or too weak. Polymorphic variants are structural: tags that can be used without any declaration and shared between types. GADTs (generalized algebraic data types) let each constructor refine the type of the whole value, so the type checker can follow facts such as "this expression evaluates to a bool".

You can write plenty of OCaml without either. Know what they are, and reach for them when plain variants start to fight you.

OCaml is not available in the site's code runners, so the ocaml blocks are read-only. The Python stand-ins show the ideas with dynamic checks instead of types.

Polymorphic variants

A polymorphic variant tag starts with a backtick. You do not need a type declaration:

OCAML
let c = `Red
(* val c : [> `Red ] *)

let describe = function
  | `Red -> "stop"
  | `Green -> "go"
(* val describe : [< `Green | `Red ] -> string *)

The inferred types use two kinds of bounds:

  • [> Red ]means "at leastRed`": an open type, which can be extended with more tags.
  • [< Green | Red ] means "at most these tags": a closed upper bound; the function accepts only these.

You can also name a type:

OCAML
type color = [ `Red | `Green | `Blue ]
type signal = [ color | `Flash of int ]

signal includes all the color tags plus a new one that carries data. That kind of reuse is hard with ordinary variants, where two types must repeat their constructors.

Sharing handlers

OCAML
let name_of_color : color -> string = function
  | `Red -> "red"
  | `Green -> "green"
  | `Blue -> "blue"

let name_of_signal : signal -> string = function
  | #color as c -> name_of_color c
  | `Flash n -> Printf.sprintf "flash x%d" n

The #color pattern matches any tag of color and lets you pass the value on to a function that only knows about color.

Trade-offs

Ordinary variant Polymorphic variant
Declaration required optional
Constructor names belong to one type can be shared across types
Error messages clear can be long and hard to read
Typos caught immediately a wrong tag may just create a new open type
Speed fast slightly slower (hash tags)

Because a typo like `Gren is still a valid tag, errors can show up far from the mistake. Prefer ordinary variants by default. Polymorphic variants shine for options in flags, for sharing a subset of cases between types, and in libraries that must stay extensible.

Stand-in: tags without a declaration

Dynamic languages have this freedom for free. The part OCaml adds is the check:

Python Stand-in: structural tags with a runtime handler

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The typo fails only when the line runs. OCaml reports the mismatch when you compile.

GADTs: types that follow the data

Imagine a tiny expression language with integers, booleans, addition and if. With an ordinary variant, an evaluator must return a value that could be an int or a bool, and an expression such as Add (Bool true, Int 1) is representable and fails only at run time:

OCAML
type expr =
  | Int of int
  | Bool of bool
  | Add of expr * expr
  | If of expr * expr * expr

A GADT adds a type parameter that records what the expression evaluates to, and each constructor states it:

OCAML
type _ expr =
  | Int : int -> int expr
  | Bool : bool -> bool expr
  | Add : int expr * int expr -> int expr
  | If : bool expr * 'a expr * 'a expr -> 'a expr
  | Eq : int expr * int expr -> bool expr

let rec eval : type a. a expr -> a = function
  | Int n -> n
  | Bool b -> b
  | Add (x, y) -> eval x + eval y
  | If (c, t, e) -> if eval c then eval t else eval e
  | Eq (x, y) -> eval x = eval y

Look at the pieces:

  • Each constructor is written Name : arguments -> result_type. Add only accepts int expr arguments, so Add (Bool true, Int 1) is a compile error.
  • eval : type a. a expr -> a is a locally abstract type annotation. GADT matching needs it so the type checker may learn a = int inside the Int n arm and a = bool inside Bool b.
  • The return type depends on the argument: eval (Eq (Int 1, Int 1)) has type bool and eval (Add (Int 1, Int 2)) has type int, with no casts and no run-time tag checks.
flowchart TD
    I["If (c, t, e) : 'a expr"] --> C["c : bool expr"]
    I --> T["t : 'a expr"]
    I --> E["e : 'a expr"]
    C --> Q["Eq (x, y) : bool expr"]
    Q --> X["x : int expr"]
    Q --> Y["y : int expr"]

Figure: the types of an If expression are tied together by the constructors.

Where GADTs are used

Well-typed interpreters, type-safe printf-like formatting, length-indexed vectors, typed protocol states and encoding witnesses. They are an advanced tool: error messages are harder, and many programs never need them. Use them when "the compiler should reject this nonsense program" is worth the added complexity.

Stand-in: the checks a GADT removes

Python Stand-in: dynamic type checks in an evaluator

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every isinstance check here is something the GADT version proves at compile time. This is also the starting point of the expression evaluator project, which uses a simpler ordinary variant.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the type [> Red ]` mean?

    ` marks a lower bound: the type contains Red and can be extended with more tags.

  2. 2. Why can a typo in a polymorphic variant tag be harder to spot?

    Since no declaration is required, an unexpected tag can be inferred into the type rather than rejected immediately.
  3. 3. In Add : int expr * int expr -> int expr, what does the GADT form give you?

    Each constructor states its argument and result types, so ill-typed trees cannot be built.
  4. 4. Why does the GADT eval need the annotation type a. a expr -> a?

    A locally abstract, explicitly polymorphic type lets each arm learn a different equation for a.

Summary

  • Polymorphic variants use backtick tags, need no declaration and can be shared and extended, at the price of weaker error messages.
  • Prefer ordinary variants unless you need open or shared tags.
  • GADTs let each constructor refine the type of the whole value, which allows evaluators that cannot mix up ints and bools.
  • GADT functions need locally abstract type annotations.

Next: Modules and Signatures