Modules

Fun and Profit with OCaml

Modules and Abstraction

Part 3 of 3

Structures

Defining structures

All OCaml programs are organised into modules. The simplest form of module is a structure. You can think of structures as collections of definitions. Structures can be created using the module and struct keywords:

Defining structures

module M = struct type t = T let x = T end

All OCaml programs are organised into modules; a structure is the simplest form of module.
Structures are collections of definitions.
Created using the module and struct keywords.

Accessing structure components

The components of a module can be accessed using the . operator:

Accessing structure components

let y = M.x

Reach inside a module with the . operator.
It works for types as well as values: y above has type M.t.

let y = M.x

Note that the . operator works for types as well as values: the y variable defined above has type M.t.

A real world module

Modules group several related types together with the functions that operate on them. Consider a small Point module:

Example

module Point = struct type x = int type y = int type t = { x : x; y : y } let origin = { x = 0; y = 0 } let make x y = { x; y } let add p1 p2 = { x = p1.x + p2.x; y = p1.y + p2.y } end

A module can define more than one type: here x and y name the two coordinates, and t is the point built from them.
Point.origin, Point.make, and Point.add are all reached the same way, with ..

let p = Point.add Point.origin (Point.make 3 4)

p is { x = 3; y = 4 }. Everything about points lives under one name, Point, instead of floating around as loose top-level definitions that could clash with, say, some other part of the program's own origin or add.

x and y are aliases for int, not new, distinct types: nothing stops you from writing p1.x + p2.y, mismatched coordinate or not. Naming them separately is about making signatures self-documenting as make : x -> y -> t reads better than make : int -> int -> t. Later in this lesson we will see how a signature can make a type genuinely opaque, so that mixing things up really does become a compile error.

Files as structures

In OCaml every source file defines a structure. For example, a file called foo.ml would be treated as the definition of a module called Foo. We have already used such modules in earlier examples: for instance the List.map function of the standard library is defined in a file called list.ml.

Files as structures

Every source file is already a structure; no module ... = struct needed.
foo.ml defines a module named Foo: the base name with its first letter capitalised.
List.map is just the map defined in the standard library's list.ml.

Define a module Temperature containing a function celsius_to_fahrenheit : float -> float that converts a Celsius temperature to Fahrenheit (f = c * 9.0 / 5.0 + 32.0).

module Temperature = struct let celsius_to_fahrenheit c = failwith "not implemented" end

Show reference solution

Nothing about modules changes how you write the function body — the module ... = struct ... end wrapper is just packaging.

module Temperature = struct let celsius_to_fahrenheit c = c *. 9.0 /. 5.0 +. 32.0 end

Signatures and abstraction

Just as all values in OCaml have a type, all modules have a module type. As you can see from the output, the module M defined above has the module type:

Signatures and abstraction

sig
  type t = T
  val x : t
end

Every module has a module type, usually called a signature.
A signature lists the types and values a module contains.
M above holds a variant type t with one constructor, and a value x of type t.

sig
  type t = T
  val x : t
end

This means that it contains a variant type t with a single T constructor, and a value x of type t. The module types of structures, like the one above, are often called signatures.

Signature ascription

While OCaml will infer the module type of a structure from its definition, you can also ascribe it a more restricted signature. This allows us to hide some of the details of the structure:

A named signature

module type INT_SET = sig type t val empty : t val mem : int -> t -> bool val add : int -> t -> t end

A named module type describes a public interface.
type t exposes the type's name while hiding its representation.

Naming a module type like INT_SET lets more than one module promise to satisfy it. Any structure ascribed as INT_SET must supply exactly these three names — no more, no fewer — which is what makes the next step possible: swapping one IntSet implementation for another without touching anything that only knows about INT_SET.

Signature ascription

module IntSet : INT_SET = struct type t = int list let empty = [] let mem i s = List.mem i s let add i s = if mem i s then s else i :: s end

A structure can be given a signature that publishes less than it actually contains.
Another implementation can promise the same INT_SET interface.

The colon in module IntSet : INT_SET = struct ... end is a signature ascription: it restricts what the outside world sees of IntSet to exactly the INT_SET signature, even though the struct ... end on the right defines more (the concrete type t = int list). Read it the way you'd read a value's type annotation, let x : int = 5, just one level up — for a module instead of a value.

What ascription hides

OCaml infers a structure's module type by default; ascribing one restricts what callers can see.
Here IntSet publishes a type t representing sets of integers.
The signature gives t no definition, so the fact that it is an int list never leaves the module.
Callers can only use empty, mem and add.

Why does restricting IntSet's signature to omit the definition of t matter?

It makes IntSet.add run faster.
It hides the implementation detail that t = int list, so client code cannot depend on it, and the implementation can later change (say, to a tree) without breaking callers.
It's required syntax; OCaml refuses to compile a module signature without hiding at least one type.
It prevents IntSet from ever being used as a functor argument.

Why: this is abstraction: as long as callers only use the names published in the signature (empty, mem, add, and the opaque type t), the module's author is free to change how t is represented internally. Nothing outside the module can type-check code that assumes t is secretly a list.

Here we create an IntSet module with a type t representing sets of integers.

let s = IntSet.add 6 (IntSet.add 5 IntSet.empty) let b = IntSet.mem 6 s

By not including the definition of t in the signature, we hide the implementation of IntSet. This means that users of our set type cannot depend on the fact we have implemented it using lists.

Abstraction, enforced

let r = 4 :: s

Line 1, characters 13-14:
Error: This expression has type IntSet.t
       but an expression was expected of type int list

Type checking sees only the signature, never the hidden implementation.
The signature says type t with no equation, so IntSet.t and int list are unrelated types.
The implementation can switch to a tree later without breaking a single caller.

let r = 4 :: s

Line 1, characters 13-14:
Error: This expression has type IntSet.t
       but an expression was expected of type int list

Live demo: change the representation

The useful part of abstraction is not the error by itself; it is what the error makes possible. In the live session:

Run the IntSet implementation and its client.
Show that 4 :: s is rejected.
Replace only the implementation with the version below, then rerun the unchanged client.

Live demo: let's swap the implementation

The signature INT_SET remains in place, the implementationIntSet needs to be changed:

module IntSet : INT_SET = struct type t = int list let empty = [] let mem i s = List.mem i s let add i s = if mem i s then s else i :: s end

Now rerunning:

let s = IntSet.add 6 (IntSet.add 5 IntSet.empty) let b = IntSet.mem 6 s

The client still works because it depended on INT_SET, not on the hidden list representation.

Types with hidden definitions, like t above, are called abstract types. OCaml's support for abstraction is one of its most important and powerful features.

The INT_SET interface has no way to ask how many elements a set holds. Below is a COUNTED_SET signature that adds one, size, and an implementation with empty, mem, and add already filled in — complete size (the tests only ever call IntSet2.empty, .add, and .size, never anything about how t is represented).

module type COUNTED_SET = sig type t val empty : t val mem : int -> t -> bool val add : int -> t -> t val size : t -> int end module IntSet2 : COUNTED_SET = struct type t = int list let empty = [] let mem i s = List.mem i s let add i s = if mem i s then s else i :: s let size s = failwith "not implemented" end

Show reference solution

Inside the module, t is still just int list, so size can use the concrete representation directly — abstraction only stops callers from doing that, not the module itself.

let size s = List.length s

Signatures for files

To add a signature to the module represented by a file we add an interface file. For example, if a file called foo.ml defines a structure called Foo then foo.mli defines the signature of Foo. Corresponding to the list.ml in the OCaml standard library, we have list.mli which describes the signature of the list interface.

Signatures for files

A file foo.ml gets its signature from foo.mli.
The .mli lists what the file publishes; everything else stays private to foo.ml.
The standard library works this way: list.ml is the implementation, list.mli the interface you read.