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 -> intReturns the number of elements in a set.
val cardinal : 'a t -> intReturns the number of elements in a set (same as size).
val empty : 'a tThe empty set.
val singleton : 'a -> 'a tsingleton 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.
val iter : ('a -> unit) -> 'a t -> unititer 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 -> unitrev_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 -> 'bfold 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 -> 'brev_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.
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.
val is_empty : 'a t -> boolTests whether a set is empty.
val for_all : ('a -> bool) -> 'a t -> boolfor_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 -> boolfor_all p s returns true if p a = true for some element a of the set s, and false otherwise.
val mem : 'a -> 'a t -> boolmem x s test whether the set s contains the element x.
val choose : 'a t -> 'aReturns 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 optionmin_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 optionmax_elt s returns Some x if x is the maximum element of s, or None if s is empty.
val to_list : 'a t -> 'a listReturns a list containing the elements of a set in increasing order.
val of_list : 'a list -> 'a tReturns a set containing the elements of a list.
val elements : 'a t -> 'a listReturns a list containing the elements of a set in increasing order (same as to_list).
module type OrderedType = sig ... endInput signature of the functor FSet.Make.