This module defines the Set module for Core.Std. We use "core_set" as the file name rather than "set" to avoid conflicts with OCaml's standard set module.

This module uses the same organizational approach as Core_map. See the documentation in core_map.mli for a description of the approach.

Functions that construct a set take as an argument the comparator for the element type.

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.
module Tree : sig .. end
type ('a, 'cmp) t
A Tree.t contains just the tree data structure that a set is based on, without including the comparator. Accordingly, any operation on a Tree.t must also take as an argument the corresponding comparator.
include Core_set_intf.Creators_and_accessors2_with_comparator with type set := ('a, 'b) t with type t := ('a, 'b) t with type tree := ('a, 'b) t
val sexp_of_t : ('a -> Sexplib.Sexp.t) ->
('cmp -> Sexplib.Sexp.t) -> ('a, 'cmp) t -> Sexplib.Sexp.t
val invariants : ('a, 'b) t -> bool
Tests internal invariants of the set data structure. Returns true on success.
val comparator : ('a, 'cmp) t -> ('a, 'cmp) Comparator.t
val empty : comparator:('a, 'cmp) Comparator.t -> ('a, 'cmp) t
Creates an empty set based on the provided comparator.
val singleton : comparator:('a, 'cmp) Comparator.t -> 'a -> ('a, 'cmp) t
Creates a set based on the provided comparator that contains only the provided element.
val length : ('a, 'b) t -> int
Returns the number of elements in the set. O(1).
val is_empty : ('a, 'b) t -> bool
is_empty t is true iff t is empty. O(1).
val mem : ('a, 'b) t -> 'a -> bool
mem t a returns true iff a is in t. O(log n).
val add : ('a, 'cmp) t -> 'a -> ('a, 'cmp) t
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, 'cmp) t -> 'a -> ('a, 'cmp) t
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, 'cmp) t -> ('a, 'cmp) t -> ('a, 'cmp) t
union t1 t2 returns the union of the two sets. O(length t1 + length t2).
val union_list : comparator:('a, 'cmp) Comparator.t -> ('a, 'cmp) t list -> ('a, 'cmp) t
union ~comparator 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.
val inter : ('a, 'cmp) t -> ('a, 'cmp) t -> ('a, 'cmp) t
inter t1 t2 computes the intersection of sets t1 and t2. O(log(length t1) + log(length t2)).
val diff : ('a, 'cmp) t -> ('a, 'cmp) t -> ('a, 'cmp) t
diff t1 t2 computes the set difference t1 - t2, i.e., the set containing all elements in t1 that are not in t2. O(log(length t1) + log(length t2)).
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).
val equal : ('a, 'cmp) t -> ('a, 'cmp) t -> bool
equal t1 t2 returns true iff the two sets have the same elements. O(length t1 + length t2)
val exists : ('a, 'b) t -> f:('a -> bool) -> 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, 'b) t -> f:('a -> bool) -> 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, 'b) t -> f:('a -> bool) -> int
count t returns the number of elements of t for which f returns true. O(n).
val find : ('a, 'b) t -> f:('a -> bool) -> 'a 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, 'c) 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.
val find_exn : ('a, 'b) t -> f:('a -> bool) -> 'a
Like find, but throws an exception on failure.
val find_index : ('a, 'b) t -> int -> 'a option
find_index 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 remove_index : ('a, 'cmp) t -> int -> ('a, 'cmp) t
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 subset : ('a, 'cmp) t -> ('a, 'cmp) t -> bool
subset t1 t2 returns true iff t1 is a subset of t2.
val of_list : comparator:('a, 'cmp) Comparator.t -> 'a list -> ('a, 'cmp) t
The list or array given to of_list and of_array need not be sorted.
val of_array : comparator:('a, 'cmp) Comparator.t -> 'a array -> ('a, 'cmp) t
val to_list : ('a, 'b) t -> 'a list
to_list and to_array produce sequences sorted in ascending order according to the comparator.
val to_array : ('a, 'b) t -> 'a array
val to_tree : ('a, 'cmp) t -> ('a, 'cmp) Tree.t
val of_tree : comparator:('a, 'cmp) Comparator.t -> ('a, 'cmp) Tree.t -> ('a, 'cmp) t
val of_sorted_array : comparator:('a, 'cmp) Comparator.t -> 'a array -> ('a, 'cmp) t 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 : comparator:('a, 'cmp) Comparator.t -> 'a array -> ('a, 'cmp) t
Similar to of_sorted_array, but without checking the input array.
val stable_dedup_list : comparator:('a, 'b) Comparator.t -> 'a list -> 'a 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 : comparator:('b, 'cmp) Comparator.t ->
('a, 'c) t -> f:('a -> 'b) -> ('b, 'cmp) t
map ~comparator 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 : comparator:('b, 'cmp) Comparator.t ->
('a, 'c) 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, 'b) 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_until : ('a, 'b) t ->
init:'accum ->
f:('accum -> 'a -> [ `Continue of 'accum | `Stop of 'accum ]) -> 'accum
Like fold, except that it will terminate early, if f returns `Stop.
val fold_right : ('a, 'b) t -> init:'accum -> f:('a -> 'accum -> 'accum) -> 'accum
Like fold, except that it goes from the largest to the smallest element.
val iter : ('a, 'b) t -> f:('a -> unit) -> unit
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:([ `Both of 'a * 'a | `Left of 'a | `Right of '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.
val elements : ('a, 'b) t -> 'a list
Same as to_list.
val min_elt : ('a, 'b) t -> 'a option
Returns the smallest element of the set. O(log n).
Like min_elt, but throws an exception when given an empty set.
val min_elt_exn : ('a, 'b) t -> 'a
val max_elt : ('a, 'b) t -> 'a option
Returns the largest element of the set. O(log n).
Like max_elt, but throws an exception when given an empty set.
val max_elt_exn : ('a, 'b) t -> 'a
val choose : ('a, 'b) t -> 'a option
returns an arbitrary element, or None if the set is empty.
Like choose, but throws an exception on an empty set.
val choose_exn : ('a, 'b) t -> 'a
val split : ('a, 'cmp) t -> 'a -> ('a, 'cmp) t * bool * ('a, 'cmp) t
split t x produces a triple (t1, b, t2) where t1 is the set of elements strictly less than x, b = mem set x, and t2 is the set of elements strictly larger than 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

produces:

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

group_by runs in O(n^2) time.

Polymorphic sets

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

module Poly : sig .. end with type set := ('a, 'b) t
type ('a, 'b) set
module Tree : sig .. end
type 'elt t = ('elt, Comparator.Poly.comparator_witness) Tree.t
include Core_set_intf.Creators_and_accessors1 with type set := ('a, 'b) Tree.t with type t := 'elt t with type tree := 'elt t
val t_of_sexp : (Sexplib.Sexp.t -> 'elt) -> Sexplib.Sexp.t -> 'elt t
val sexp_of_t : ('elt -> Sexplib.Sexp.t) -> 'elt t -> Sexplib.Sexp.t
type 'elt t = ('elt, Comparator.Poly.comparator_witness) set
include Core_set_intf.Creators_and_accessors1 with type set := ('a, 'b) set with type t := 'elt t with type tree := 'elt Tree.t
val t_of_sexp : (Sexplib.Sexp.t -> 'elt) -> Sexplib.Sexp.t -> 'elt t
val sexp_of_t : ('elt -> Sexplib.Sexp.t) -> 'elt t -> Sexplib.Sexp.t
val compare : ('elt -> 'elt -> int) -> 'elt t -> 'elt t -> int
val bin_t : 'elt Bin_prot.Type_class.t -> 'elt t Bin_prot.Type_class.t
val bin_read_t : 'elt Bin_prot.Read.reader -> 'elt t Bin_prot.Read.reader
val __bin_read_t__ : 'elt Bin_prot.Read.reader -> (int -> 'elt t) Bin_prot.Read.reader
val bin_reader_t : 'elt Bin_prot.Type_class.reader -> 'elt t Bin_prot.Type_class.reader
val bin_size_t : 'elt Bin_prot.Size.sizer -> 'elt t Bin_prot.Size.sizer
val bin_write_t : 'elt Bin_prot.Write.writer -> 'elt t Bin_prot.Write.writer
val bin_writer_t : 'elt Bin_prot.Type_class.writer -> 'elt t Bin_prot.Type_class.writer

Signatures and functors for building Set modules

module type Elt = Core_set_intf.Elt
The signature that something needs to match in order to be used as a set element.
module type Elt_binable = Core_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 = Core_set_intf.S0 with type set := ('a, 'b) t with type tree := ('a, 'b) Tree.t
Module signature for a Set.
module type S_binable = Core_set_intf.S0_binable with type set := ('a, 'b) t with type tree := ('a, 'b) Tree.t
Module signature for a Set that supports bin_io.
module Make : 
functor (Elt : Elt) -> S 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.

Make_binable is similar, except the element and set types support bin_io.

module Make_binable : 
functor (Elt : Elt_binable) -> S_binable with type Elt.t = Elt.t
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.

Make_binable_using_comparator is similar, except the element and set types support bin_io.

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
val compare : ('elt -> 'elt -> int) ->
('cmp -> 'cmp -> int) -> ('elt, 'cmp) t -> ('elt, 'cmp) t -> int