On this page

Exercise: Build a Generic OCaml Set Map Library with Functors

Published on September 15, 2026

Enrico Hochkoeppler Profile

By Enrico Hochkoeppler

Web Developer & TutoriaLibre Founder

A functor-based Set and Map library in OCaml is built by parameterizing a balanced binary search tree implementation over a module that provides an element type and a comparison function. The OrderedType signature defines this parameter, the Set.Make functor produces a specialized set module, and the Map.Make functor produces a specialized map module. This article guides you through building such a library from scratch, explaining every design decision, every line of code, and every signature along the way.

The Problem: Why Generic Collections Need Functors​

OCaml's type system does not allow a collection to be polymorphic over its comparison function in the same way that a list is polymorphic over its element type. A list of integers and a list of strings can share the same 'a list type because the list operations never need to compare elements. A set, by contrast, must compare elements to decide where to insert them, whether an element is a member, and how to traverse the structure in order.

If sets were defined as a simple polymorphic type like 'a set, every set operation would need to receive a comparison function as an argument. Inserting an element would require passing both the element and the comparison function. Checking membership would require the same. This would be verbose and error-prone, because nothing would prevent a programmer from using two different comparison functions on the same set, producing inconsistent results.

Functors solve this problem by binding the comparison function to the set type at module creation time. The Set.Make functor takes a module that provides a type t and a function compare : t -> t -> int, and returns a module whose set type is specialized to that element type. The comparison function is stored once, inside the module, and every operation on the set uses it consistently. The resulting set type is abstract, so users cannot accidentally apply operations with a different comparison function.

The same design applies to maps. A map from keys of type K.t to values of type 'v needs a comparison function for the keys. The Map.Make functor takes a module providing the key type and comparison function, and returns a module whose map type is parameterized by the value type.

Step 1: Defining the OrderedType Signature​

Every functor-based collection starts with a signature that describes what the collection needs from its element type. For sets and maps, the element type must be totally ordered. This means there must be a comparison function that returns a negative integer if the first argument is less than the second, zero if they are equal, and a positive integer if the first is greater than the second.

The signature is conventionally called OrderedType.


module type OrderedType = sig

  type t

  val compare : t -> t -> int

end

The signature declares an abstract type t and a comparison function. The type t is abstract because the functor does not need to know anything about the element type beyond the fact that it can be compared. This abstraction is what makes the functor generic: it can be applied to any module that provides these two components.

A module that matches OrderedType is called an ordered type module. Here is a concrete example for strings:


module StringOrder = struct

  type t = string

  let compare = String.compare

end

The String.compare function returns an integer following the same convention. When StringOrder is passed to a functor, the functor uses StringOrder.t as the element type and StringOrder.compare as the comparison function.

It is worth noting that the comparison function must define a total order. If two distinct values compare as equal, the set will treat them as the same element, and the map will treat them as the same key. This is a semantic requirement, not a syntactic one. The functor cannot verify totality; that responsibility belongs to the programmer who writes the OrderedType module.

Step 2: Designing the Set Signature​

Before implementing the set functor, it helps to define the signature that the functor will return. This signature describes the operations that every set module produced by the functor will provide. The OCaml standard library calls this signature Set.S, and it is extensive. For this exercise, a focused signature covering the core operations is sufficient and more instructive.


module type SET = sig

  type elt

  type t

  val empty : t

  val is_empty : t -> bool

  val mem : elt -> t -> bool

  val add : elt -> t -> t

  val remove : elt -> t -> t

  val union : t -> t -> t

  val inter : t -> t -> t

  val diff : t -> t -> t

  val elements : t -> elt list

  val cardinal : t -> int

end

The signature declares two abstract types. elt is the type of set elements, and t is the type of sets themselves. Keeping both abstract means that users cannot inspect the internal representation of a set, which preserves the invariant that every set is built using the same comparison function.

The operations are the familiar set operations. empty is the empty set. is_empty tests whether a set has no elements. mem tests membership. add and remove produce new sets with an element added or removed. union, inter, and diff compute the union, intersection, and difference of two sets. elements returns a sorted list of the set's elements. cardinal returns the number of elements.

Each of these operations is purely functional. They do not modify the input set; they return a new set. Because the underlying data structure is a balanced binary search tree, the new set shares most of its structure with the old set, which makes these operations efficient in both time and memory.

Step 3: Implementing the Set Functor with a Balanced Tree​

The set functor produces a module that matches the SET signature. The implementation uses a balanced binary search tree, specifically a height-balanced tree similar to the one used in the OCaml standard library. The tree is represented by a variant type with two constructors: Empty for an empty tree and Node for a node containing a left subtree, an element, a right subtree, and the height of the subtree.


module MakeSet (Ord : OrderedType) : SET with type elt = Ord.t = struct

  type elt = Ord.t



  type t = Empty | Node of t * elt * t * int



  let empty = Empty



  let is_empty = function Empty -> true | _ -> false



  let height = function Empty -> 0 | Node (_, _, _, h) -> h



  let create l x r =

    let hl = height l and hr = height r in

    Node (l, x, r, 1 + max hl hr)

end

The MakeSet functor takes a module Ord matching OrderedType and returns a module matching SET with the additional equation type elt = Ord.t. This equation is important: it tells the type checker that the abstract type elt in the result is the same as Ord.t, which allows users to pass values of type Ord.t directly to set operations.

The tree type is defined inside the functor, so each application of the functor produces a distinct tree type. This is what makes sets from different functor applications incompatible, even if the element types happen to be the same. Two different OrderedType modules for the same type produce two different set types, which prevents mixing sets built with different comparison functions.

The height function returns the height of a tree, with the empty tree having height zero. The create function builds a node from a left subtree, an element, and a right subtree, computing the height as one plus the maximum of the two subtree heights.

Rotation for Balance​

A binary search tree without balancing degenerates into a linked list when elements are inserted in sorted order. Inserting elements in ascending order would produce a tree where every node has only a right child, and search would take linear time. To prevent this, the tree must rebalance itself after insertions and removals.

The standard approach uses rotations. A left rotation takes a node whose right subtree is taller than its left subtree and restructures the tree so that the right child becomes the new root. A right rotation does the mirror operation.


  let balance l x r =

    let hl = height l and hr = height r in

    if hl > hr + 2 then

      match l with

      | Empty -> assert false

      | Node (ll, lx, lr, _) ->

          if height ll >= height lr then

            create ll lx (create lr x r)

          else

            match lr with

            | Empty -> assert false

            | Node (lrl, lrx, lrr, _) ->

                create (create ll lx lrl) lrx (create lrr x r)

    else if hr > hl + 2 then

      match r with

      | Empty -> assert false

      | Node (rl, rx, rr, _) ->

          if height rr >= height rl then

            create (create l x rl) rx rr

          else

            match rl with

            | Empty -> assert false

            | Node (rll, rlx, rlr, _) ->

                create (create l x rll) rlx (create rlr rx rr)

    else

      create l x r

The balance function checks whether the heights of the left and right subtrees differ by more than two. If they do, it performs one or two rotations to restore the balance. The cases distinguish between a single rotation, when the outer subtree is taller, and a double rotation, when the inner subtree is taller. The assert false branches are unreachable because the height difference condition guarantees that the relevant subtree is non-empty.

This balancing scheme is a simplified version of the one used in the OCaml standard library. It guarantees that the height of a tree with ( n ) nodes is ( O(\log n) ), which in turn guarantees that insertion, removal, and membership testing all run in logarithmic time.

Insertion and Removal​

With the balancing primitive in place, insertion and removal are implemented recursively.


  let rec add x = function

    | Empty -> Node (Empty, x, Empty, 1)

    | Node (l, v, r, _) as t ->

        let c = Ord.compare x v in

        if c = 0 then t

        else if c < 0 then balance (add x l) v r

        else balance l v (add x r)



  let rec remove x = function

    | Empty -> Empty

    | Node (l, v, r, _) ->

        let c = Ord.compare x v in

        if c = 0 then

          match (l, r) with

          | Empty, _ -> r

          | _, Empty -> l

          | _ ->

              let min_r = min_elt r in

              balance l min_r (remove min_r r)

        else if c < 0 then balance (remove x l) v r

        else balance l v (remove x r)



  and min_elt = function

    | Empty -> assert false

    | Node (Empty, v, _, _) -> v

    | Node (l, _, _, _) -> min_elt l

The add function recursively descends the tree. If the element is already present, the original tree is returned unchanged. If the element is less than the current node's value, the function recurses into the left subtree; if greater, into the right subtree. In both cases, the balance function is called to rebalance the tree after the insertion.

The remove function follows the same recursive pattern. When it finds the element to remove, it handles three cases. If the left subtree is empty, it returns the right subtree. If the right subtree is empty, it returns the left subtree. If both subtrees are non-empty, it finds the minimum element of the right subtree, replaces the removed element with that minimum, and removes the minimum from the right subtree. This maintains the binary search tree invariant while preserving balance.

The min_elt function traverses the left spine of a tree to find the smallest element. It is defined with and because it is mutually recursive with remove.

Membership and Set Operations​

Membership testing follows the same descent pattern as insertion.


  let rec mem x = function

    | Empty -> false

    | Node (l, v, r, _) ->

        let c = Ord.compare x v in

        if c = 0 then true

        else if c < 0 then mem x l

        else mem x r

The mem function compares the target element with the current node's value and descends left or right accordingly. It returns true when it finds an equal element and false when it reaches an empty tree.

The set operations union, inter, and diff can be implemented in terms of add, mem, and elements. This is not the most efficient approach, but it is clear and correct, and it illustrates how the operations compose.


  let elements t =

    let rec aux acc = function

      | Empty -> acc

      | Node (l, v, r, _) -> aux (v :: aux acc r) l

    in

    aux [] t



  let cardinal t =

    let rec aux acc = function

      | Empty -> acc

      | Node (l, _, r, _) -> aux (aux (acc + 1) l) r

    in

    aux 0 t



  let union s1 s2 =

    List.fold_left (fun acc x -> add x acc) s1 (elements s2)



  let inter s1 s2 =

    List.fold_left

      (fun acc x -> if mem x s2 then add x acc else acc)

      empty (elements s1)



  let diff s1 s2 =

    List.fold_left

      (fun acc x -> if mem x s2 then acc else add x acc)

      empty (elements s1)

The elements function performs an in-order traversal of the tree, which produces a sorted list. It uses an accumulator to build the list efficiently without repeated appends. The cardinal function counts nodes by traversing the entire tree.

The union function inserts every element of s2 into s1. Because add is idempotent, elements that are already present are not duplicated. The inter function selects elements from s1 that are also members of s2. The diff function selects elements from s1 that are not members of s2.

These implementations are correct but not optimal. The standard library's union, inter, and diff operate directly on the tree structure and achieve better performance by exploiting the ordering. For a learning exercise, the clarity of the list-based implementations is more valuable than their efficiency.

Step 4: Building the Map Functor on Top of the Tree​

A map is an association table that binds keys to values. Like a set, a map needs a comparison function for its keys. The map functor can reuse the same balanced tree structure, but each node stores a key-value pair instead of a single element.

The map signature declares the key type, the map type (which is parameterized by the value type), and the core operations.


module type MAP = sig

  type key

  type 'a t

  val empty : 'a t

  val is_empty : 'a t -> bool

  val mem : key -> 'a t -> bool

  val add : key -> 'a -> 'a t -> 'a t

  val remove : key -> 'a t -> 'a t

  val find : key -> 'a t -> 'a

  val find_opt : key -> 'a t -> 'a option

  val bindings : 'a t -> (key * 'a) list

end

The map type is written 'a t, which means that a map from keys of type key to values of type 'a has type 'a t. The find function returns the value associated with a key and raises Not_found if the key is not present. The find_opt function returns an option instead, which is often more convenient.

The map functor is structurally similar to the set functor, but the tree nodes carry both a key and a value. The comparison function compares keys only.


module MakeMap (Ord : OrderedType) : MAP with type key = Ord.t = struct

  type key = Ord.t



  type 'a t = Empty | Node of 'a t * key * 'a * 'a t * int



  let empty = Empty



  let is_empty = function Empty -> true | _ -> false



  let height = function Empty -> 0 | Node (_, _, _, _, h) -> h



  let create l k v r =

    let hl = height l and hr = height r in

    Node (l, k, v, r, 1 + max hl hr)



  let balance l k v r =

    let hl = height l and hr = height r in

    if hl > hr + 2 then

      match l with

      | Empty -> assert false

      | Node (ll, lk, lv, lr, _) ->

          if height ll >= height lr then

            create ll lk lv (create lr k v r)

          else

            match lr with

            | Empty -> assert false

            | Node (lrl, lrk, lrv, lrr, _) ->

                create (create ll lk lv lrl) lrk lrv (create lrr k v r)

    else if hr > hl + 2 then

      match r with

      | Empty -> assert false

      | Node (rl, rk, rv, rr, _) ->

          if height rr >= height rl then

            create (create l k v rl) rk rv rr

          else

            match rl with

            | Empty -> assert false

            | Node (rll, rlk, rlv, rlr, _) ->

                create (create l k v rll) rlk rlv (create rlr rk rv rr)

    else

      create l k v r



  let rec add k v = function

    | Empty -> Node (Empty, k, v, Empty, 1)

    | Node (l, k', v', r, _) as t ->

        let c = Ord.compare k k' in

        if c = 0 then Node (l, k, v, r, height t)

        else if c < 0 then balance (add k v l) k' v' r

        else balance l k' v' (add k v r)



  let rec find k = function

    | Empty -> raise Not_found

    | Node (l, k', v, r, _) ->

        let c = Ord.compare k k' in

        if c = 0 then v

        else if c < 0 then find k l

        else find k r



  let find_opt k m =

    try Some (find k m) with Not_found -> None



  let rec remove k = function

    | Empty -> Empty

    | Node (l, k', v, r, _) ->

        let c = Ord.compare k k' in

        if c = 0 then

          match (l, r) with

          | Empty, _ -> r

          | _, Empty -> l

          | _ ->

              let min_k, min_v = min_binding r in

              balance l min_k min_v (remove min_k r)

        else if c < 0 then balance (remove k l) k' v r

        else balance l k' v (remove k r)



  and min_binding = function

    | Empty -> assert false

    | Node (Empty, k, v, _, _) -> (k, v)

    | Node (l, _, _, _, _) -> min_binding l



  let bindings m =

    let rec aux acc = function

      | Empty -> acc

      | Node (l, k, v, r, _) -> aux ((k, v) :: aux acc r) l

    in

    aux [] m

end

The map functor mirrors the set functor almost line for line, with two differences. First, the tree node carries a key and a value in addition to the left and right subtrees and the height. Second, the add function replaces the value when the key already exists, rather than returning the original tree unchanged. This is the expected behavior for a map: adding a binding for a key that is already present updates the existing binding.

The find function raises Not_found when the key is not in the map. The find_opt function wraps find in a try expression and returns None if the exception is raised. The bindings function performs an in-order traversal and returns a list of key-value pairs sorted by key.

Step 5: Using the Library​

With the functors defined, using the library requires only that the user provides an OrderedType module for the element or key type. Here is a complete example using integers and strings.


module IntOrder = struct

  type t = int

  let compare = Int.compare

end



module IntSet = MakeSet (IntOrder)

module IntMap = MakeMap (IntOrder)



let () =

  let s = IntSet.(empty |> add 3 |> add 1 |> add 4 |> add 1) in

  Printf.printf "Set elements: %s\n"

    (String.concat ", " (List.map string_of_int (IntSet.elements s)));

  Printf.printf "Cardinal: %d\n" (IntSet.cardinal s);

  Printf.printf "Member 3: %b\n" (IntSet.mem 3 s);

  Printf.printf "Member 2: %b\n" (IntSet.mem 2 s);



  let m = IntMap.(empty |> add 1 "one" |> add 2 "two" |> add 1 "uno") in

  Printf.printf "Find 1: %s\n" (IntMap.find 1 m);

  Printf.printf "Find 2: %s\n" (IntMap.find 2 m)

The IntOrder module defines the integer type and comparison function. Applying MakeSet to IntOrder produces the IntSet module. Applying MakeMap to the same IntOrder produces the IntMap module. Both modules are specialized to integers and can coexist without interfering with each other.

The example builds a set by adding elements 3, 1, 4, and 1. The duplicate 1 is ignored, so the set contains three elements: 1, 3, and 4. The elements function returns them in sorted order. The map example adds three bindings: 1 -> "one", 2 -> "two", and 1 -> "uno". The second addition for key 1 replaces the first value, so find 1 returns "uno".

Common Pitfalls and How to Avoid Them​

The first pitfall is forgetting the with type elt = Ord.t equation on the functor's return signature. Without this equation, the elt type in the result is abstract and distinct from Ord.t, which means users cannot pass values of type Ord.t to set operations. The compiler will reject IntSet.add 3 s because 3 has type int, not IntSet.elt. The equation establishes the type equality that makes the module usable.

The second pitfall is using a comparison function that does not define a total order. If compare returns inconsistent results, the set or map will behave incorrectly in ways that are difficult to debug. Elements may be duplicated, membership tests may fail for elements that are present, and the tree may become unbalanced. The comparison function must be antisymmetric, transitive, and consistent with equality.

The third pitfall is exposing the tree type in the module signature. If t is not abstract, users can construct trees directly, bypassing the comparison function and breaking the invariants of the data structure. The signature must declare type t (or type 'a t) without a definition, so the representation is hidden.

The fourth pitfall is forgetting to balance the tree after insertion and removal. Without balancing, the tree degenerates into a linked list for sorted input, and operations become linear in the number of elements. The balance function must be called at every recursive step where the tree structure changes.

The fifth pitfall is using structural equality or polymorphic comparison on sets or maps. Because the tree representation is hidden and the comparison function is baked into the module, structural equality does not correspond to set equality. Two sets containing the same elements may have different tree structures. To test set equality, the module should provide an equal function that compares elements using Ord.compare, not the built-in =.

Key Takeaways​

A functor-based Set and Map library in OCaml is built from three components: an OrderedType signature that describes what the collection needs from its element type, a Set.Make functor that produces a specialized set module with a balanced binary search tree, and a Map.Make functor that produces a specialized map module using the same tree structure. The functor binds the comparison function to the collection type at module creation time, ensuring consistency and enabling the element type to be abstract. The with type elt = Ord.t equation on the functor's return signature is what makes the resulting module usable with values of the original type. Balancing the tree after insertion and removal is what keeps operations logarithmic. Hiding the tree representation in the signature is what preserves the invariants of the data structure. Understanding this design illuminates how OCaml's standard Set and Map modules work and provides a foundation for building other functor-based generic containers.

Frequently Asked Questions​

Why does OCaml use functors for Set and Map instead of polymorphic types?

Functors bind the comparison function to the set or map type at module creation time. This ensures that every operation uses the same comparison function consistently, and it makes the element type abstract so users cannot mix sets built with different comparison functions.

What is the OrderedType signature?

OrderedType is a module signature that declares an abstract type t and a comparison function compare : t -> t -> int. It describes what a functor-based collection needs from its element or key type.

Why is the with type elt = Ord.t equation necessary?

Without this equation, the elt type in the functor's result is abstract and distinct from Ord.t. The equation establishes the type equality that allows users to pass values of type Ord.t directly to set operations.

What data structure does the OCaml Set module use internally?

The OCaml Set module uses a balanced binary search tree, specifically a height-balanced tree similar to an AVL tree. Insertion, removal, and membership testing take logarithmic time in the number of elements.

Can I use the same OrderedType module for both Set.Make and Map.Make?

Yes. The same OrderedType module can be passed to both Set.Make and Map.Make. The resulting set and map modules are independent and use the same comparison function for their elements and keys respectively.

What happens if the comparison function is not a total order?

The set or map will behave incorrectly. Elements may be duplicated, membership tests may fail, and the tree may become unbalanced. The comparison function must be antisymmetric, transitive, and consistent with equality.

Found this helpful? Share the knowledge...

... or support this project to keep it alive!

Buy Me a Coffee

Previous

Extensible Variants and Exn Patterns

Next

Object-Oriented Programming