Single-File Programs

We’ll start with an example: a utility that reads lines from stdin, computes a frequency count of the lines, and prints out the ten most frequent lines. We’ll start with a simple implementation, which we’ll save as the file freq.ml.   

This implementation will use two functions from the List.Assoc module, which provides utility functions for interacting with association lists, i.e., lists of key/value pairs. In particular, we use the function List.Assoc.find, which looks up a key in an association list; and List.Assoc.add, which adds a new binding to an association list, as shown here:     

open Base;;
let assoc = [("one", 1); ("two",2); ("three",3)];;
>val assoc : (string * int) list = [("one", 1); ("two", 2); ("three", 3)]
List.Assoc.find ~equal:String.equal assoc "two";;
>- : int option = Some 2
List.Assoc.add ~equal:String.equal assoc "four" 4;;
>- : (string, int) Base.List.Assoc.t =
>[("four", 4); ("one", 1); ("two", 2); ("three", 3)]
List.Assoc.add ~equal:String.equal assoc "two"  4;;
>- : (string, int) Base.List.Assoc.t = [("two", 4); ("one", 1); ("three", 3)]

Note that List.Assoc.add doesn’t modify the original list, but instead allocates a new list with the requisite key/value pair added.

Now we can write freq.ml.

open Base
open Stdio

let build_counts () =
  In_channel.fold_lines In_channel.stdin ~init:[] ~f:(fun counts line ->
      let count =
        match List.Assoc.find ~equal:String.equal counts line with
        | None -> 0
        | Some x -> x
      in
      List.Assoc.add ~equal:String.equal counts line (count + 1))

let () =
  build_counts ()
  |> List.sort ~compare:(fun (_, x) (_, y) -> Int.descending x y)
  |> (fun l -> List.take l 10)
  |> List.iter ~f:(fun (line, count) -> printf "%3d: %s\n" count line)

The function build_counts reads in lines from stdin, constructing from those lines an association list with the frequencies of each line. It does this by invoking In_channel.fold_lines (similar to the function List.fold described in Chapter 3, Lists And Patterns), which reads through the lines one by one, calling the provided fold function for each line to update the accumulator. That accumulator is initialized to the empty list.

With build_counts defined, we then call the function to build the association list, sort that list by frequency in descending order, grab the first 10 elements off the list, and then iterate over those 10 elements and print them to the screen. These operations are tied together using the |> operator described in Chapter 2, Variables And Functions.  

If we weren’t using Base or any other external libraries, we could build the executable like this:

ocamlopt freq.ml -o freq
>File "freq.ml", line 1, characters 5-9:
>1 | open Base
>         ^^^^
>Error: Unbound module Base
[2]

But as you can see, it fails because it can’t find Base and Stdio. We need a somewhat more complex invocation to get them linked in:    

ocamlfind ocamlopt -linkpkg -package base -package stdio freq.ml -o freq

This uses ocamlfind, a tool which itself invokes other parts of the OCaml toolchain (in this case, ocamlopt) with the appropriate flags to link in particular libraries and packages. Here, -package base is asking ocamlfind to link in the Base library; -linkpkg asks ocamlfind to link in the packages as is necessary for building an executable.  

While this works well enough for a one-file project, more complicated projects require a tool to orchestrate the build. One good tool for this task is dune. To invoke dune, you need to have two files: a dune-project file for the overall project, and a dune file that configures the particular directory. This is a single-directory project, so we’ll just have one of each, but more realistic projects will have one dune-project and many dune files.    

At its simplest, the dune-project just specifies the version of the dune configuration-language in use.

(lang dune 3.0)

We also need a dune file to declare the executable we want to build, along with the libraries it depends on.

(executable
  (name      freq)
  (libraries base stdio))

With that in place, we can invoke dune as follows.

dune build freq.exe

We can run the resulting executable, freq.exe, from the command line. Executables built with dune will be left in the _build/default directory, from which they can be invoked. The specific invocation below will count the words that come up in the file freq.ml itself.  

grep -Eo '[[:alpha:]]+' freq.ml | ./_build/default/freq.exe
>  5: line
>  5: List
>  5: counts
>  4: count
>  4: fun
>  4: x
>  4: equal
>  3: let
>  2: f
>  2: l

Conveniently, dune allows us to combine the building and running an executable into a single operation, which we can do using dune exec.

grep -Eo '[[:alpha:]]+' freq.ml | dune exec ./freq.exe
>  5: line
>  5: List
>  5: counts
>  4: count
>  4: fun
>  4: x
>  4: equal
>  3: let
>  2: f
>  2: l

We’ve really just scratched the surface of what can be done with dune. We’ll discuss dune in more detail in Chapter 21, The OCaml Platform.

Multifile Programs and Modules

Source files in OCaml are tied into the module system, with each file compiling down into a module whose name is derived from the name of the file. We’ve encountered modules before, such as when we used functions like find and add from the List.Assoc module. At its simplest, you can think of a module as a collection of definitions that are stored within a namespace.    

Let’s consider how we can use modules to refactor the implementation of freq.ml. Remember that the variable counts contains an association list representing the counts of the lines seen so far. But updating an association list takes time linear in the length of the list, meaning that the time complexity of processing a file is quadratic in the number of distinct lines in the file.

We can fix this problem by replacing association lists with a more efficient data structure. To do that, we’ll first factor out the key functionality into a separate module with an explicit interface. We can consider alternative (and more efficient) implementations once we have a clear interface to program against.

We’ll start by creating a file, counter.ml, that contains the logic for maintaining the association list used to represent the frequency counts. The key function, called touch, bumps the frequency count of a given line by one.

open Base

let touch counts line =
  let count =
    match List.Assoc.find ~equal:String.equal counts line with
    | None -> 0
    | Some x -> x
  in
  List.Assoc.add ~equal:String.equal counts line (count + 1)

The file counter.ml will be compiled into a module named Counter, where the name of the module is derived automatically from the filename. The module name is capitalized even if the file is not. Indeed, module names are always capitalized.  

We can now rewrite freq.ml to use Counter.

open Base
open Stdio

let build_counts () =
  In_channel.fold_lines In_channel.stdin ~init:[] ~f:Counter.touch

let () =
  build_counts ()
  |> List.sort ~compare:(fun (_, x) (_, y) -> Int.descending x y)
  |> (fun l -> List.take l 10)
  |> List.iter ~f:(fun (line, count) -> printf "%3d: %s\n" count line)

The resulting code can still be built with dune, which will discover dependencies and realize that counter.ml needs to be compiled.

dune build freq.exe

Signatures and Abstract Types

While we’ve pushed some of the logic to the Counter module, the code in freq.ml can still depend on the details of the implementation of Counter. Indeed, if you look at the definition of build_counts, you’ll see that it depends on the fact that the empty set of frequency counts is represented as an empty list. We’d like to prevent this kind of dependency, so we can change the implementation of Counter without needing to change client code like that in freq.ml.      

The implementation details of a module can be hidden by attaching an interface. (Note that in the context of OCaml, the terms interface, signature, and module type are all used interchangeably.) A module defined by a file filename.ml can be constrained by a signature placed in a file called filename.mli.  

For counter.mli, we’ll start by writing down an interface that describes what’s currently available in counter.ml, without hiding anything. val declarations are used to specify values in a signature. The syntax of a val declaration is as follows:

val <identifier> : <type>

Using this syntax, we can write the signature of counter.ml as follows.

open Base

(** Bump the frequency count for the given string. *)
val touch : (string * int) list -> string -> (string * int) list

Note that dune will detect the presence of the mli file automatically and include it in the build.

To hide the fact that frequency counts are represented as association lists, we’ll need to make the type of frequency counts abstract. A type is abstract if its name is exposed in the interface, but its definition is not. Here’s an abstract interface for Counter:

open Base

(** A collection of string frequency counts *)
type t

(** The empty set of frequency counts *)
val empty : t

(** Bump the frequency count for the given string. *)
val touch : t -> string -> t

(** Converts the set of frequency counts to an association list. A
    string shows up at most once, and the counts are >= 1. *)
val to_list : t -> (string * int) list

We added empty and to_list to Counter, since without them there would be no way to create a Counter.t or get data out of one.

We also used this opportunity to document the module. The mli file is the place where you specify your module’s interface, and as such is a natural place to put documentation. We started our comments with a double asterisk to cause them to be picked up by the odoc tool when generating API documentation. We’ll discuss odoc more in Chapter 21, The OCaml Platform.

Here’s a rewrite of counter.ml to match the new counter.mli:

open Base

type t = (string * int) list

let empty = []
let to_list x = x

let touch counts line =
  let count =
    match List.Assoc.find ~equal:String.equal counts line with
    | None -> 0
    | Some x -> x
  in
  List.Assoc.add ~equal:String.equal counts line (count + 1)

If we now try to compile freq.ml, we’ll get the following error:

dune build freq.exe
>File "freq.ml", line 5, characters 53-66:
>5 |   In_channel.fold_lines In_channel.stdin ~init:[] ~f:Counter.touch
>                                                         ^^^^^^^^^^^^^
>Error: This expression has type Counter.t -> Export.string -> Counter.t
>       but an expression was expected of type
>         'a list -> Export.string -> 'a list
>       Type Counter.t is not compatible with type 'a list
[1]

This is because freq.ml depends on the fact that frequency counts are represented as association lists, a fact that we’ve just hidden. We just need to fix build_counts to use Counter.empty instead of [] and to use Counter.to_list to convert the completed counts to an association list. The resulting implementation is shown below.

open Base
open Stdio

let build_counts () =
  In_channel.fold_lines
    In_channel.stdin
    ~init:Counter.empty
    ~f:Counter.touch

let () =
  build_counts ()
  |> Counter.to_list
  |> List.sort ~compare:(fun (_, x) (_, y) -> Int.descending x y)
  |> (fun counts -> List.take counts 10)
  |> List.iter ~f:(fun (line, count) -> printf "%3d: %s\n" count line)

With this implementation, the build now succeeds!

dune build freq.exe

Now we can turn to optimizing the implementation of Counter. Here’s an alternate and far more efficient implementation, based on Base’s Map data structure.

open Base

type t = int Map.M(String).t

let empty = Map.empty (module String)
let to_list t = Map.to_alist t

let touch t s =
  let count =
    match Map.find t s with
    | None -> 0
    | Some x -> x
  in
  Map.set t ~key:s ~data:(count + 1)

There’s some unfamiliar syntax in the above example, in particular the use of int Map.M(String).t to indicate the type of a map, and Map.empty (module String) to generate an empty map. Here, we’re making use of a more advanced feature of the language (specifically, functors and first-class modules, which we’ll get to in later chapters). The use of these features for the Map data-structure in particular is covered in Chapter 14, Maps And Hash Tables.

Concrete Types in Signatures

In our frequency-count example, the module Counter had an abstract type Counter.t for representing a collection of frequency counts. Sometimes, you’ll want to make a type in your interface concrete, by including the type definition in the interface.   

For example, imagine we wanted to add a function to Counter for returning the line with the median frequency count. If the number of lines is even, then there is no single median, and the function would return the lines before and after the median instead. We’ll use a custom type to represent the fact that there are two possible return values. Here’s a possible implementation:

type median =
  | Median of string
  | Before_and_after of string * string

let median t =
  let sorted_strings =
    List.sort (Map.to_alist t) ~compare:(fun (_, x) (_, y) ->
        Int.descending x y)
  in
  let len = List.length sorted_strings in
  if len = 0 then failwith "median: empty frequency count";
  let nth n = fst (List.nth_exn sorted_strings n) in
  if len % 2 = 1
  then Median (nth (len / 2))
  else Before_and_after (nth ((len / 2) - 1), nth (len / 2))

In the above, we use failwith to throw an exception for the case of the empty list. We’ll discuss exceptions more in Chapter 7, Error Handling. Note also that the function fst simply returns the first element of any two-tuple.

Now, to expose this usefully in the interface, we need to expose both the function and the type median with its definition. Note that values (of which functions are an example) and types have distinct namespaces, so there’s no name clash here. Adding the following two lines to counter.mli does the trick.

(** Represents the median computed from a set of strings. In the case
    where there is an even number of choices, the one before and after
    the median is returned. *)
type median =
  | Median of string
  | Before_and_after of string * string

val median : t -> median

The decision of whether a given type should be abstract or concrete is an important one. Abstract types give you more control over how values are created and accessed, and make it easier to enforce invariants beyond what is enforced by the type itself; concrete types let you expose more detail and structure to client code in a lightweight way. The right choice depends very much on the context.

Nested Modules

Up until now, we’ve only considered modules that correspond to files, like counter.ml. But modules (and module signatures) can be nested inside other modules. As a simple example, consider a program that needs to deal with multiple identifiers like usernames and hostnames. If you just represent these as strings, then it becomes easy to confuse one with the other.    

A better approach is to mint new abstract types for each identifier, where those types are under the covers just implemented as strings. That way, the type system will prevent you from confusing a username with a hostname, and if you do need to convert, you can do so using explicit conversions to and from the string type.

Here’s how you might create such an abstract type, within a submodule:  

open Base

module Username : sig
  type t

  val of_string : string -> t
  val to_string : t -> string
  val ( = ) : t -> t -> bool
end = struct
  type t = string

  let of_string x = x
  let to_string x = x
  let ( = ) = String.( = )
end

Note that the to_string and of_string functions above are implemented simply as the identity function, which means they have no runtime effect. They are there purely as part of the discipline that they enforce on the code through the type system. We also chose to put in an equality function, so you can check if two usernames match. In a real application, we might want more functionality, like the ability to hash and compare usernames, but we’ve kept this example purposefully simple.

The basic structure of a module declaration like this is:

module <name> : <signature> = <implementation>

We could have written this slightly differently, by giving the signature its own top-level module type declaration, making it possible to create multiple distinct types with the same underlying implementation in a lightweight way:

open Base
module Time = Core.Time

module type ID = sig
  type t

  val of_string : string -> t
  val to_string : t -> string
  val ( = ) : t -> t -> bool
end

module String_id = struct
  type t = string

  let of_string x = x
  let to_string x = x
  let ( = ) = String.( = )
end

module Username : ID = String_id
module Hostname : ID = String_id

type session_info =
  { user : Username.t
  ; host : Hostname.t
  ; when_started : Time.t
  }

let sessions_have_same_user s1 s2 = Username.( = ) s1.user s2.host

The preceding code has a bug: it compares the username in one session to the host in the other session, when it should be comparing the usernames in both cases. Because of how we defined our types, however, the compiler will flag this bug for us.

dune build session_info.exe
>File "session_info.ml", line 29, characters 59-66:
>29 | let sessions_have_same_user s1 s2 = Username.( = ) s1.user s2.host
>                                                                ^^^^^^^
>Error: This expression has type Hostname.t
>       but an expression was expected of type Username.t
[1]

This is a trivial example, but confusing different kinds of identifiers is a very real source of bugs, and the approach of minting abstract types for different classes of identifiers is an effective way of avoiding such issues.

Opening Modules

Most of the time, you refer to values and types within a module by using the module name as an explicit qualifier. For example, you write List.map to refer to the map function in the List module. Sometimes, though, you want to be able to refer to the contents of a module without this explicit qualification. That’s what the open statement is for.   

We’ve encountered open already, specifically where we’ve written open Base to get access to the standard definitions in the Base library. In general, opening a module adds the contents of that module to the environment that the compiler looks at to find the definition of various identifiers. Here’s an example:

module M = struct let foo = 3 end;;
>module M : sig val foo : int end
foo;;
>Line 1, characters 1-4:
>Error: Unbound value foo
open M;;
foo;;
>- : int = 3

Here’s some general advice on how to use open effectively.

let average x y =
  let open Int64 in
  (x + y) / of_int 2;;
>val average : int64 -> int64 -> int64 = <fun>

let average x y =
  Int64.((x + y) / of_int 2);;
>val average : int64 -> int64 -> int64 = <fun>

let print_median m =
  match m with
  | Counter.Median string -> printf "True median:\n   %s\n" string
  | Counter.Before_and_after (before, after) ->
    printf "Before and after median:\n   %s\n   %s\n" before after

let print_median m =
  let module C = Counter in
  match m with
  | C.Median string -> printf "True median:\n   %s\n" string
  | C.Before_and_after (before, after) ->
    printf "Before and after median:\n   %s\n   %s\n" before after

Including Modules

While opening a module affects the environment used to search for identifiers, including a module is a way of adding new identifiers to a module proper. Consider the following simple module for representing a range of integer values:   

module Interval = struct
  type t = | Interval of int * int
           | Empty

  let create low high =
    if high < low then Empty else Interval (low,high)
end;;
>module Interval :
>  sig type t = Interval of int * int | Empty val create : int -> int -> t end

We can use the include directive to create a new, extended version of the Interval module:

module Extended_interval = struct
  include Interval

  let contains t x =
    match t with
    | Empty -> false
    | Interval (low,high) -> x >= low && x <= high
end;;
>module Extended_interval :
>  sig
>    type t = Interval.t = Interval of int * int | Empty
>    val create : int -> int -> t
>    val contains : t -> int -> bool
>  end
Extended_interval.contains (Extended_interval.create 3 10) 4;;
>- : bool = true

The difference between include and open is that we’ve done more than change how identifiers are searched for: we’ve changed what’s in the module. If we’d used open, we’d have gotten a quite different result:

module Extended_interval = struct
  open Interval

  let contains t x =
    match t with
    | Empty -> false
    | Interval (low,high) -> x >= low && x <= high
end;;
>module Extended_interval :
>  sig val contains : Extended_interval.t -> int -> bool end
Extended_interval.contains (Extended_interval.create 3 10) 4;;
>Line 1, characters 29-53:
>Error: Unbound value Extended_interval.create

To consider a more realistic example, imagine you wanted to build an extended version of the Option module, where you’ve added some functionality not present in the module as distributed in Base. That’s a job for include.

open Base

(* The full contents of the option module *)
include Option

(* The new function we're going to add *)
let apply f_opt x =
  match f_opt with
  | None -> None
  | Some f -> Some (f x)

Now, how do we write an interface for this new module? It turns out that include works on signatures as well, so we can pull essentially the same trick to write our mli. The only issue is that we need to get our hands on the signature for the Option module. This can be done using module type of, which computes a signature from a module:

open Base

(* Include the interface of the option module from Base *)
include module type of Option

(* Signature of function we're adding *)
val apply : ('a -> 'b) t -> 'a -> 'b t

The order of declarations in the mli doesn’t need to match the order of declarations in the ml. The order of declarations in the ml mostly matters insofar as it affects which values are shadowed. If we wanted to replace a function in Option with a new function of the same name, the declaration of that function in the ml would have to come after the include Option declaration.

We can now use Ext_option as a replacement for Option. If we want to use Ext_option in preference to Option in our project, we can create a file of common definitions, which in this case we’ll call import.ml.

module Option = Ext_option

Then, by opening Import, we can shadow Base’s Option module with our extension.

open Base
open Import

let lookup_and_apply map key x = Option.apply (Map.find map key) x

Common Errors with Modules

When OCaml compiles a program with an ml and an mli, it will complain if it detects a mismatch between the two. Here are some of the common errors you’ll run into.

(** Bump the frequency count for the given string. *)
val touch : string -> t -> t

dune build freq.exe
>File "counter.ml", line 1:
>Error: The implementation counter.ml
>       does not match the interface .freq.eobjs/byte/dune__exe__Counter.cmi:
>       Values do not match:
>         val touch :
>           ('a, int, 'b) Base.Map.t -> 'a -> ('a, int, 'b) Base.Map.t
>       is not included in
>         val touch : string -> t -> t
>       The type ('a, int, 'b) Base.Map.t -> 'a -> ('a, int, 'b) Base.Map.t
>       is not compatible with the type string -> t -> t
>       Type ('a, int, 'b) Base.Map.t is not compatible with type string
>       File "counter.mli", line 16, characters 0-28: Expected declaration
>       File "counter.ml", line 8, characters 4-9: Actual declaration
[1]

(** Returns the frequency count for the given string *)
val count : t -> string -> int

dune build freq.exe
>File "counter.ml", line 1:
>Error: The implementation counter.ml
>       does not match the interface .freq.eobjs/byte/dune__exe__Counter.cmi:
>       The value `count' is required but not provided
>       File "counter.mli", line 15, characters 0-30: Expected declaration
[1]

(** Represents the median computed from a set of strings. In the case
    where there is an even number of choices, the one before and after
    the median is returned. *)
type median =
  | Before_and_after of string * string
  | Median of string

val median : t -> median

dune build freq.exe
>File "counter.ml", line 1:
>Error: The implementation counter.ml
>       does not match the interface .freq.eobjs/byte/dune__exe__Counter.cmi:
>       Type declarations do not match:
>         type median = Median of string | Before_and_after of string * string
>       is not included in
>         type median = Before_and_after of string * string | Median of string
>       Constructor Before_and_after has been moved from position 1 to 2.
>       File "counter.mli", lines 21-23, characters 0-20: Expected declaration
>       File "counter.ml", lines 17-19, characters 0-39: Actual declaration
[1]

let singleton l = Counter.touch Counter.empty

dune build freq.exe
>File "counter.ml", line 18, characters 18-31:
>18 | let singleton l = Counter.touch Counter.empty
>                       ^^^^^^^^^^^^^
>Error: The module Counter is an alias for module Dune__exe__Counter, which is the current compilation unit
[1]

let _build_counts = Freq.build_counts

dune build freq.exe
>Error: Dependency cycle between the following files:
>   _build/default/.freq.eobjs/freq.impl.all-deps
>-> _build/default/.freq.eobjs/counter.impl.all-deps
>-> _build/default/.freq.eobjs/freq.impl.all-deps
[1]

Designing with Modules

The module system is a key part of how an OCaml program is structured. As such, we’ll close this chapter with some advice on how to think about designing that structure effectively.