Module Set: sets over ordered types

This module implements the set data structure, given a total ordering
function over the set elements. All operations over sets
are purely applicative (no sideeffects).
The implementation uses balanced binary trees, and is therefore
reasonably efficient: insertion and membership take time
logarithmic in the size of the set, for instance.
module type OrderedType =
sig
type t
val compare: t > t > int
end

The input signature of the functor Set.Make.
t is the type of the set elements.
compare is a total ordering function over the set elements.
This is a twoargument function f such that
f e1 e2 is zero if the elements e1 and e2 are equal,
f e1 e2 is strictly negative if e1 is smaller than e2,
and f e1 e2 is strictly positive if e1 is greater than e2.
Example: a suitable ordering function is
the generic structural comparison function compare.
module type S =
sig
type elt

The type of the set elements.
type t

The type of sets.
val empty: t

The empty set.
val is_empty: t > bool

Test whether a set is empty or not.
val mem: elt > t > bool

mem x s tests whether x belongs to the set s.
val add: elt > t > t

add x s returns a set containing all elements of s,
plus x. If x was already in s, s is returned unchanged.
val remove: elt > t > t

remove x s returns a set containing all elements of s,
except x. If x was not in s, s is returned unchanged.
val union: t > t > t
val inter: t > t > t
val diff: t > t > t

Union, intersection and set difference.
val compare: t > t > int

Total ordering between sets. Can be used as the ordering function
for doing sets of sets.
val equal: t > t > bool

equal s1 s2 tests whether the sets s1 and s2 are
equal, that is, contain the same elements.
val subset: t > t > bool

subset s1 s2 tests whether the set s1 is a subset of
the set s2.
val iter: (elt > unit) > t > unit

iter f s applies f in turn to all elements of s.
The order in which the elements of s are presented to f
is unspecified.
val fold: (elt > 'a > 'a) > t > 'a > 'a

fold f s a computes (f xN ... (f x2 (f x1 a))...),
where x1 ... xN are the elements of s.
The order in which elements of s are presented to f is
unspecified.
val cardinal: t > int

Return the number of elements of a set.
val elements: t > elt list

Return the list of all elements of the given set.
The elements appear in the list in some unspecified order.
val choose: t > elt

Return one element of the given set, or raise Not_found if
the set is empty. Which element is chosen is unspecified,
but equal elements will be chosen for equal sets.
end
module Make(Ord: OrderedType): (S with type elt = Ord.t)

Functor building an implementation of the set structure
given a totally ordered type.