19.26 |
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 side-effects).
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 two-argument 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 singleton: elt -> t
singleton x
returns the one-element set containing only x
.
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 equal 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