How do I use sets in OCaml?

Question

I want to write a function that, given a non-negative integer n, returns the power set of {1,...,n}. So I want to use the Set.S module as found here. But I can't seem to import it. When I run the following code:

open Set.S

let rec power_set n =
  if n = 0 then add empty empty else union (iter (add n s) power_set (n-1)) (power_set (n-1));;

let print_set s = SS.iter print_endline s;;

print_set (power_set 2)

I get the error:

File "countTopologies.ml", line 1, characters 5-10:
Error: Unbound module Set.S

Maybe I just don't have the Set.S module installed on my computer? (I've only done the bare bones needed to install OCaml). If this is the case, how would I get it?

Answer 1

The Set.S is a module type, not a module. You can open only modules. In fact, the module Set contains three elements:

• the module type OrderedType that denotes the type of modules that implement ordered types;
• the module type S that denotes the type of modules that implement Set data structures;
• the functor Make that takes a module of type OrderedType and returns a module of type S.

To get a set module you need to create it using the Set.Make functor. The functor has one parameter - the module for the set elements. In modern OCaml (4.08+) you can create a set module for integers as easy as,

module Ints = Set.Make(Int)

and then you can use like this,

let numbers = Ints.of_list [1;2;3] assert (Ints.mem 2 numbers)

For older versions of OCaml, which doesn't provide the Int module, or for non-standard (custom) types, you need to define your own module that implements the OrderedType interface, e.g.,

 module Int = struct 
   type t = int 
   (* use Pervasives compare *)
   let compare = compare
 end

 module Ints = Set.Make(Int)

You can also use non-standard libraries, like Janestreet's Core library, which provide sets out of box. The Core library has an Int module that is already charged with sets, maps, hashtables, so it can be accessed without any functors:

open Core.Std

let nil = Int.Set.empty

Or, in the modern (2018-2019) version of Janestreet Core or Base libraries, you can use polymorphic sets/maps, which require you to specify the module for keys only when a new set or map is created, e.g., like this

open Base (* or Core, or Core_kernel *)

let nil = Set.empty (module Int)
let one = Set.add nil 1
let two = Set.singleton (module Int) 2

Answer 2

You have to Make a set module from the Set functor.

module SI = Set.Make(struct type t = int let compare = compare end)

Then you can have a set of ints:

# let myset = SI.add 3 SI.empty;;
val myset : SI.t = <abstr>
# SI.elements myset;;
- : SI.elt list = [3]