package TCSLib
Install
Dune Dependency
Authors
Maintainers
Sources
sha256=b894f4028d71c3cbaf466dd221faa6b09e563c1be92571e7a0fcbf59523b8e97
md5=b55c4bb13f694fc149c38ee91738d937
doc/TCSLib/FSet/index.html
Module FSet
Finite sets.
The FSet
module provides a purely functional finite set datastructure based on balanced binary trees. Most operations on single elements, for example inserting elements or testing membership, can be performed in time logarithmic in the size of the set.
This module provides a superset of the operations in the Set
module in the OCaml standard library, but with a polymorphic interface in addition to the standard functorial interface.
A set provided by this module requires a strict order on its set elements. When using the polymorphic interface, set elements are compared using the structural comparison operators (=)
and (<)
. For this reason, the polymorphic interface can only be used if semantic equality in the element type is equivalent to structural equality. This is not the case for 'a FSet.t
itself, which means that the polymorphic interface cannot be used for creating sets of sets.
val size : 'a t -> int
Returns the number of elements in a set.
val cardinal : 'a t -> int
Returns the number of elements in a set (same as size
).
Set comparison
Set construction
val empty : 'a t
The empty set.
val singleton : 'a -> 'a t
singleton x
returns the one-element set containing only x
.
add x s
returns the union of the set s
and the one-element set containing only x
.
remove x s
returns the difference of the set s
and the set containing only x
.
Iterators
val iter : ('a -> unit) -> 'a t -> unit
iter f s
applies f
to all elements of the set s
. The elements of s
are processed in increasing order.
val rev_iter : ('a -> unit) -> 'a t -> unit
rev_iter f s
applies f
to all elements of the set s
. The elements of s
are processed in decreasing order.
val fold : ('a -> 'b -> 'b) -> 'a t -> 'b -> 'b
fold f s a
returns (f an ... (f a2 (f a1 a)) ... )
, where a1
, ..., an
are the elements of s
in increasing order.
val rev_fold : ('a -> 'b -> 'b) -> 'a t -> 'b -> 'b
rev_fold f s a
returns (f a1 ... (f a(n-1) (f an a)) ... )
, where a1
, ..., an
are the elements of s
in increasing order.
map f s
returns a set with elements f a1
, ... f an
, where a1
, ..., an
are the elements of the set s
.
Filters
filter p s
returns a set containing all elements of the set s
that satisfy the predicate p
.
partition p s
returns a pair (s1, s2)
of sets, such that s1
contains the elements of s
that satisfy the predicate p
, and s2
contains the elements of s
that do not satisfy the predicate p
.
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
, and present
is true
if s
contains an element equal to x
and false
otherwise.
Scanning
val is_empty : 'a t -> bool
Tests whether a set is empty.
val for_all : ('a -> bool) -> 'a t -> bool
for_all p s
returns true
if p a = true
for all elements a
of the set s
, and false
otherwise.
val exists : ('a -> bool) -> 'a t -> bool
for_all p s
returns true if p a = true
for some element a
of the set s
, and false
otherwise.
Searching
val mem : 'a -> 'a t -> bool
mem x s
test whether the set s
contains the element x
.
val choose : 'a t -> 'a
Returns an element of a set. It is unspecified how the element is chosen, but equal elements will be chosen for equal sets.
val min_elt : 'a t -> 'a option
min_elt s
returns Some x
if x
is the minimum element of s
, or None
if s
is empty.
val max_elt : 'a t -> 'a option
max_elt s
returns Some x
if x
is the maximum element of s
, or None
if s
is empty.
Conversion
val to_list : 'a t -> 'a list
Returns a list containing the elements of a set in increasing order.
val of_list : 'a list -> 'a t
Returns a set containing the elements of a list.
val elements : 'a t -> 'a list
Returns a list containing the elements of a set in increasing order (same as to_list
).
module type OrderedType = sig ... end
Input signature of the functor FSet.Make
.