# Module Core_set

    module Core_set: sig .. end

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., `Core_set.union`), require that they be passed sets with the same element type and the same comparator type.

    module Tree: sig .. end

    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 symmetric_diff : ('a, 'cmp) t ->
           ('a, 'cmp) t -> ('a, 'a) Either.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, '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 sum : (module Commutative_group.S with type t = 'sum) ->
           ('a, 'b) t -> f:('a -> 'sum) -> 'sum

`sum t` returns the sum of `f t` for each `t` in the set. `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 `i`th 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 `i`th 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 `Core_set.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 `Core_set.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 `Core_set.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 `Core_set.to_list`.

    val min_elt : ('a, 'b) t -> 'a option

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

Like `Core_set.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 `Core_set.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 `Core_set.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 * 'a option * ('a, 'cmp) t

`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, '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, so if you have a comparison function, it's usually much faster to use `Set.of_list`.

    val to_sequence : ?order:[ `Decreasing | `Increasing ] ->
           ?greater_or_equal_to:'a ->
           ?less_or_equal_to:'a -> ('a, 'cmp) t -> '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.

    val to_map : ('key, 'cmp) t ->
           f:('key -> 'data) -> ('key, 'data, 'cmp) Core_set_intf.Map.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, 'a, 'cmp) Core_set_intf.Map.t -> ('key, 'cmp) 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 = 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 = S0
      with type ('a, 'b) set  := ('a, 'b) t
      with type ('a, 'b) tree := ('a, 'b) Tree.t

Module signature for a Set.

    module type S_binable = S0_binable
      with type ('a, 'b) set  := ('a, 'b) t
      with type ('a, 'b) 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.

    module Make_binable: functor (Elt : Elt_binable) -> S_binable  with type Elt.t = Elt.t

    module Make_using_comparator: functor (Elt : sig
    type t

    include Comparator.S

    val t_of_sexp : Sexplib.Sexp.t -> t
    val sexp_of_t : t -> Sexplib.Sexp.tend) -> 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
    type t

    include Comparator.S

    val t_of_sexp : Sexplib.Sexp.t -> t
    val sexp_of_t : t -> Sexplib.Sexp.t
    val bin_t : t Bin_prot.Type_class.t
    val bin_read_t : t Bin_prot.Read.reader
    val __bin_read_t__ : (int -> t) Bin_prot.Read.reader
    val bin_reader_t : t Bin_prot.Type_class.reader
    val bin_size_t : t Bin_prot.Size.sizer
    val bin_write_t : t Bin_prot.Write.writer
    val bin_writer_t : t Bin_prot.Type_class.writerend) -> 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

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.
Tests internal invariants of the set data structure. Returns true on success.
Creates an empty set based on the provided comparator.
Creates a set based on the provided comparator that contains only the provided element.
Returns the number of elements in the set. `O(1)`.
`is_empty t` is `true` iff `t` is empty. `O(1)`.
`mem t a` returns `true` iff `a` is in `t`. `O(log n)`.
`add t a` returns a new set with `a` added to `t`, or returns `t` if `mem t a`. `O(log n)`.
`remove t a` returns a new set with `a` removed from `t` if `mem t a`, or returns `t` otherwise. `O(log n)`.
`union t1 t2` returns the union of the two sets. `O(length t1 + length t2)`.
`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.
`inter t1 t2` computes the intersection of sets `t1` and `t2`. `O(log(length t1) + log(length t2))`.
`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))`.
`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.
`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)`.
`equal t1 t2` returns `true` iff the two sets have the same elements. `O(length t1 + length t2)`
`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`.
`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)`.
`count t` returns the number of elements of `t` for which `f` returns `true`. `O(n)`.
`sum t` returns the sum of `f t` for each `t` in the set. `O(n)`.
`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.
`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.
Like `find`, but throws an exception on failure.
`find_index t i` returns the `i`th smallest element of `t`, in `O(log n)` time. The smallest element has `i = 0`. Returns `None` if `i < 0` or `i >= length t`.
`remove_index t i` returns a version of `t` with the `i`th smallest element removed, in `O(log n)` time. The smallest element has `i = 0`. Returns `t` if `i < 0` or `i >= length t`.
`subset t1 t2` returns true iff `t1` is a subset of `t2`.
The list or array given to `of_list` and `of_array` need not be sorted.
`to_list` and `to_array` produce sequences sorted in ascending order according to the comparator.
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)`.
Similar to `of_sorted_array`, but without checking the input array.
`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`.
`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)`.
Like `Core_set.map`, except elements for which `f` returns `None` will be dropped.
`filter t ~f` returns the subset of `t` for which `f` evaluates to true. `O(n log n)`.
`fold t ~init ~f` folds over the elements of the set from smallest to largest.
Like `Core_set.fold`, except that it will terminate early, if `f` returns ``Stop`.
Like `Core_set.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.
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`.
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`.
Same as `Core_set.to_list`.
Returns the smallest element of the set. `O(log n)`.
Like `Core_set.min_elt`, but throws an exception when given an empty set.
Returns the largest element of the set. `O(log n)`.
Like `Core_set.max_elt`, but throws an exception when given an empty set.
returns an arbitrary element, or `None` if the set is empty.
Like `Core_set.choose`, but throws an exception on an empty set.
`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`.
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`.
`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.
default
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).

# Polymorphic sets

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

# Signatures and functors for building `Set` modules

The signature that something needs to match in order to be used as a set element.
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 signature for a Set.
Module signature for a Set that supports `bin_io`.
`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`.
`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`.