module Make: (Ord: OrderedType) => S with type elt = Ord.t;
Functor building an implementation of the set structure
given a totally ordered type.
type elt;
The type of the set elements.
type t;
The type of sets.
let empty: t;
The empty set.
let is_empty: t => bool;
Test whether a set is empty or not.
let mem: (elt, t) => bool;
mem x s
tests whether x
belongs to the set s
.
let 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.
let singleton: elt => t;
singleton x
returns the one-element set containing only x
.
let 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.
let union: (t, t) => t;
Set union.
let inter: (t, t) => t;
Set intersection.
let diff: (t, t) => t;
Set difference.
let compare: (t, t) => int;
Total ordering between sets. Can be used as the ordering function
for doing sets of sets.
let equal: (t, t) => bool;
equal s1 s2
tests whether the sets s1
and s2
are
equal, that is, contain equal elements.
let subset: (t, t) => bool;
subset s1 s2
tests whether the set s1
is a subset of
the set s2
.
let iter: (elt => unit, t) => unit;
iter f s
applies f
in turn to all elements of s
.
The elements of s
are presented to f
in increasing order
with respect to the ordering over the type of the elements.
let 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
, in increasing order.
let for_all: (elt => bool, t) => bool;
for_all p s
checks if all elements of the set
satisfy the predicate p
.
let exists: (elt => bool, t) => bool;
exists p s
checks if at least one element of
the set satisfies the predicate p
.
let filter: (elt => bool, t) => t;
filter p s
returns the set of all elements in s
that satisfy predicate p
.
let partition: (elt => bool, t) => (t, t);
partition p s
returns a pair of sets (s1, s2)
, where
s1
is the set of all the elements of s
that satisfy the
predicate p
, and s2
is the set of all the elements of
s
that do not satisfy p
.
let cardinal: t => int;
Return the number of elements of a set.
let elements: t => list(elt);
Return the list of all elements of the given set.
The returned list is sorted in increasing order with respect
to the ordering
Ord.compare
, where
Ord
is the argument
given to
Set.Make
.
let min_elt: t => elt;
Return the smallest element of the given set
(with respect to the Ord.compare
ordering), or raise
Not_found
if the set is empty.
let max_elt: t => elt;
Same as
Set.S.min_elt
, but returns the largest element of the
given set.
let 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.
let split: (elt, t) => (t, bool, t);
split x s
returns a triple (l, present, r)
, where
l
is the set of elements of s
that are
strictly less than x
;
r
is the set of elements of s
that are
strictly greater than x
;
present
is false
if s
contains no element equal to x
,
or true
if s
contains an element equal to x
.
let find: (elt, t) => elt;
find x s
returns the element of s
equal to x
(according
to Ord.compare
), or raise Not_found
if no such element
exists.
Since 4.01.0
let of_list: list(elt) => t;
of_list l
creates a set from a list of elements.
This is usually more efficient than folding add
over the list,
except perhaps for lists with many duplicated elements.
Since 4.02.0