Skip to content
Tutorials Center
My learning

Topics

Lesson 28 of 40 ยท Modules and Functors

Functors: Functions from Modules to Modules

Understand OCaml functors step by step. Build modules parameterized by other modules, use Map.Make and Set.Make, share types with constraints, and know when functors pay off.

A functor is a function that takes a module and returns a module. It sounds exotic, but the need is ordinary: you want a data structure, such as a set, that works for any element type, as long as that type provides a way to compare two elements. In OCaml, the functor receives "a module with a type and a comparison" and returns "a set module for that type".

You have already used functors if you have used Map.Make or Set.Make from the standard library. This lesson shows how they work and how to write your own.

OCaml is not available in the site's code runners, so the ocaml blocks are read-only. Outputs appear only where they are certain. The Python stand-in passes a "comparison module" as an argument, the closest everyday idea.

Why not just polymorphism?

A polymorphic function such as List.sort compare uses the built-in structural compare. That is fine for ints, but it is wrong when you want case-insensitive strings, or when your type is abstract or contains functions (structural comparison raises on closures). A functor lets the caller supply the right operations, and the result can be specialised to them.

Using Set.Make

Set.Make expects a module matching the signature Set.OrderedType:

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

Give it one:

OCAML
module IntSet = Set.Make (Int)       (* Int has type t = int and compare *)

module CiString = struct
  type t = string
  let compare a b = String.compare (String.lowercase_ascii a) (String.lowercase_ascii b)
end

module NameSet = Set.Make (CiString)

let s = NameSet.(empty |> add "Ada" |> add "ada" |> add "Grace")
let () = Printf.printf "%d\n" (NameSet.cardinal s)
(* prints: 2   ("Ada" and "ada" are equal under CiString.compare) *)

IntSet and NameSet are complete modules with add, mem, union, inter, fold, elements and the rest, each fast and typed for its element type. Because the comparison is part of the module, a set built with one ordering cannot be accidentally mixed with another.

Map.Make works the same way, giving maps with keys of your type:

OCAML
module StrMap = Map.Make (String)

let m = StrMap.(empty |> add "one" 1 |> add "two" 2)
let () = print_int (StrMap.find "two" m)
(* prints: 2 *)

Standard Hashtbl.Make takes an equal and a hash function in the same way.

Writing a functor

The syntax is module F (X : SIG) = struct ... end. Here is a small one that builds a "priority queue" module from any ordered type, implemented as a sorted list:

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

module type PQ = sig
  type elt
  type t
  val empty : t
  val push : elt -> t -> t
  val pop : t -> (elt * t) option
end

module MakePQ (O : ORDERED) : PQ with type elt = O.t = struct
  type elt = O.t
  type t = elt list

  let empty = []

  let rec push x = function
    | [] -> [ x ]
    | y :: ys as l -> if O.compare x y <= 0 then x :: l else y :: push x ys

  let pop = function
    | [] -> None
    | x :: rest -> Some (x, rest)
end

module IntPQ = MakePQ (Int)

let () =
  let q = IntPQ.(empty |> push 5 |> push 1 |> push 3) in
  match IntPQ.pop q with
  | Some (x, _) -> Printf.printf "min = %d\n" x
  | None -> ()
(* prints: min = 1 *)
flowchart LR
    A["Int<br/>(ORDERED)"] --> F["MakePQ<br/>functor"]
    F --> B["IntPQ<br/>(PQ with elt = int)"]
    C["String<br/>(ORDERED)"] --> F
    F --> D["StringPQ"]

Figure: a functor builds a new module from an argument module.

Sharing constraints: with type

Notice PQ with type elt = O.t. Without it, elt would be abstract in the result, and IntPQ.push 5 would be rejected because the compiler would not know that elt is int. A with type constraint reveals just enough about an abstract type so clients can use it. It is the single most common source of "type is abstract" errors when starting with functors; the fix is nearly always a missing with type.

Functors as extension

Functors can add functionality to a module. This one gives any module with compare the operators <, >, max and min:

OCAML
module Make_comparable (O : ORDERED) = struct
  let ( < ) a b = O.compare a b < 0
  let ( > ) a b = O.compare a b > 0
  let max a b = if O.compare a b >= 0 then a else b
end

module IntC = Make_comparable (Int)
let biggest = IntC.max 3 9      (* 9 *)

Jane Street's Base library follows this pattern with Comparable.Make: define compare once and derive the rest.

Applicative functors and generativity

OCaml functors are applicative: applying Set.Make (Int) twice produces compatible types, so Set.Make(Int).t from two different places is the same type. For modules that must create fresh types each time (for example with mutable global state), you can write the functor with () as its argument to make it generative. Most code does not need this.

When functors are worth it

Use a functor when a module's behaviour depends on a set of operations and types that go together (an ordering plus its type, a hash plus equality, a storage backend). For a single function parameter a normal higher-order function is simpler. For choosing a module at run time, see first-class modules.

Stand-in: passing a comparison "module"

Python Stand-in: a set built from a comparison parameter

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.

make_set plays the role of the functor and order is the argument module. What OCaml adds is that the type checker guarantees the argument really has the operations the functor needs.

Common mistakes

  • Forgetting with type and getting abstract-type errors.
  • Using polymorphic compare inside a functor body when you should call the argument's compare.
  • Over-engineering: not every parameterization needs a functor.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is a functor in OCaml?

    A functor takes one or more modules as arguments and builds a new module.
  2. 2. What does module IntSet = Set.Make (Int) create?

    The functor Set.Make receives Int (type t and compare) and returns a set module for int elements.
  3. 3. Why does MakePQ use PQ with type elt = O.t?

    Without the constraint, elt would be abstract and IntPQ.push 5 would not type-check.
  4. 4. When is a plain higher-order function better than a functor?

    A functor is for bundles of types and operations that belong together; a single behaviour is simpler to pass as a function.

Summary

  • A functor is a function from modules to modules, written module F (X : SIG) = struct ... end.
  • Set.Make, Map.Make and Hashtbl.Make take an ordering or hash module and return a specialised data-structure module.
  • Use with type constraints to expose type equalities of the result.
  • Reach for a functor when types and operations travel together. Otherwise pass a function.

Next: First-Class Modules and Module Tools