Sets

In addition to maps, Base also provides a set data type that’s designed along similar lines. In some sense, sets are little more than maps where you ignore the data. But while you could encode sets in terms of maps, it’s more natural, and more efficient, to use Base’s specialized set type. Here’s a simple example.  

Set.of_list (module Int) [1;2;3] |> Set.to_list;;
>- : int list = [1; 2; 3]
Set.union
  (Set.of_list (module Int) [1;2;3;2])
  (Set.of_list (module Int) [3;5;1])
|> Set.to_list;;
>- : int list = [1; 2; 3; 5]

In addition to the operators you would expect to have for maps, sets support the traditional set operations, including union, intersection, and set difference.

Modules and Comparators

It’s easy enough to create a map or set based on a type represented by a module in Base. Here, we’ll create a map from digits to their English names, based on digit_alist, which was defined earlier in the chapter.

let digit_map = Map.of_alist_exn (module Int) digit_alist;;
>val digit_map : (int, string, Int.comparator_witness) Map.t = <abstr>
Map.find digit_map 3;;
>- : string option = Some "three"

The function Map.of_alist_exn constructs a map from a provided association list, throwing an exception if a key is used more than once. Let’s take a look at the type signature of Map.of_alist_exn.

#show Map.of_alist_exn;;
>val of_alist_exn :
>  ('a, 'cmp) Set.comparator -> ('a * 'b) list -> ('a, 'b, 'cmp) Map.t

The type Map.comparator is actually an alias for a first-class module type, representing any module that matches the signature Comparator.S, shown below.

#show Base.Comparator.S;;
>module type S = Base.Comparator.S

Such a module must contain the type of the key itself, as well as the comparator_witness type, which serves as a type-level identifier of the comparison function in question, and finally, the concrete comparator itself, a value that contains the necessary comparison function.

Modules from Base like Int and String already satisfy this interface. But what if you want to satisfy this interface with a new module? Consider, for example, the following type representing a book, for which we’ve written a comparison function and an s-expression serializer.

module Book = struct

  type t = { title: string; isbn: string }

  let compare t1 t2 =
    let cmp_title = String.compare t1.title t2.title in
    if cmp_title <> 0 then cmp_title
    else String.compare t1.isbn t2.isbn

  let sexp_of_t t : Sexp.t =
    List [ Atom t.title; Atom t.isbn ]
end;;
>module Book :
>  sig
>    type t = { title : string; isbn : string; }
>    val compare : t -> t -> int
>    val sexp_of_t : t -> Sexp.t
>  end

This module has the basic functionality we need, but doesn’t satisfy the Comparator.S interface, so we can’t use it for creating a map, as you can see.

Map.empty (module Book);;
>Line 1, characters 19-23:
>Error: Signature mismatch:
>       ...
>       The type `comparator_witness' is required but not provided
>       File "duniverse/base/src/comparator.mli", line 18, characters 2-25:
>         Expected declaration
>       The value `comparator' is required but not provided
>       File "duniverse/base/src/comparator.mli", line 20, characters 2-53:
>         Expected declaration

In order to satisfy the interface, we need to use the Comparator.Make functor to extend the module. Here, we use a common idiom where we create a submodule, called T containing the basic functionality for the type in question, and then include both that module and the result of applying a functor to that module.  

module Book = struct
  module T = struct

    type t = { title: string; isbn: string }

    let compare t1 t2 =
      let cmp_title = String.compare t1.title t2.title in
      if cmp_title <> 0 then cmp_title
      else String.compare t1.isbn t2.isbn

    let sexp_of_t t : Sexp.t =
      List [ Atom t.title; Atom t.isbn ]

  end
  include T
  include Comparator.Make(T)
end;;

With this module in hand, we can now build a set of Book.t’s.

let some_programming_books =
  Set.of_list (module Book)
    [ { title = "Real World OCaml"
      ; isbn = "978-1449323912" }
    ; { title = "Structure and Interpretation of Computer Programs"
      ; isbn = "978-0262510875" }
    ; { title = "The C Programming Language"
      ; isbn = "978-0131101630" } ];;
>val some_programming_books : (Book.t, Book.comparator_witness) Set.t =
>  <abstr>

While we used Comparator.Make in the above, it’s often preferable to use Comparable.Make instead, since it provides extra helper functions, like infix comparison operators and min and max functions, in addition to the comparator itself.  

Why Do We Need Comparator Witnesses?

The comparator witness is quite different from other types that we’ve seen. Instead of tracking the kind of data being used, it’s used to single out a particular value, a comparison function. Why do we even need such a thing?

The comparator witness matters because some of the operations on maps and sets, in particular those that combine multiple maps or sets together, depend for their correctness on the fact that both objects being combined are ordered according to the same total order, which in turn is determined by the comparison function.

Consider, for example, Map.symmetric_diff, which computes the difference between two maps.

let left = Map.of_alist_exn (module String) ["foo",1; "bar",3; "snoo",0];;
>val left : (string, int, String.comparator_witness) Map.t = <abstr>
let right = Map.of_alist_exn (module String) ["foo",0; "snoo",0];;
>val right : (string, int, String.comparator_witness) Map.t = <abstr>
Map.symmetric_diff ~data_equal:Int.equal left right |> Sequence.to_list;;
>- : (string, int) Map.Symmetric_diff_element.t list =
>[("bar", `Left 3); ("foo", `Unequal (1, 0))]

As you can see below, the type of Map.symmetric_diff requires that the two maps it compares have the same comparator witness, in addition to the same key and value type.

#show Map.symmetric_diff;;
>val symmetric_diff :
>  ('k, 'v, 'cmp) Map.t ->
>  ('k, 'v, 'cmp) Map.t ->
>  data_equal:('v -> 'v -> bool) ->
>  ('k, 'v) Map.Symmetric_diff_element.t Sequence.t

Without this constraint, we could run Map.symmetric_diff on maps that are sorted in different orders, which could lead to garbled results.

To see this constraint in action, we’ll need to create two maps with the same key and data types, but different comparison functions. In the following, we do this by minting a new module Reverse, which represents strings sorted in the reverse of the usual lexicographic order.

module Reverse = struct
  module T = struct
    type t = string
    let sexp_of_t = String.sexp_of_t
    let t_of_sexp = String.t_of_sexp
    let compare x y = String.compare y x
  end
  include T
  include Comparator.Make(T)
end;;

As you can see in the following, both Reverse and String can be used to create maps with a key type of string:

let alist = ["foo", 0; "snoo", 3];;
>val alist : (string * int) list = [("foo", 0); ("snoo", 3)]
let ord_map = Map.of_alist_exn (module String) alist;;
>val ord_map : (string, int, String.comparator_witness) Map.t = <abstr>
let rev_map = Map.of_alist_exn (module Reverse) alist;;
>val rev_map : (string, int, Reverse.comparator_witness) Map.t = <abstr>

Map.min_elt returns the key and value for the smallest key in the map, which confirms that these two maps do indeed use different comparison functions.

Map.min_elt ord_map;;
>- : (string * int) option = Some ("foo", 0)
Map.min_elt rev_map;;
>- : (string * int) option = Some ("snoo", 3)

As a result, the algorithm in Map.symmetric_diff just wouldn’t work correctly when applied to these values. Happily, the type system will give us a compile-time error if we try, instead of throwing an error at run time, or worse, silently returning the wrong result.

Map.symmetric_diff ord_map rev_map;;
>Line 1, characters 28-35:
>Error: This expression has type
>         (string, int, Reverse.comparator_witness) Map.t
>       but an expression was expected of type
>         (string, int, String.comparator_witness) Map.t
>       Type Reverse.comparator_witness is not compatible with type
>         String.comparator_witness

The Polymorphic Comparator

We don’t need to generate specialized comparators for every type we want to build a map on. We can instead build a map based on OCaml’s built-in polymorphic comparison function, which was discussed in Chapter 3, Lists And Patterns.   

Map.Poly.of_alist_exn digit_alist;;
>- : (int, string) Map.Poly.t = <abstr>

Note that maps based on the polymorphic comparator have different comparator witnesses than those based on the type-specific comparison function. Thus, the compiler rejects the following:

Map.symmetric_diff
  (Map.Poly.singleton 3 "three")
  (Map.singleton (module Int) 3 "four" );;
>Line 3, characters 5-43:
>Error: This expression has type (int, string, Int.comparator_witness) Map.t
>       but an expression was expected of type
>         (int, string, Map.Poly.comparator_witness) Map.t
>       Type Int.comparator_witness is not compatible with type
>         Map.Poly.comparator_witness

This is rejected for good reason: there’s no guarantee that the comparator associated with a given type will order things in the same way that polymorphic compare does.

let m1 = Map.of_alist_exn (module Int) [1, "one";2, "two"];;
>val m1 : (int, string, Int.comparator_witness) Map.t = <abstr>
let m2 = Map.of_alist_exn (module Int) [2, "two";1, "one"];;
>val m2 : (int, string, Int.comparator_witness) Map.t = <abstr>

Map.equal String.equal m1 m2;;
>- : bool = true

Poly.(m1 = m2);;
>Exception: Invalid_argument "compare: functional value".

Poly.((Map.Using_comparator.to_tree m1) =
(Map.Using_comparator.to_tree m2));;
>- : bool = false

Satisfying Comparator.S with [@@deriving]

Using maps and sets on a new type requires satisfying the Comparator.S interface, which in turn requires s-expression converters and comparison functions for the type in question. Writing such functions by hand is annoying and error prone, but there’s a better way. Base comes along with a set of syntax extensions that automate these tasks away.

Let’s return to an example from earlier in the chapter, where we created a type Book.t and set it up for use in creating maps and sets.

module Book = struct
  module T = struct

    type t = { title: string; isbn: string }

    let compare t1 t2 =
      let cmp_title = String.compare t1.title t2.title in
      if cmp_title <> 0 then cmp_title
      else String.compare t1.isbn t2.isbn

    let sexp_of_t t : Sexp.t =
      List [ Atom t.title; Atom t.isbn ]

  end
  include T
  include Comparator.Make(T)
end

Much of the code here is devoted to creating a comparison function and s-expression converter for the type Book.t. But if we have the ppx_sexp_conv and ppx_compare syntax extensions enabled, then we can request that default implementations of these functions be created for us. We can enable both of these extensions via the omnibus ppx_jane package.            

#require "ppx_jane";;

And we can use the extensions in our definition of Book as follows:

module Book = struct
  module T = struct
    type t = { title: string; isbn: string }
    [@@deriving compare, sexp_of]
  end
  include T
  include Comparator.Make(T)
end;;

If you want a comparison function that orders things in a particular way, you can always write your own by hand; but if all you need is a total order suitable for creating maps and sets with, then [@@deriving compare] is a good choice.

1 = 2;;
>- : bool = false
"one" = "two";;
>Line 1, characters 1-6:
>Error: This expression has type string but an expression was expected of type
>         int

String.("one" = "two");;
>- : bool = false

ref 1 == ref 1;;
>Line 1, characters 7-9:
>Alert deprecated: Base.==
>[2016-09] this element comes from the stdlib distributed with OCaml.
>Use [phys_equal] instead.
>- : bool = false
phys_equal (ref 1) (ref 1);;
>- : bool = false

Applying [@@deriving] to Maps and Sets

In the previous section, we showed how to use [@@deriving] annotations to set up a type so it could be used to create a map or set type. But what if we want to put a [@@deriving] annotation on a map or set type itself?

type string_int_map =
  (string,int,String.comparator_witness) Map.t [@@deriving sexp];;
>Line 2, characters 44-49:
>Error: Unbound value Map.t_of_sexp
>Hint: Did you mean m__t_of_sexp?

This fails because there is no existing Map.t_of_sexp. This isn’t a simple omission; there’s no reasonable way to define a useful Map.t_of_sexp, because a comparator witness isn’t something that can be parsed out of the s-expression.

Happily, there’s another way of writing the type of a map that does work with the various [@@deriving] extensions, which you can see below.

type string_int_map = int Map.M(String).t [@@deriving sexp];;
>type string_int_map = int Base.Map.M(Base.String).t
>val string_int_map_of_sexp : Sexp.t -> string_int_map = <fun>
>val sexp_of_string_int_map : string_int_map -> Sexp.t = <fun>

Here, we use a functor, Map.M, to define the type we need. While this looks different than the ordinary type signature, the meaning of the type is the same, as we can see below.

let m = Map.singleton (module String) "one" 1;;
>val m : (string, int, String.comparator_witness) Map.t = <abstr>
(m : int Map.M(String).t);;
>- : int Base.Map.M(Base.String).t = <abstr>

This same type works with other derivers as well, like those for comparison and hash functions. Since this way of writing the type is also shorter, it’s what you should use most of the time.

Trees

As we’ve discussed, maps carry within them the comparator that they were created with. Sometimes, for space efficiency reasons, you want a version of the map data structure that doesn’t include the comparator. You can get such a representation with Map.Using_comparator.to_tree, which returns just the tree underlying the map, without the comparator.   

let ord_tree = Map.Using_comparator.to_tree ord_map;;
>val ord_tree :
>  (string, int, String.comparator_witness) Map.Using_comparator.Tree.t =
>  <abstr>

Even though the tree doesn’t physically include a comparator, it does include the comparator in its type. This is what is known as a phantom type, because it reflects something about the logic of the value in question, even though it doesn’t correspond to any values directly represented in the underlying physical structure of the value.

Since the comparator isn’t included in the tree, we need to provide the comparator explicitly when we, say, search for a key, as shown below:

Map.Using_comparator.Tree.find ~comparator:String.comparator ord_tree "snoo";;
>- : int option = Some 3

The algorithm of Map.Tree.find depends on the fact that it’s using the same comparator when looking up a value as you were when you stored it. That’s the invariant that the phantom type is there to enforce. As you can see in the following example, using the wrong comparator will lead to a type error:

Map.Using_comparator.Tree.find ~comparator:Reverse.comparator ord_tree "snoo";;
>Line 1, characters 63-71:
>Error: This expression has type
>         (string, int, String.comparator_witness) Map.Using_comparator.Tree.t
>       but an expression was expected of type
>         (string, int, Reverse.comparator_witness)
>         Map.Using_comparator.Tree.t
>       Type String.comparator_witness is not compatible with type
>         Reverse.comparator_witness

Collisions with the Polymorphic Hash Function

The polymorphic hash function, like polymorphic compare, has problems that derive from the fact that it doesn’t pay any attention to the type, just blindly walking down the structure of a data type and computing a hash from what it sees. That means that for data structures like maps and sets where equivalent instances can have different structures, it will do the wrong thing.

But there’s another problem with polymorphic hash, which is that it is prone to creating hash collisions. OCaml’s polymorphic hash function works by walking over the data structure it’s given using a breadth-first traversal that is bounded in the number of nodes it’s willing to traverse. By default, that bound is set at 10 “meaningful” nodes.  

The bound on the traversal means that the hash function may ignore part of the data structure, and this can lead to pathological cases where every value you store has the same hash value. We’ll demonstrate this below, using the function List.range to allocate lists of integers of different length:

Hashtbl.Poly.hashable.hash (List.range 0 9);;
>- : int = 209331808
Hashtbl.Poly.hashable.hash (List.range 0 10);;
>- : int = 182325193
Hashtbl.Poly.hashable.hash (List.range 0 11);;
>- : int = 182325193
Hashtbl.Poly.hashable.hash (List.range 0 100);;
>- : int = 182325193

As you can see, the hash function stops after the first 10 elements. The same can happen with any large data structure, including records and arrays. When building hash functions over large custom data structures, it is generally a good idea to write one’s own hash function, or to use the ones provided by [@@deriving], which don’t have this problem, as you can see below.

[%hash: int list] (List.range 0 9);;
>- : int = 999007935
[%hash: int list] (List.range 0 10);;
>- : int = 195154657
[%hash: int list] (List.range 0 11);;
>- : int = 527899773
[%hash: int list] (List.range 0 100);;
>- : int = 594983280

Note that rather than declaring a type and using [@@deriving hash] to invoke ppx_hash, we use [%hash], a shorthand for creating a hash function inline in an expression.