Module Core_kernel.Set

This module defines the Set module for Core. Functions that construct a set take as an argument the comparator for the element type.

This module uses the same organizational approach as Map.

type ('elt, 'cmp) t = ('elt'cmpBase.Set.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.

include sig ... end
val compare : ('elt ‑> 'elt ‑> Core_kernel__.Import.int) ‑> ('cmp ‑> 'cmp ‑> Core_kernel__.Import.int) ‑> ('elt'cmpt ‑> ('elt'cmpt ‑> Core_kernel__.Import.int
type ('k, 'cmp) comparator = (module Comparator.S with type comparator_witness = 'cmp and type t = 'k)
module Tree : sig ... end
module Using_comparator : sig ... end
val invariants : (__t ‑> Core_kernel__.Import.bool

Tests internal invariants of the set data structure. Returns true on success.

val comparator : ('a'cmpt ‑> ('a'cmpComparator.t
val empty : ('a'cmpcomparator ‑> ('a'cmpt

Creates an empty set based on the provided comparator.

val singleton : ('a'cmpcomparator ‑> 'a ‑> ('a'cmpt

Creates a set based on the provided comparator that contains only the provided element.

val length : (__t ‑> Core_kernel__.Import.int

Returns the cardinality of the set. O(1).

val is_empty : (__t ‑> Core_kernel__.Import.bool

is_empty t is true iff t is empty. O(1).

val mem : ('a_t ‑> 'a ‑> Core_kernel__.Import.bool

mem t a returns true iff a is in t. O(log n).

val add : ('a'cmpt ‑> 'a ‑> ('a'cmpt

add t a returns a new set with a added to t, or returns t if mem t a. O(log n).

val remove : ('a'cmpt ‑> 'a ‑> ('a'cmpt

remove t a returns a new set with a removed from t if mem t a, or returns t otherwise. O(log n).

val union : ('a'cmpt ‑> ('a'cmpt ‑> ('a'cmpt

union t1 t2 returns the union of the two sets. O(length t1 + length t2).

val union_list : ('a'cmpcomparator ‑> ('a'cmpt Core_kernel__.Import.list ‑> ('a'cmpt

union c list returns the union of all the sets in list. The c 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.

val inter : ('a'cmpt ‑> ('a'cmpt ‑> ('a'cmpt

inter t1 t2 computes the intersection of sets t1 and t2. O(length t1 + length t2).

val diff : ('a'cmpt ‑> ('a'cmpt ‑> ('a'cmpt

diff t1 t2 computes the set difference t1 - t2, i.e., the set containing all elements in t1 that are not in t2. O(length t1 + length t2).

val symmetric_diff : ('a'cmpt ‑> ('a'cmpt ‑> ('a'aEither.t Sequence.t

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'cmpt ‑> ('a'cmpt ‑> Core_kernel__.Import.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).

val hash_fold_direct : 'a Core_kernel__.Import.Hash.folder ‑> ('a'cmpt Core_kernel__.Import.Hash.folder

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.

val equal : ('a'cmpt ‑> ('a'cmpt ‑> Core_kernel__.Import.bool

equal t1 t2 returns true iff the two sets have the same elements. O(length t1 + length t2)

val exists : ('a_t ‑> f:('a ‑> Core_kernel__.Import.bool) ‑> Core_kernel__.Import.bool

exists t ~f returns true iff there exists an a in t for which f a. O(n), but returns as soon as it finds an a for which f a.

val for_all : ('a_t ‑> f:('a ‑> Core_kernel__.Import.bool) ‑> Core_kernel__.Import.bool

for_all t ~f returns true iff for all a in t, f a. O(n), but returns as soon as it finds an a for which not (f a).

val count : ('a_t ‑> f:('a ‑> Core_kernel__.Import.bool) ‑> Core_kernel__.Import.int

count t returns the number of elements of t for which f returns true. O(n).

val sum : (module Core_kernel__.Import.Commutative_group.S with type t = 'sum) ‑> ('a_t ‑> f:('a ‑> 'sum) ‑> 'sum

sum t returns the sum of f t for each t in the set. O(n).

val find : ('a_t ‑> f:('a ‑> Core_kernel__.Import.bool) ‑> 'a Core_kernel__.Import.option

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 Core_kernel__.Import.option) ‑> 'b Core_kernel__.Import.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.

val find_exn : ('a_t ‑> f:('a ‑> Core_kernel__.Import.bool) ‑> 'a

Like find, but throws an exception on failure.

val nth : ('a_t ‑> Core_kernel__.Import.int ‑> 'a Core_kernel__.Import.option

nth t i returns the ith smallest element of t, in O(log n) time. The smallest element has i = 0. Returns None if i < 0 or i >= length t.

val find_index : ('a_t ‑> Core_kernel__.Import.int ‑> 'a Core_kernel__.Import.option
val remove_index : ('a'cmpt ‑> Core_kernel__.Import.int ‑> ('a'cmpt

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'cmpt ‑> of_:('a'cmpt ‑> Core_kernel__.Import.bool

is_subset t1 ~of_:t2 returns true iff t1 is a subset of t2.

val subset : ('a'cmpt ‑> ('a'cmpt ‑> Core_kernel__.Import.bool

subset is a synonym for is_subset.

val of_list : ('a'cmpcomparator ‑> 'a Core_kernel__.Import.list ‑> ('a'cmpt

The list or array given to of_list and of_array need not be sorted.

val of_array : ('a'cmpcomparator ‑> 'a Core_kernel__.Import.array ‑> ('a'cmpt
val of_hash_set : ('a'cmpcomparator ‑> 'a Hash_set.t ‑> ('a'cmpt
val of_hashtbl_keys : ('a'cmpcomparator ‑> ('a_Hashtbl.t ‑> ('a'cmpt
val to_list : ('a_t ‑> 'a Core_kernel__.Import.list

to_list and to_array produce sequences sorted in ascending order according to the comparator.

val to_array : ('a_t ‑> 'a Core_kernel__.Import.array
val to_tree : ('a'cmpt ‑> ('a'cmpTree.t
val of_tree : ('a'cmpcomparator ‑> ('a'cmpTree.t ‑> ('a'cmpt
val of_sorted_array : ('a'cmpcomparator ‑> 'a Core_kernel__.Import.array ‑> ('a'cmpt Or_error.t

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'cmpcomparator ‑> 'a Core_kernel__.Import.array ‑> ('a'cmpt

Similar to of_sorted_array, but without checking the input array.

val of_increasing_iterator_unchecked : ('a'cmpcomparator ‑> len:Core_kernel__.Import.int ‑> f:(Core_kernel__.Import.int ‑> 'a) ‑> ('a'cmpt

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.

val stable_dedup_list : ('a_comparator ‑> 'a Core_kernel__.Import.list ‑> 'a Core_kernel__.Import.list

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.

val map : ('b'cmpcomparator ‑> ('a_t ‑> f:('a ‑> 'b) ‑> ('b'cmpt

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 c. O(n log n).

val filter_map : ('b'cmpcomparator ‑> ('a_t ‑> f:('a ‑> 'b Core_kernel__.Import.option) ‑> ('b'cmpt

Like map, except elements for which f returns None will be dropped.

val filter : ('a'cmpt ‑> f:('a ‑> Core_kernel__.Import.bool) ‑> ('a'cmpt

filter t ~f returns the subset of t for which f evaluates to true. O(n log n).

val fold : ('a_t ‑> init:'accum ‑> f:('accum ‑> 'a ‑> 'accum) ‑> 'accum

fold t ~init ~f folds over the elements of the set from smallest to largest.

val fold_result : ('a_t ‑> init:'accum ‑> f:('accum ‑> 'a ‑> ('accum'eResult.t) ‑> ('accum'eResult.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:'accum ‑> f:('accum ‑> 'a ‑> ('accum'stopSet_intf.Continue_or_stop.t) ‑> ('accum'stopSet_intf.Finished_or_stopped_early.t

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:'accum ‑> f:('a ‑> 'accum ‑> 'accum) ‑> 'accum

Like fold, except that it goes from the largest to the smallest element.

val iter : ('a_t ‑> f:('a ‑> Core_kernel__.Import.unit) ‑> Core_kernel__.Import.unit

iter t ~f calls f on every element of t, going in order from the smallest to largest.

val iter2 : ('a'cmpt ‑> ('a'cmpt ‑> f:([ `Left of 'a | `Right of 'a | `Both of 'a * 'a ] ‑> Core_kernel__.Import.unit) ‑> Core_kernel__.Import.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'cmpt ‑> f:('a ‑> Core_kernel__.Import.bool) ‑> ('a'cmpt * ('a'cmpt

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.

val elements : ('a_t ‑> 'a Core_kernel__.Import.list

Same as to_list.

val min_elt : ('a_t ‑> 'a Core_kernel__.Import.option

Returns the smallest element of the set. O(log n).

val min_elt_exn : ('a_t ‑> 'a

Like min_elt, but throws an exception when given an empty set.

val max_elt : ('a_t ‑> 'a Core_kernel__.Import.option

Returns the largest element of the set. O(log n).

val max_elt_exn : ('a_t ‑> 'a

Like max_elt, but throws an exception when given an empty set.

val choose : ('a_t ‑> 'a Core_kernel__.Import.option

returns an arbitrary element, or None if the set is empty.

val choose_exn : ('a_t ‑> 'a

Like choose, but throws an exception on an empty set.

val split : ('a'cmpt ‑> 'a ‑> ('a'cmpt * 'a Core_kernel__.Import.option * ('a'cmpt

split t x produces a triple (t1, maybe_x, t2) where t1 is the set of elements strictly less than x, maybe_x is the member (if any) of t which compares equal to x, and t2 is the set of elements strictly larger than x.

val group_by : ('a'cmpt ‑> equiv:('a ‑> 'a ‑> Core_kernel__.Import.bool) ‑> ('a'cmpt Core_kernel__.Import.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

produces:

      [Set.of_list ['A';'a']; Set.singleton 'b'; Set.singleton 'c']

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'cmpt ‑> 'a Sequence.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.

module Merge_to_sequence_element : sig ... end

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').

val merge_to_sequence : ?⁠order:[ `Increasing | `Decreasing ] ‑> ?⁠greater_or_equal_to:'a ‑> ?⁠less_or_equal_to:'a ‑> ('a'cmpt ‑> ('a'cmpt ‑> ('a'aMerge_to_sequence_element.t Sequence.t
val to_map : ('key'cmpt ‑> f:('key ‑> 'data) ‑> ('key'data'cmpMap.t

Convert a set to or from a map. to_map takes a function to produce data for each key. Both functions run in O(n) time (assuming the function passed to to_map runs in constant time).

val of_map_keys : ('key_'cmpMap.t ‑> ('key'cmpt
val gen : ('key'cmpcomparator ‑> 'key Quickcheck.Generator.t ‑> ('key'cmpt Quickcheck.Generator.t
val obs : 'key Quickcheck.Observer.t ‑> ('key'cmpt Quickcheck.Observer.t
val shrinker : 'key Quickcheck.Shrinker.t ‑> ('key'cmpt Quickcheck.Shrinker.t

Polymorphic sets

Module Poly deals with sets that use OCaml's polymorphic comparison to compare elements.

module Poly : sig ... end with type (a, b) set := (a, b) t

Signatures and functors for building Set modules

module type Elt_plain = Set_intf.Elt_plain
module type Elt = Set_intf.Elt

The signature that something needs to match in order to be used as a set element.

module type Elt_binable = Set_intf.Elt_binable

The signature that something needs to match in order to be used as a set element if the resulting set is going to support bin_io.

module type S_plain = Set_intf.S_plain

Module signature for a Set that doesn't support of_sexp.

module type S = Set_intf.S

Module signature for a Set.

module type S_binable = Set_intf.S_binable

Module signature for a Set that supports bin_io.

module Make_plain : functor (Elt : Elt_plain) -> S_plain with type Elt.t = Elt.t

Make builds a set from an element type that has a compare function but doesn't have a comparator. This generates a new comparator.

module Make : functor (Elt : Elt) -> S with type Elt.t = Elt.t
module Make_binable : functor (Elt : Elt_binable) -> S_binable with type Elt.t = Elt.t
module Make_plain_using_comparator : functor (Elt : sig ... end) -> S_plain with type Elt.t = Elt.t with type Elt.comparator_witness = Elt.comparator_witness
module Make_using_comparator : functor (Elt : sig ... end) -> S with type Elt.t = Elt.t with type Elt.comparator_witness = Elt.comparator_witness

Make_using_comparator builds a set from an element type that has a comparator.

module Make_binable_using_comparator : functor (Elt : sig ... end) -> S_binable with type Elt.t = Elt.t with type Elt.comparator_witness = Elt.comparator_witness
module Stable : sig ... end

The following types and functors may be used to define stable modules.