Extensible OCaml Data Structures with Polymorphic Variants

The Problem with Closed Algebraic Data Types

In traditional OCaml, type shape = Circle of float | Rect of float * float defines a closed set of cases. Adding a new variant like Triangle requires editing the original definition and recompiling all dependent code. This creates a bottleneck for library authors and plugin systems where data structures must evolve without touching core source.

Polymorphic Variants to the Rescue

Polymorphic variants use backtick-prefixed constructors, such as `Circle. They are not tied to a single type declaration; instead, the compiler infers the set of possible variants from usage. This enables "open" types that can be merged across modules.

Worked Example: Extensible Expression Evaluator

Suppose we build a core evaluator for basic arithmetic, but want downstream code to add operations like square root without touching the core.

(* Core evaluator: handles Int, Add, Mul *)
let rec eval_core = function
  | `Int n -> n
  | `Add (a, b) -> eval_core a + eval_core b
  | `Mul (a, b) -> eval_core a * eval_core b
  | `Other e -> failwith "unsupported in core"

(* Extended evaluator adds Sqrt *)
let rec eval_extended = function
  | `Sqrt x -> sqrt (eval_core x)
  | e -> eval_core e

The core function accepts any variant set that includes `Int, `Add, `Mul. The extended version adds `Sqrt and delegates the rest to the core. Pattern matches are not required to be exhaustive over the whole variant universe, only over the cases handled.

Verifying Inferred Types

Because polymorphic variants rely on inference, it helps to inspect exactly what the compiler sees. Run the following command in your terminal, inside a directory containing eval.ml:

ocamlopt -i eval.ml

Look for output formatted like [>`Int of int | `Add of 'a * 'a | `Mul of 'a * 'a]. The [>` prefix indicates a lower bound: the function accepts at least these variants, possibly more. This check confirms that adding new variants to downstream code does not break the core, as long as the core's lower bound set remains compatible.

Trade-offs and Limitations

• Compilation overhead: In large modules with deeply nested polymorphic variants, the type engine must track many subtypes, which can increase build times.
• Error message complexity: Type mismatches produce verbose listings of all inferred variants, which can be hard to parse.

To keep code maintainable, define named type aliases for public APIs: type core_expr = [ `Int of int | `Add of core_expr * core_expr | `Mul of core_expr * core_expr ]. This gives users a clear boundary while retaining the flexibility of polymorphic variants under the hood.

When to Use Polymorphic Variants

Use this pattern for plugin systems, compiler passes where the AST evolves across stages, or any data structure that downstream consumers need to extend. For stable, internal data models, standard ADTs still offer better compilation speed and clearer exhaustiveness warnings.