Module FSet

module FSet: sig .. end
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.

type +'a t
The type of finite sets over type 'a.
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

val equal : 'a t -> 'a t -> bool
Tests whether two sets contain the same elements.
val compare : 'a t -> 'a t -> int
Defines a total ordering on sets.
val subset : 'a t -> 'a t -> bool
subset s1 s2 tests whether s1 is a subset of the set s2.

Set construction

val empty : 'a t
The empty set.
val singleton : 'a -> 'a t
singleton x returns the one-element set containing only x.
val add : 'a -> 'a t -> 'a t
add x s returns the union of the set s and the one-element set containing only x.
val remove : 'a -> 'a t -> 'a t
remove x s returns the difference of the set s and the set containing only x.
val union : 'a t -> 'a t -> 'a t
union s1 s2 returns the union of the sets s1 and s2.
val inter : 'a t -> 'a t -> 'a t
inter s1 s2 returns the intersection of the sets s1 and s2.
val diff : 'a t -> 'a t -> 'a t
diff s1 s2 returns the difference of the sets s1 and s2.

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.
val map : ('a -> 'b) -> 'a t -> 'b t
map f s returns a set with elements f a1, ... f an, where a1, ..., an are the elements of the set s.

Filters

val filter : ('a -> bool) -> 'a t -> 'a t
filter p s returns a set containing all elements of the set s that satisfy the predicate p.
val partition : ('a -> bool) -> 'a t -> 'a t * 'a t
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.
val split : 'a -> 'a t -> 'a t * bool * 'a 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, 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.
module type S = sig .. end
Output signature of the functor FSet.Make.
module Make:
functor (Ord : OrderedType) -> S with type elt = Ord.t
Functor returning a finite set module over a totally ordered type.