Creators require a comparator argument to be passed in, whereas accessors use the comparator provided by the input set.
type(!'elt, !'cmp) t
The type of a set. The first type parameter identifies the type of the element, and the second identifies the comparator, which determines the comparison function that is used for ordering elements in this set. Many operations (e.g., union), require that they be passed sets with the same element type and the same comparator type.
val compare :
('a->'a-> int)->('b->'b-> int)->('a, 'b)t->('a, 'b)t->
int
union_list c list returns the union of all the sets in list. The comparator argument is required for the case where list is empty. O(max(List.length list, n log n)), where n is the sum of sizes of the input sets.
symmetric_diff t1 t2 returns a sequence of changes between t1 and t2. It is intended to be efficient in the case where t1 and t2 share a large amount of structure.
val compare_direct : ('a, 'cmp)t->('a, 'cmp)t-> int
compare_direct t1 t2 compares the sets t1 and t2. It returns the same result as compare, but unlike compare, doesn't require arguments to be passed in for the type parameters of the set. O(length t1 + length t2).
Hash function: a building block to use when hashing data structures containing sets in them. hash_fold_direct hash_fold_key is compatible with compare_direct iff hash_fold_key is compatible with (comparator s).compare of the set s being hashed.
find t f returns an element of t for which f returns true, with no guarantee as to which element is returned. O(n), but returns as soon as a suitable element is found.
val find_map : ('a, _)t->f:('a->'b option)->'b option
find_map t f returns b for some a in t for which f a = Some b. If no such a exists, then find returns None. O(n), but returns as soon as a suitable element is found.
remove_index t i returns a version of t with the ith smallest element removed, in O(log n) time. The smallest element has i = 0. Returns t if i < 0 or i >= length t.
val is_subset : ('a, 'cmp)t->of_:('a, 'cmp)t-> bool
is_subset t1 ~of_:t2 returns true iff t1 is a subset of t2.
val are_disjoint : ('a, 'cmp)t->('a, 'cmp)t-> bool
are_disjoint t1 t2 returns true iff is_empty (inter t1 t2), but is more efficient.
Named allows the validation of subset and equality relationships between sets. A Named.t is a record of a set and a name, where the name is used in error messages, and Named.is_subset and Named.equal validate subset and equality relationships respectively.
Create set from sorted array. The input must be sorted (either in ascending or descending order as given by the comparator) and contain no duplicates, otherwise the result is an error. The complexity of this function is O(n).
val of_sorted_array_unchecked :
('a, 'cmp)Comparator.Module.t->'a array->('a, 'cmp)t
Similar to of_sorted_array, but without checking the input array.
val of_increasing_iterator_unchecked :
('a, 'cmp)Comparator.Module.t->len:int ->f:(int ->'a)->('a, 'cmp)t
of_increasing_iterator_unchecked c ~len ~f behaves like of_sorted_array_unchecked c
(Array.init len ~f), with the additional restriction that a decreasing order is not supported. The advantage is not requiring you to allocate an intermediate array. f will be called with 0, 1, ... len - 1, in order.
stable_dedup_list is here rather than in the List module because the implementation relies crucially on sets, and because doing so allows one to avoid uses of polymorphic comparison by instantiating the functor at a different implementation of Comparator and using the resulting stable_dedup_list.
deprecated [since 2023-04] Use [List.stable_dedup] instead.
map c t ~f returns a new set created by applying f to every element in t. The returned set is based on the provided comparator. O(n log n).
val filter_map :
('b, 'cmp)Comparator.Module.t->('a, _)t->f:('a->'b option)->('b, 'cmp)t
Like map, except elements for which f returns None will be dropped.
val filter : ('a, 'cmp)t->f:('a-> bool)->('a, 'cmp)t
filter t ~f returns the subset of t for which f evaluates to true. O(n log
n).
val fold : ('a, _)t->init:'acc->f:('acc->'a->'acc)->'acc
fold t ~init ~f folds over the elements of the set from smallest to largest.
val fold_result :
('a, _)t->init:'acc->f:('acc->'a->('acc, 'e)Result.t)->('acc, 'e)Result.t
fold_result ~init ~f folds over the elements of the set from smallest to largest, short circuiting the fold if f accum x is an Error _
val fold_until :
('a, _)t->init:'acc->f:('acc->'a->('acc, 'final)Container.Continue_or_stop.t)->finish:('acc->'final)->'final
fold_until t ~init ~f is a short-circuiting version of fold. If f returns Stop _ the computation ceases and results in that value. If f returns Continue _, the fold will proceed.
val fold_right : ('a, _)t->init:'acc->f:('a->'acc->'acc)->'acc
Like fold, except that it goes from the largest to the smallest element.
iter t ~f calls f on every element of t, going in order from the smallest to largest.
val iter2 :
('a, 'cmp)t->('a, 'cmp)t->f:([ `Left of 'a| `Right of 'a| `Both of 'a * 'a ]-> unit)->
unit
Iterate two sets side by side. Complexity is O(m+n) where m and n are the sizes of the two input sets. As an example, with the inputs 0; 1 and 1; 2, f will be called with `Left 0; `Both (1, 1); and `Right 2.
val partition_tf :
('a, 'cmp)t->f:('a-> bool)->('a, 'cmp)t * ('a, 'cmp)t
if a, b = partition_tf set ~f then a is the elements on which f produced true, and b is the elements on which f produces false.
Like choose, but throws an exception on an empty set.
val split : ('a, 'cmp)t->'a->('a, 'cmp)t * 'a option * ('a, 'cmp)t
split t x produces a triple (t1, maybe_x, t2).
t1 is the set of elements strictly less than x, maybe_x is the member (if any) of t which compares equal to x, t2 is the set of elements strictly larger than x.
val split_le_gt : ('a, 'cmp)t->'a->('a, 'cmp)t * ('a, 'cmp)t
split_le_gt t x produces a pair (t1, t2).
t1 is the set of elements less than or equal to x, t2 is the set of elements strictly greater than x.
val split_lt_ge : ('a, 'cmp)t->'a->('a, 'cmp)t * ('a, 'cmp)t
split_lt_ge t x produces a pair (t1, t2).
t1 is the set of elements strictly less than x, t2 is the set of elements greater than or equal to x.
val group_by : ('a, 'cmp)t->equiv:('a->'a-> bool)->('a, 'cmp)t list
if equiv is an equivalence predicate, then group_by set ~equiv produces a list of equivalence classes (i.e., a set-theoretic quotient). E.g.,
let chars = Set.of_list ['A'; 'a'; 'b'; 'c'] in
let equiv c c' = Char.equal (Char.uppercase c) (Char.uppercase c') in
group_by chars ~equiv
group_by runs in O(n^2) time, so if you have a comparison function, it's usually much faster to use Set.of_list.
val to_sequence :
?order:[ `Increasing | `Decreasing ]->?greater_or_equal_to:'a->?less_or_equal_to:'a->('a, 'cmp)t->'aSequence.t
to_sequence t converts the set t to a sequence of the elements between greater_or_equal_to and less_or_equal_to inclusive in the order indicated by order. If greater_or_equal_to > less_or_equal_to the sequence is empty. Cost is O(log n) up front and amortized O(1) for each element produced.
binary_search t ~compare which elt returns the element in t specified by compare and which, if one exists.
t must be sorted in increasing order according to compare, where compare and elt divide t into three (possibly empty) segments:
| < elt | = elt | > elt |
binary_search returns an element on the boundary of segments as specified by which. See the diagram below next to the which variants.
binary_search does not check that compare orders t, and behavior is unspecified if compare doesn't order t. Behavior is also unspecified if compare mutates t.
binary_search_segmented returns the element on the boundary of the segments as specified by which: `Last_on_left yields the last element of the left segment, while `First_on_right yields the first element of the right segment. It returns None if the segment is empty.
binary_search_segmented does not check that segment_of segments t as in the diagram, and behavior is unspecified if segment_of doesn't segment t. Behavior is also unspecified if segment_of mutates t.
Produces the elements of the two sets between greater_or_equal_to and less_or_equal_to in order, noting whether each element appears in the left set, the right set, or both. In the both case, both elements are returned, in case the caller can distinguish between elements that are equal to the sets' comparator. Runs in O(length t + length t').
Using comparator is a similar interface as the toplevel of Set, except the functions take a ~comparator:('elt, 'cmp) Comparator.t where the functions at the toplevel of Set takes a ('elt, 'cmp) comparator.