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
.
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, 'cmp) t ‑> ('elt, 'cmp) t ‑> 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, 'cmp) t ‑> ('a, 'cmp) Comparator.t
val empty : ('a, 'cmp) comparator ‑> ('a, 'cmp) t
Creates an empty set based on the provided comparator.
val singleton : ('a, 'cmp) comparator ‑> 'a ‑> ('a, 'cmp) t
Creates a set based on the provided comparator that contains only the provided element.
val union_list : ('a, 'cmp) comparator ‑> ('a, 'cmp) t Core_kernel__.Import.list ‑> ('a, 'cmp) t
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.
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, '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 ‑> 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, 'cmp) t 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, 'cmp) t ‑> ('a, 'cmp) t ‑> 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 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 find_index : ('a, _) t ‑> Core_kernel__.Import.int ‑> 'a Core_kernel__.Import.option
val remove_index : ('a, 'cmp) t ‑> Core_kernel__.Import.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 is_subset : ('a, 'cmp) t ‑> of_:('a, 'cmp) t ‑> Core_kernel__.Import.bool
is_subset t1 ~of_:t2
returns true iff t1
is a subset of t2
.
val subset : ('a, 'cmp) t ‑> ('a, 'cmp) t ‑> Core_kernel__.Import.bool
subset
is a synonym for is_subset
.
module Named : sig ... end
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.
val of_list : ('a, 'cmp) comparator ‑> 'a Core_kernel__.Import.list ‑> ('a, 'cmp) t
The list or array given to of_list
and of_array
need not be sorted.
val of_array : ('a, 'cmp) comparator ‑> 'a Core_kernel__.Import.array ‑> ('a, 'cmp) t
val of_hash_set : ('a, 'cmp) comparator ‑> 'a Hash_set.t ‑> ('a, 'cmp) t
val of_hashtbl_keys : ('a, 'cmp) comparator ‑> ('a, _) Hashtbl.t ‑> ('a, 'cmp) t
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 of_tree : ('a, 'cmp) comparator ‑> ('a, 'cmp) Tree.t ‑> ('a, 'cmp) t
val of_sorted_array : ('a, 'cmp) comparator ‑> 'a Core_kernel__.Import.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 : ('a, 'cmp) comparator ‑> 'a Core_kernel__.Import.array ‑> ('a, 'cmp) t
Similar to of_sorted_array
, but without checking the input array.
val of_increasing_iterator_unchecked : ('a, 'cmp) comparator ‑> len:Core_kernel__.Import.int ‑> f:(Core_kernel__.Import.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.
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, 'cmp) comparator ‑> ('a, _) t ‑> f:('a ‑> 'b) ‑> ('b, 'cmp) t
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, 'cmp) comparator ‑> ('a, _) t ‑> f:('a ‑> 'b Core_kernel__.Import.option) ‑> ('b, 'cmp) t
Like map, except elements for which f
returns None
will be dropped.
val filter : ('a, 'cmp) t ‑> f:('a ‑> Core_kernel__.Import.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:'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, 'e) Result.t) ‑> ('accum, '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:'accum ‑> f:('accum ‑> 'a ‑> ('accum, 'final) Set_intf.Continue_or_stop.t) ‑> finish:('accum ‑> '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:'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, 'cmp) t ‑> ('a, 'cmp) t ‑> 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, 'cmp) t ‑> f:('a ‑> Core_kernel__.Import.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 min_elt : ('a, _) t ‑> 'a Core_kernel__.Import.option
Returns the smallest element of the set. O(log n)
.
val max_elt : ('a, _) t ‑> 'a Core_kernel__.Import.option
Returns the largest element of the set. O(log n)
.
val choose : ('a, _) t ‑> 'a Core_kernel__.Import.option
returns an arbitrary element, or None
if the set is empty.
val split : ('a, 'cmp) t ‑> 'a ‑> ('a, 'cmp) t * 'a Core_kernel__.Import.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 ‑> Core_kernel__.Import.bool) ‑> ('a, 'cmp) t 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, '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.
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, 'cmp) t ‑> ('a, 'cmp) t ‑> ('a, 'a) Merge_to_sequence_element.t Sequence.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 gen : ('key, 'cmp) comparator ‑> 'key Quickcheck.Generator.t ‑> ('key, 'cmp) t Quickcheck.Generator.t
val obs : 'key Quickcheck.Observer.t ‑> ('key, 'cmp) t Quickcheck.Observer.t
val shrinker : 'key Quickcheck.Shrinker.t ‑> ('key, 'cmp) t Quickcheck.Shrinker.t
Module Poly deals with sets that use OCaml's polymorphic comparison to compare elements.
Set
modulesmodule 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
.
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_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