Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

OCaml: Set modules

Tags:

I want to use OCaml to generates sets of data and make comparisons between them. I have seen the documentation for Module types like Set.OrderType, Set.Make, etc, but I can't figure out how to initialize a set or otherwise use them.

like image 781
Nick Heiner Avatar asked Sep 20 '09 22:09

Nick Heiner


2 Answers

Sets are defined using a functorial interface. For any given type, you have to create a Set module for that type using the Set.Make functor. An unfortunate oversight of the standard libraries is that they don't define Set instances for the built-in types. In most simple cases, it's sufficient to use Pervasives.compare. Here's a definition that works for int:

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

The module IntSet will implement the Set.S interface. Now you can operate on sets using the IntSet module:

let s = IntSet.empty ;;
let t = IntSet.add 1 s ;;
let u = IntSet.add 2 s ;;
let tu = IntSet.union t u ;;

Note that you don't have to explicitly define the input structure for Set.Make as an OrderedType; type inference will do the work for you. Alternatively, you could use the following definition:

module IntOrder : Set.OrderedType = struct
  type t = int
  let compare = Pervasives.compare
end

module IntSet = Set.Make( IntOrder )

This has the advantage that you can re-use the same module to instantiate a Map:

module IntMap = Map.Make( IntOrder )

You lose some genericity in using functors, because the type of the elements is fixed. For example, you won't be able to define a function that takes a Set of some arbitrary type and performs some operation on it. (Luckily, the Set module itself declares many useful operations on Sets.)

like image 146
Chris Conway Avatar answered Oct 13 '22 01:10

Chris Conway


In addition to Chris's answer, it may be useful to say that some standard library modules already adhere to the OrderedType signature. For example, you can simply do:

module StringSet = Set.Make(String) ;;       (* sets of strings *)
module Int64Set = Set.Make(Int64) ;;         (* sets of int64s *)
module StringSetSet = Set.Make(StringSet) ;; (* sets of sets of strings *)

And so on.

Here's a simple usage example for StringSet; remember that sets are functional data structures, so adding a new element to a set returns a new set:

let set = List.fold_right StringSet.add ["foo";"bar";"baz"] StringSet.empty ;;
StringSet.mem "bar" set ;; (* returns true *)
StringSet.mem "zzz" set ;; (* returns false *)
like image 27
Bruno De Fraine Avatar answered Oct 13 '22 01:10

Bruno De Fraine