Using OCaml Polymorphic Variants for Extensible Data Structures

Problem: Adding constructors without breaking existing code

When you design a library or a domain‑specific language, you often start with a fixed set of tags (e.g., `String, `Int, `List) and later realize you need a new one such as `Bool. With regular variants every new constructor forces you to edit the type definition and all match statements that handle it, risking missed cases and breaking backward compatibility.

Thesis: Polymorphic variants give you structural, open types that let you add tags freely

OCaml’s polymorphic variants are inferred from the constructors you actually use. A value of type [> `A | `B] means “at least the tags `A and `B”. The type checker treats each variant as a set of possible tags, allowing subtyping: [> `A | `B] is a supertype of [`A] and of [`A | `B]. Because the type is open, you can introduce new tags without touching existing definitions, and functions that only inspect a subset of tags continue to work unchanged.

How the type checker works

• Each occurrence of a constructor contributes its tag to the inferred set.
• Functions that pattern‑match on a variant receive the minimal open type that covers the tags they actually match.
• When you later use a new tag in a value, the inferred type of that value simply grows; existing functions keep their original inferred type because they never mentioned the new tag.

Worked example: a JSON‑like parser that stays unchanged when you add a Boolean tag

First, define a simple parser that handles strings, integers, lists and objects. The parser works with an open polymorphic variant type for the JSON values.

type json = [> `String of string
          | `Int of int
          | `List of json list
          | `Obj of (string * json) list]

let rec parse_lexer lexbuf =
  (* a very small hand‑written lexer for illustration *)
  let token = Lexer.token lexbuf in
  match token with
  | Lexer.STRING s -> `String s
  | Lexer.INT i    -> `Int i
  | Lexer.LBRACKET ->
      let rec lst acc =
        match Lexer.token lexbuf with
        | Lexer.RBRACKET -> `List (List.rev acc)
        | Lexer.COMMA    -> lst (parse_lexer lexbuf :: acc)
        | t              -> lst (parse_lexer lexbuf :: acc)  (* simplified *)
      in lst []
  | Lexer.LBRACE ->
      let rec obj acc =
        match Lexer.token lexbuf with
        | Lexer.RBRACE -> `Obj (List.rev acc)
        | Lexer.COMMA  -> obj (parse_lexer lexbuf :: acc)
        | t            -> obj (parse_lexer lexbuf :: acc)
      in obj []
  | _ -> failwith "unexpected token"

let parse_from_string s =
  let lexbuf = Lexing.from_string s in
  parse_lexer lexbuf

The type of parse_from_string is inferred as string -> json, where json is the open variant shown above. Notice that the type uses [> ...] because the function only constructs values; it does not pattern‑match on all possible tags.

Now extend the data model with a Boolean tag without touching the parser:

type json = [> `String of string
          | `Int of int
          | `List of json list
          | `Obj of (string * json) list
          | `Bool of bool]   (* new tag added *)

(* The same parse_from_string function works unchanged *)
let test () =
  let input = "{ \"flag\": true, \"count\": 5 }" in
  let value = parse_from_string input in
  (* pattern match only on the tags we care about *)
  match value with
  | `Obj fields ->
      List.iter (fun (k, v) ->
          match k, v with
          | "flag", `Bool b -> Printf.printf "flag=%b\n" b
          | "count", `Int i -> Printf.printf "count=%d\n" i
          | _ -> ())
      fields
  | _ -> ()

To see how the type evolves, compile with the -dtype flag:

ocamlc -dtype parser.ml

The output will show the inferred type for parse_from_string as something like string -> [> `Bool of bool | `Int of int | `List of ... | `Obj of ... | `String of string]. The new `Bool tag appears only in the set; the function’s type did not need to change.

Trade‑off: loss of exhaustiveness checking and possible type confusion

Because the variant is open ([> ...]), the compiler cannot guarantee that a match covers every possible tag. Forgetting to handle a newly added constructor leads to a Match_failure at runtime. To mitigate this:

• Prefer closed variants ([< `A | `B]) when the set of tags is fixed and known.
• When you must use open variants, enable the warning -warn-error +8 to treat non‑exhaustive matches as errors.
• Keep the variant definition close to the functions that consume it, so the intended set of tags stays visible.

Excessive use of polymorphic variants can also produce long inferred types that are hard to read, especially when combined with functors or module abstractions. In such cases, consider defining an explicit alias or a closed variant and converting at the boundaries.

Actionable closing

If you are building an extensible API, a configuration format, or a parser that may grow over time, start with polymorphic variants for the data model. Use the -dtype flag to inspect inferred types during development, and enable exhaustiveness warnings to catch missing cases early. When the tag set stabilizes, migrate to a closed variant to gain full pattern‑match safety.