Programming in the large
The features you have met so far, functions, lists, records, variants, are about programming in the small: getting one piece of logic right. Real systems are large, written by many people over many years, and their main difficulty is different: how do you divide a program into parts that can be understood, tested and changed one at a time, without every change rippling everywhere?
OCaml's answer is its module system, and it is the feature experienced OCaml programmers miss most in other languages. Three ideas, each simple:
- A module is a named collection of definitions: types, values, functions, even other modules. Every source file is automatically a module.
- A signature is the module's interface: which of its definitions others may use, with which types. A signature can make a type abstract, so that users can hold and pass values of the type but cannot see or depend on how it is built.
- A functor is a function from modules to modules: "give me any module that provides an ordering, and I will give you a set module for that ordering".
Together they let a team change the inside of a module freely, with the compiler checking that nothing outside depended on what changed.
Structures, signatures, functors
Definition— Module (structure)
module Name = struct ... end defines a module containing the definitions between struct and end. Outside, they are referred to as Name.x. A file geometry.ml defines a module Geometry automatically.
Definition— Signature (module type)
module type NAME = sig ... end lists declarations: type t, val area : t -> float, and so on. Writing module M : NAME = struct ... end checks the structure against the signature and hides everything the signature does not mention. A file geometry.mli is the signature of geometry.ml.
Definition— Abstract type
In a signature, type t with no definition makes t abstract: outside the module, values of type t can only be created and inspected through the module's functions. The module's author can then change the representation without breaking any user.
Definition— Functor
module F (X : SIG) = struct ... end defines a functor, a module parameterised by a module X that must satisfy the signature SIG. Applying it, module M = F (Arg), produces a new module. Map.Make and Set.Make in the standard library are functors.
Definition— open and local open
open M brings all of M's names into scope for the rest of the file. The local open M.(expr), or let open M in expr, does so only inside expr, which is usually the better choice.
Modules at work
A module with an abstract type
(* A signature: what users of the module may see. *)
module type QUEUE = sig
type 'a t (* abstract: the representation is hidden *)
val empty : 'a t
val push : 'a -> 'a t -> 'a t
val pop : 'a t -> ('a * 'a t) option
val size : 'a t -> int
end
(* A structure: the implementation. A queue as two lists, front and back. *)
module Fifo : QUEUE = struct
type 'a t = { front : 'a list; back : 'a list }
let empty = { front = []; back = [] }
let push x q = { q with back = x :: q.back }
let rec pop q =
match q.front, q.back with
| x :: front, _ -> Some (x, { q with front })
| [], [] -> None
| [], back -> pop { front = List.rev back; back = [] }
let size q = List.length q.front + List.length q.back
end
let rec drain q =
match Fifo.pop q with
| None -> []
| Some (x, rest) -> x :: drain rest
let () =
let q = Fifo.(empty |> push "Asha" |> push "Bruno" |> push "Chidi") in
Printf.printf "size %d\n" (Fifo.size q);
match Fifo.pop q with
| None -> print_endline "empty"
| Some (first, rest) ->
Printf.printf "first: %s\n" first;
let rest = Fifo.push "Dilnoza" rest in
print_endline (String.concat ", " (drain rest))size 3
first: Asha
Bruno, Chidi, DilnozaThis is a classic functional queue. New elements are pushed onto the back list in constant time; elements are popped from the front list, and when the front runs out, the back list is reversed once to become the new front. Each element is reversed at most once, so on average every operation takes constant time.
The signature QUEUE is what makes it a good module. It says that 'a t exists but not what it is, so the two-list record is invisible from outside. In the toplevel, after the definitions above:
# Fifo.push 1 Fifo.empty;;
- : int Fifo.t = <abstr>
# let broken : int Fifo.t = { front = [ 1 ]; back = [] };;
Line 1, characters 28-33:
1 | let broken : int Fifo.t = { front = [ 1 ]; back = [] };;
^^^^^
Error: Unbound record field frontThe value is shown as <abstr>, and code outside the module cannot build or inspect the record. If the implementation later changes (to an array-based ring buffer, say), no user of Fifo needs to change, and the compiler guarantees it.
Fifo.(empty |> push "Asha" |> ...) is a local open: inside the parentheses, empty and push mean Fifo.empty and Fifo.push. It keeps code short without importing names into the whole file.
The standard functors: Map and Set
(* The standard library's Map and Set are functors: give them an ordered type. *)
module String_map = Map.Make (String)
module Int_set = Set.Make (Int)
let word_counts text =
String.split_on_char ' ' text
|> List.filter (fun w -> w <> "")
|> List.fold_left
(fun m w -> String_map.update w (function None -> Some 1 | Some n -> Some (n + 1)) m)
String_map.empty
(* Any module with a type t and a compare function can be a key. *)
module Date = struct
type t = { year : int; month : int; day : int }
let compare = compare
end
module Date_map = Map.Make (Date)
let () =
let counts = word_counts "the rain in spain falls mainly on the plain in the rain" in
String_map.iter (fun w n -> Printf.printf "%s=%d " w n) counts;
print_newline ();
Printf.printf "rain: %d, snow: %d\n"
(String_map.find "rain" counts)
(Option.value ~default:0 (String_map.find_opt "snow" counts));
let evens = Int_set.of_list [ 8; 2; 4; 2; 6 ] and small = Int_set.of_list [ 1; 2; 3; 4 ] in
Printf.printf "union %s; inter %s\n"
(String.concat "," (List.map string_of_int (Int_set.elements (Int_set.union evens small))))
(String.concat "," (List.map string_of_int (Int_set.elements (Int_set.inter evens small))));
let events =
Date_map.(
empty
|> add { Date.year = 2026; month = 3; day = 14 } "launch"
|> add { Date.year = 2025; month = 12; day = 1 } "kick-off"
|> add { Date.year = 2026; month = 1; day = 20 } "review")
in
Date_map.iter (fun d e -> Printf.printf "%04d-%02d-%02d %s\n" d.Date.year d.month d.day e) eventsfalls=1 in=2 mainly=1 on=1 plain=1 rain=2 spain=1 the=3
rain: 2, snow: 0
union 1,2,3,4,6,8; inter 2,4
2025-12-01 kick-off
2026-01-20 review
2026-03-14 launchMap.Make takes any module that has a type t and a function compare : t -> t -> int, and returns a module of immutable, balanced-tree maps with those keys: add, find, find_opt, update, remove, iter, fold, bindings and dozens more. The standard String and Int modules already have the right shape, so Map.Make (String) just works. Iteration visits keys in order, which is why the words and the dates come out sorted.
For Date, we wrote the module ourselves. Its compare is the built-in structural comparison, which compares records field by field in declaration order, so putting year before month before day gives chronological order. (Writing { Date.year = 2026; month = 3; day = 14 } tells OCaml which module's record fields we mean; the first qualified field is enough.)
Notice that String_map.update takes a function from the old binding (None if absent) to the new one, which handles "insert or increment" in one call.
Writing a functor
In lesson 4, the binary search tree used OCaml's built-in <. A functor lets the user decide what the ordering is:
(* The signature a functor's argument must satisfy. *)
module type ORDERED = sig
type t
val compare : t -> t -> int
end
(* A functor: a module parameterised by another module. *)
module Tree_set (Ord : ORDERED) = struct
type elt = Ord.t
type t = Leaf | Node of t * elt * t
let empty = Leaf
let rec add x = function
| Leaf -> Node (Leaf, x, Leaf)
| Node (l, v, r) as t ->
let c = Ord.compare x v in
if c < 0 then Node (add x l, v, r) else if c > 0 then Node (l, v, add x r) else t
let rec mem x = function
| Leaf -> false
| Node (l, v, r) ->
let c = Ord.compare x v in
c = 0 || if c < 0 then mem x l else mem x r
let rec elements = function
| Leaf -> []
| Node (l, v, r) -> elements l @ (v :: elements r)
let of_list xs = List.fold_left (fun s x -> add x s) empty xs
end
(* Two different orderings on strings give two different set modules. *)
module Caseless = struct
type t = string
let compare a b = String.compare (String.lowercase_ascii a) (String.lowercase_ascii b)
end
module Names = Tree_set (String)
module Caseless_names = Tree_set (Caseless)
module Descending = Tree_set (struct
type t = int
let compare a b = Int.compare b a
end)
let () =
let input = [ "Lagos"; "lima"; "LAGOS"; "Kyiv"; "Lima"; "Hanoi" ] in
print_endline (String.concat " " (Names.elements (Names.of_list input)));
print_endline (String.concat " " (Caseless_names.elements (Caseless_names.of_list input)));
Printf.printf "%b %b\n" (Names.mem "LIMA" (Names.of_list input))
(Caseless_names.mem "LIMA" (Caseless_names.of_list input));
print_endline
(String.concat " " (List.map string_of_int (Descending.elements (Descending.of_list [ 3; 9; 1; 7 ]))))Hanoi Kyiv LAGOS Lagos Lima lima
Hanoi Kyiv Lagos lima
false true
9 7 3 1One functor, three set modules. Names uses ordinary string comparison, where upper-case letters sort before lower-case ones and "Lima" and "lima" are different. Caseless_names treats them as the same element (the first one inserted is kept). Descending is built from an anonymous structure written inline, and sorts integers from largest to smallest.
The important property is that each application produces a distinct type: a Names.t cannot be passed to Caseless_names.mem. That is not pedantry. A tree built with one ordering and searched with another would silently give wrong answers, and the type system rules the mistake out. It is the same reason that Map.Make (String).t and Map.Make (Caseless).t are different types.
Signatures that hide, and signatures that share
A signature is a filter: it lets through exactly what it mentions, and it can make a type abstract. Sometimes that filter is too strong. Suppose you want to say "this module is a map whose keys are strings". The standard library describes every map module with the signature Map.S, in which the key type is abstract. Constrain a string map with it, and the keys become unusable. In the toplevel:
# module B : Map.S = Map.Make (String);;
module B : Map.S
# B.add "a" 1 B.empty;;
Line 1, characters 6-9:
1 | B.add "a" 1 B.empty;;
^^^
Error: This constant has type string but an expression was expected of type
B.keyFrom outside, B.key is some unknown type, so not even a string literal fits. The fix is a sharing constraint, with type, which takes a signature and reveals one of its abstract types:
module type STRING_MAP = Map.S with type key = string
module A : STRING_MAP = Map.Make (String)
let one = A.add "a" 1 A.empty (* accepted: A.key is known to be string *)This is how signatures are used at scale: a library publishes one general signature, and each use reveals precisely the types its clients need to know, hiding the rest. Functors use the same mechanism in their results: the signature of Map.Make (Ord) is Map.S with type key = Ord.t, which is why Map.Make (String) accepts strings as keys while still hiding how the tree is built.
How do functors compare with the abstraction tools of other languages? A functor plays the role that generics with interface constraints play in Java or C#, or traits in Rust: "this code works for any t that has a compare". The differences are that the argument is an explicit module, chosen by the programmer rather than found by the compiler, so one type can have several orderings, as Names and Caseless_names showed; and that the result is a whole module of related types and functions, not just one function. Haskell's type classes choose the "implementation" automatically from the type; OCaml's functors make you pass it, which is more verbose and more explicit.
Modules in real projects
In a real project, every .ml file is a module, and most have a matching .mli interface file. For a file fifo.ml, the interface fifo.mli contains exactly what our QUEUE signature contained:
(** First-in, first-out queues. All operations are purely functional. *)
type 'a t
val empty : 'a t
val push : 'a -> 'a t -> 'a t
(** [pop q] is the oldest element and the rest of the queue, or [None] if [q] is empty. *)
val pop : 'a t -> ('a * 'a t) option
val size : 'a t -> intInterface files are where OCaml teams put their documentation (comments starting with (** are turned into HTML by the odoc tool), and they are what a code reviewer reads first. They also speed up builds: when a change to a module's implementation leaves its .mli untouched, the modules that use it need not be recompiled (dune arranges this in development builds; optimised release builds may still recompile them to inline across modules).
A few more facts you will meet:
include Mcopies all ofM's definitions into the current module, the usual way to extend a module:module List = struct include List let sum = fold_left ( + ) 0 end.- Libraries are modules of modules. Dune wraps each library in a single top-level module, so a library
shopwith filescart.mlandprice.mlis used asShop.CartandShop.Price. - First-class modules let you pack a module into an ordinary value and unpack it later, for plug-in architectures and similar dynamic choices. They are an advanced feature; you will recognise them by the syntax
(module M : S). - Jane Street's Base and Core libraries, an alternative standard library widely used in industry, are built around these ideas: almost every type is a module with its own
compare,sexp_of_tand so on.
Where ML modules came from
The idea of structures, signatures and functors comes from Standard ML, OCaml's sibling in the ML family, whose module system David MacQueen proposed in the mid-1980s. It answered a question that was hard at the time: how can a typed language let you build large programs out of separately written, separately compiled parts, with interfaces checked by the compiler and implementations genuinely hidden?
OCaml's module system grew out of Xavier Leroy's research in the early 1990s on manifest types (the with type constraints you just saw) and applicative functors, in which applying the same functor to the same module twice gives compatible types. That work made separate compilation of .ml and .mli files fit cleanly with the type theory, and it is the design you use today, with later additions such as first-class modules (OCaml 3.12, 2010) and module aliases.
Few mainstream languages have adopted ML-style modules wholesale, but the ideas travelled: abstract types behind interfaces, explicit instantiation of generic code, and the discipline of designing an interface before an implementation are all visible in Rust's traits and modules, in Scala's objects and traits, and in how large OCaml codebases at companies such as Jane Street are organised: thousands of modules, each with an .mli file reviewers read first.
Common misconceptions
Misconception
"Modules are like classes." A module has no instances: there is exactly one Fifo, and the queues are ordinary values of type 'a Fifo.t passed to its functions. Modules organise and hide code; they do not create objects. (OCaml does have classes and objects, separately, and they are used much less.)
Misconception
"open everything at the top of each file, to save typing." Opening many modules makes it hard to tell where a name comes from and can silently shadow definitions. Experienced OCaml programmers open a few modules deliberately (often a project's own prelude) and use qualified names or local opens elsewhere.
Misconception
"Functors are an exotic feature." You use one every time you write Map.Make (String). Writing your own is less common in application code than in libraries, but the pattern, "this code works for any module that provides these operations", is everyday OCaml.
Misconception
"An abstract type costs something at run time." Abstraction is enforced entirely by the type checker. At run time a 'a Fifo.t is just the record inside; hiding it costs nothing.
Exercises
1. Modules, signatures and functors
Warm-upHumanA signature declares type t without saying what t is. What does that achieve?
2. Modules, signatures and functors
CoreComputationalWhat does this program print?
module M = Map.Make (String)
let () =
let m = M.(empty |> add "b" 2 |> add "a" 1 |> add "b" 20) in
M.iter (fun k v -> Printf.printf "%s:%d " k v) m;
print_newline ()
3. Modules, signatures and functors
Warm-upComputationalWhat does this program print?
module Int_set = Set.Make (Int)
let () = Printf.printf "%d\n" (Int_set.cardinal (Int_set.of_list [ 5; 3; 5; 1; 3 ]))
4. Modules, signatures and functors
CoreComputationalWhat does this program print?
module Caseless_set = Set.Make (struct
type t = string
let compare a b = String.compare (String.lowercase_ascii a) (String.lowercase_ascii b)
end)
let () =
[ "Oslo"; "OSLO"; "rome"; "oslo"; "Rome" ]
|> Caseless_set.of_list
|> Caseless_set.cardinal
|> Printf.printf "%d\n"
5. Modules, signatures and functors
CoreComputationalWhat does this program print?
module Desc = Set.Make (struct
type t = int
let compare a b = Int.compare b a
end)
let () =
Desc.of_list [ 2; 8; 5; 8 ]
|> Desc.elements
|> List.map string_of_int
|> String.concat " "
|> print_endline
6. Modules, signatures and functors
StretchHumanmodule A = Tree_set (String) and module B = Tree_set (Caseless) come from the same functor. Why does OCaml refuse B.mem "x" (A.of_list ["X"])?
7. Modules, signatures and functors
Warm-upHumanWhat does Fifo.(empty |> push 1 |> push 2) mean?
Further reading and resources
- The OCaml Manual: The module systemThe manual's tutorial on structures, signatures, functors and separate compilation.
- The OCaml Manual: Module typesThe precise language of signatures.
- Modules (OCaml documentation)
- Functors (OCaml documentation)
- The Map.Make functorEvery operation on the maps it creates.