Architecting Generic Data Structures with OCaml Functors

In many functional languages, code reuse is achieved through generic functions. However, in OCaml, when you need to abstract over entire modules—such as creating a Set or Map that works with any data type—standard generic functions are insufficient. The solution is the Functor. A functor is a function that takes one module as input and returns a new module as output, allowing you to write logic once while remaining decoupled from the specific types it operates upon.

To use functors, you must define three components: a Signature (module type) that describes the required interface, the Functor that implements the logic, and an Input Module that provides the concrete data.

Defining the Interface with Signatures

Before writing the functor, you must specify what it expects from the input module. This is done using a signature. For a generic Set, we need the type of elements we want to store and a way to compare two elements of that type.

module type ORDERED = sig
  type t
  val compare : t -> t -> int
end

Implementing the Functor

The functor uses module keyword and accepts a parameter M that conforms to our signature. Inside the body, we define the logic using the types and functions provided by M.

module MakeSet (M : ORDERED) : sig
  type t
  val add : t -> t -> t
  val mem : t -> t -> bool
end = struct
  type t = M.t list

  let rec mem x list =
    match list with
    | [] -> false
    | h :: t -> if M.compare x h = 0 then true else mem x t

  let add x list =
    if mem x list then list else x :: list
end

Instantiating the Functor with a Concrete Module

Once the functor is defined, it is just a template. To create a functional module, you apply it to a concrete module that satisfies the signature. Here, we apply it to integer logic.

(* Define a concrete module that satisfies ORDERED *)
module IntOrdered = struct
  type t = int
  let compare a b = if a < b then -1 else if a > b then 1 else 0
end

(* Apply the functor to create the IntSet module *)
module IntSet = MakeSet(IntOrdered)

(* Usage *)
let my_set = IntSet.add 5 (IntSet.add 10 [])
let has_five = IntSet.mem 5 my_set (* returns true *)

Comparison: Functors vs. Generic Functions

It is a common mistake to use value-level polymorphism (generics like 'a -> 'a -> bool) when module-level abstraction is required. Here is how to choose between them:

Feature	Generic Functions ('a)	Functors (Modules)
Scope	Logic over individual values.	Logic over types and structures.
Constraint	Can work on any type.	Must satisfy a specific Signature.
Use Case	Sorting a list, filtering data.	Creating Sets, Maps, Database drivers.

Limitations and Common Pitfalls

While powerful, functors introduce specific trade-offs to consider:

• Cognitive Load: Deeply nested functors (functors that return functors) can make type signatures extremely difficult for teams to read and debug.
• Compilation Overhead: Because the compiler must generate a new module for every functor application, excessive use of functors can significantly increase compilation times in very large projects.
• Abstraction Mismatch: Confusing module-level polymorphism (Functors) with value-level polymorphism (Generics/Polymorphic variants) is a common architectural error that leads to over-engineered solutions.

Verification Steps

To verify the implementation compiles correctly:

1. Save the code to a file named set_functor.ml
2. Run ocamlc -c set_functor.ml to compile to bytecode
3. Run ocamlopt -c set_functor.ml to compile to native code
4. Both commands should complete without type errors

Expected result: The compiler accepts the module definitions and produces .cmo/.cmx files. The resulting IntSet module operates on integers with proper type safety enforced by the ORDERED signature.