.TH "Set.Make" 3o source: 2019-01-25 OCamldoc "OCaml library"
.SH NAME
Set.Make \- Functor building an implementation of the set structure given a totally ordered type.
.SH Module
Module   Set.Make
.SH Documentation
.sp
Module
.BI "Make"
 : 
.B functor (Ord : OrderedType) -> sig  end

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

.sp
.B "Parameters:"
.sp
"Ord"

.B Set.OrderedType





.sp
.sp
.I type elt 

.sp
The type of the set elements\&.

.sp
.I type t 

.sp
The type of sets\&.

.sp

.I val empty 
: 
.B t
.sp
The empty set\&.

.sp

.I val is_empty 
: 
.B t -> bool
.sp
Test whether a set is empty or not\&.

.sp

.I val mem 
: 
.B elt -> t -> bool
.sp

.B mem x s
tests whether 
.B x
belongs to the set 
.B s
\&.

.sp

.I val add 
: 
.B elt -> t -> t
.sp

.B add x s
returns a set containing all elements of 
.B s
,
plus 
.B x
\&. If 
.B x
was already in 
.B s
, 
.B s
is returned unchanged
(the result of the function is then physically equal to 
.B s
)\&.

.sp
.B "Before4.03"
Physical equality was not ensured\&.


.sp

.I val singleton 
: 
.B elt -> t
.sp

.B singleton x
returns the one\-element set containing only 
.B x
\&.

.sp

.I val remove 
: 
.B elt -> t -> t
.sp

.B remove x s
returns a set containing all elements of 
.B s
,
except 
.B x
\&. If 
.B x
was not in 
.B s
, 
.B s
is returned unchanged
(the result of the function is then physically equal to 
.B s
)\&.

.sp
.B "Before4.03"
Physical equality was not ensured\&.


.sp

.I val union 
: 
.B t -> t -> t
.sp
Set union\&.

.sp

.I val inter 
: 
.B t -> t -> t
.sp
Set intersection\&.

.sp

.I val diff 
: 
.B t -> t -> t
.sp
Set difference\&.

.sp

.I val compare 
: 
.B t -> t -> int
.sp
Total ordering between sets\&. Can be used as the ordering function
for doing sets of sets\&.

.sp

.I val equal 
: 
.B t -> t -> bool
.sp

.B equal s1 s2
tests whether the sets 
.B s1
and 
.B s2
are
equal, that is, contain equal elements\&.

.sp

.I val subset 
: 
.B t -> t -> bool
.sp

.B subset s1 s2
tests whether the set 
.B s1
is a subset of
the set 
.B s2
\&.

.sp

.I val iter 
: 
.B (elt -> unit) -> t -> unit
.sp

.B iter f s
applies 
.B f
in turn to all elements of 
.B s
\&.
The elements of 
.B s
are presented to 
.B f
in increasing order
with respect to the ordering over the type of the elements\&.

.sp

.I val map 
: 
.B (elt -> elt) -> t -> t
.sp

.B map f s
is the set whose elements are 
.B f a0
,
.B f a1
\&.\&.\&. 
.B f
.B         aN
, where 
.B a0
,
.B a1
\&.\&.\&.
.B aN
are the elements of 
.B s
\&.
.sp
The elements are passed to 
.B f
in increasing order
with respect to the ordering over the type of the elements\&.
.sp
If no element of 
.B s
is changed by 
.B f
, 
.B s
is returned
unchanged\&. (If each output of 
.B f
is physically equal to its
input, the returned set is physically equal to 
.B s
\&.)

.sp
.B "Since"
4.04.0

.sp

.I val fold 
: 
.B (elt -> 'a -> 'a) -> t -> 'a -> 'a
.sp

.B fold f s a
computes 
.B (f xN \&.\&.\&. (f x2 (f x1 a))\&.\&.\&.)
,
where 
.B x1 \&.\&.\&. xN
are the elements of 
.B s
, in increasing order\&.

.sp

.I val for_all 
: 
.B (elt -> bool) -> t -> bool
.sp

.B for_all p s
checks if all elements of the set
satisfy the predicate 
.B p
\&.

.sp

.I val exists 
: 
.B (elt -> bool) -> t -> bool
.sp

.B exists p s
checks if at least one element of
the set satisfies the predicate 
.B p
\&.

.sp

.I val filter 
: 
.B (elt -> bool) -> t -> t
.sp

.B filter p s
returns the set of all elements in 
.B s
that satisfy predicate 
.B p
\&. If 
.B p
satisfies every element in 
.B s
,
.B s
is returned unchanged (the result of the function is then
physically equal to 
.B s
)\&.

.sp
.B "Before4.03"
Physical equality was not ensured\&.


.sp

.I val partition 
: 
.B (elt -> bool) -> t -> t * t
.sp

.B partition p s
returns a pair of sets 
.B (s1, s2)
, where
.B s1
is the set of all the elements of 
.B s
that satisfy the
predicate 
.B p
, and 
.B s2
is the set of all the elements of
.B s
that do not satisfy 
.B p
\&.

.sp

.I val cardinal 
: 
.B t -> int
.sp
Return the number of elements of a set\&.

.sp

.I val elements 
: 
.B t -> elt list
.sp
Return the list of all elements of the given set\&.
The returned list is sorted in increasing order with respect
to the ordering 
.B Ord\&.compare
, where 
.B Ord
is the argument
given to 
.B Set\&.Make
\&.

.sp

.I val min_elt 
: 
.B t -> elt
.sp
Return the smallest element of the given set
(with respect to the 
.B Ord\&.compare
ordering), or raise
.B Not_found
if the set is empty\&.

.sp

.I val min_elt_opt 
: 
.B t -> elt option
.sp
Return the smallest element of the given set
(with respect to the 
.B Ord\&.compare
ordering), or 
.B None
if the set is empty\&.

.sp
.B "Since"
4.05

.sp

.I val max_elt 
: 
.B t -> elt
.sp
Same as 
.B Set\&.S\&.min_elt
, but returns the largest element of the
given set\&.

.sp

.I val max_elt_opt 
: 
.B t -> elt option
.sp
Same as 
.B Set\&.S\&.min_elt_opt
, but returns the largest element of the
given set\&.

.sp
.B "Since"
4.05

.sp

.I val choose 
: 
.B t -> elt
.sp
Return one element of the given set, or raise 
.B Not_found
if
the set is empty\&. Which element is chosen is unspecified,
but equal elements will be chosen for equal sets\&.

.sp

.I val choose_opt 
: 
.B t -> elt option
.sp
Return one element of the given set, or 
.B None
if
the set is empty\&. Which element is chosen is unspecified,
but equal elements will be chosen for equal sets\&.

.sp
.B "Since"
4.05

.sp

.I val split 
: 
.B elt -> t -> t * bool * t
.sp

.B split x s
returns a triple 
.B (l, present, r)
, where
.B l
is the set of elements of 
.B s
that are
strictly less than 
.B x
;
.B r
is the set of elements of 
.B s
that are
strictly greater than 
.B x
;
.B present
is 
.B false
if 
.B s
contains no element equal to 
.B x
,
or 
.B true
if 
.B s
contains an element equal to 
.B x
\&.

.sp

.I val find 
: 
.B elt -> t -> elt
.sp

.B find x s
returns the element of 
.B s
equal to 
.B x
(according
to 
.B Ord\&.compare
), or raise 
.B Not_found
if no such element
exists\&.

.sp
.B "Since"
4.01.0

.sp

.I val find_opt 
: 
.B elt -> t -> elt option
.sp

.B find_opt x s
returns the element of 
.B s
equal to 
.B x
(according
to 
.B Ord\&.compare
), or 
.B None
if no such element
exists\&.

.sp
.B "Since"
4.05

.sp

.I val find_first 
: 
.B (elt -> bool) -> t -> elt
.sp

.B find_first f s
, where 
.B f
is a monotonically increasing function,
returns the lowest element 
.B e
of 
.B s
such that 
.B f e
,
or raises 
.B Not_found
if no such element exists\&.
.sp
For example, 
.B find_first (fun e \-> Ord\&.compare e x >= 0) s
will return
the first element 
.B e
of 
.B s
where 
.B Ord\&.compare e x >= 0
(intuitively:
.B e >= x
), or raise 
.B Not_found
if 
.B x
is greater than any element of
.B s
\&.

.sp
.B "Since"
4.05

.sp

.I val find_first_opt 
: 
.B (elt -> bool) -> t -> elt option
.sp

.B find_first_opt f s
, where 
.B f
is a monotonically increasing function,
returns an option containing the lowest element 
.B e
of 
.B s
such that
.B f e
, or 
.B None
if no such element exists\&.

.sp
.B "Since"
4.05

.sp

.I val find_last 
: 
.B (elt -> bool) -> t -> elt
.sp

.B find_last f s
, where 
.B f
is a monotonically decreasing function,
returns the highest element 
.B e
of 
.B s
such that 
.B f e
,
or raises 
.B Not_found
if no such element exists\&.

.sp
.B "Since"
4.05

.sp

.I val find_last_opt 
: 
.B (elt -> bool) -> t -> elt option
.sp

.B find_last_opt f s
, where 
.B f
is a monotonically decreasing function,
returns an option containing the highest element 
.B e
of 
.B s
such that
.B f e
, or 
.B None
if no such element exists\&.

.sp
.B "Since"
4.05

.sp

.I val of_list 
: 
.B elt list -> t
.sp

.B of_list l
creates a set from a list of elements\&.
This is usually more efficient than folding 
.B add
over the list,
except perhaps for lists with many duplicated elements\&.

.sp
.B "Since"
4.02.0

.sp