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, 'cmp) Base.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.
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 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
istrue
ifft
is empty.O(1)
.
val mem : ('a, _) t -> 'a -> Core_kernel__.Import.bool
mem t a
returnstrue
iffa
is int
.O(log n)
.
val add : ('a, 'cmp) t -> 'a -> ('a, 'cmp) t
add t a
returns a new set witha
added tot
, or returnst
ifmem t a
.O(log n)
.
val remove : ('a, 'cmp) t -> 'a -> ('a, 'cmp) t
remove t a
returns a new set witha
removed fromt
ifmem t a
, or returnst
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 : ('a, 'cmp) comparator -> ('a, 'cmp) t Core_kernel__.Import.list -> ('a, 'cmp) t
union c list
returns the union of all the sets inlist
. Thec
argument is required for the case wherelist
is empty.O(max(List.length list, n log n))
, wheren
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 setst1
andt2
.O(length t1 + length t2)
.
val diff : ('a, 'cmp) t -> ('a, 'cmp) t -> ('a, 'cmp) t
diff t1 t2
computes the set differencet1 - t2
, i.e., the set containing all elements int1
that are not int2
.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 betweent1
andt2
. It is intended to be efficient in the case wheret1
andt2
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 setst1
andt2
. It returns the same result ascompare
, 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 withcompare_direct
iffhash_fold_key
is compatible with(comparator s).compare
of the sets
being hashed.
val equal : ('a, 'cmp) t -> ('a, 'cmp) t -> Core_kernel__.Import.bool
equal t1 t2
returnstrue
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
returnstrue
iff there exists ana
int
for whichf a
.O(n)
, but returns as soon as it finds ana
for whichf a
.
val for_all : ('a, _) t -> f:('a -> Core_kernel__.Import.bool) -> Core_kernel__.Import.bool
for_all t ~f
returnstrue
iff for alla
int
,f a
.O(n)
, but returns as soon as it finds ana
for whichnot (f a)
.
val count : ('a, _) t -> f:('a -> Core_kernel__.Import.bool) -> Core_kernel__.Import.int
count t
returns the number of elements oft
for whichf
returnstrue
.O(n)
.
val sum : (module Set_intf.Container.Summable with type t = 'sum) -> ('a, _) t -> f:('a -> 'sum) -> 'sum
sum t
returns the sum off t
for eacht
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 oft
for whichf
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
returnsb
for somea
int
for whichf a = Some b
. If no sucha
exists, thenfind
returnsNone
.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 thei
th smallest element oft
, inO(log n)
time. The smallest element hasi = 0
. ReturnsNone
ifi < 0
ori >= length t
.
val remove_index : ('a, 'cmp) t -> Core_kernel__.Import.int -> ('a, 'cmp) t
remove_index t i
returns a version oft
with thei
th smallest element removed, inO(log n)
time. The smallest element hasi = 0
. Returnst
ifi < 0
ori >= length t
.
val is_subset : ('a, 'cmp) t -> of_:('a, 'cmp) t -> Core_kernel__.Import.bool
is_subset t1 ~of_:t2
returns true ifft1
is a subset oft2
.
val are_disjoint : ('a, 'cmp) t -> ('a, 'cmp) t -> Core_kernel__.Import.bool
are_disjoint t1 t2
returnstrue
iffis_empty (inter t1 t2)
, but is more efficient.
module Named : sig ... end
Named
allows the validation of subset and equality relationships between sets. ANamed.t
is a record of a set and a name, where the name is used in error messages, andNamed.is_subset
andNamed.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
andof_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
andto_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, 'cmp) t -> ('a, 'cmp) Tree.t
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 likeof_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 theList
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 ofComparator
and using the resultingstable_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 applyingf
to every element int
. The returned set is based on the providedc
.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 whichf
returnsNone
will be dropped.
val filter : ('a, 'cmp) t -> f:('a -> Core_kernel__.Import.bool) -> ('a, 'cmp) t
filter t ~f
returns the subset oft
for whichf
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 iff accum x
is anError _
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 offold
. Iff
returnsStop _
the computation ceases and results in that value. Iff
returnsContinue _
, 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
callsf
on every element oft
, 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)
wherem
andn
are the sizes of the two input sets. As an example, with the inputs0; 1
and1; 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
thena
is the elements on whichf
producedtrue
, andb
is the elements on whichf
producesfalse
.
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 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)
wheret1
is the set of elements strictly less thanx
,maybe_x
is the member (if any) oft
which compares equal tox
, andt2
is the set of elements strictly larger thanx
.
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, thengroup_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 useSet.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 sett
to a sequence of the elements betweengreater_or_equal_to
andless_or_equal_to
inclusive in the order indicated byorder
. Ifgreater_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 binary_search : ('a, 'cmp) t -> compare:('a -> 'key -> Core_kernel__.Import.int) -> [ `Last_strictly_less_than | `Last_less_than_or_equal_to | `Last_equal_to | `First_equal_to | `First_greater_than_or_equal_to | `First_strictly_greater_than ] -> 'key -> 'a Core_kernel__.Import.option
binary_search t ~compare which elt
returns the element int
specified bycompare
andwhich
, if one exists.t
must be sorted in increasing order according tocompare
, wherecompare
andelt
dividet
into three (possibly empty) segments:| < elt | = elt | > elt |
binary_search
returns an element on the boundary of segments as specified bywhich
. See the diagram below next to thewhich
variants.binary_search
does not check thatcompare
orderst
, and behavior is unspecified ifcompare
doesn't ordert
. Behavior is also unspecified ifcompare
mutatest
.
val binary_search_segmented : ('a, 'cmp) t -> segment_of:('a -> [ `Left | `Right ]) -> [ `Last_on_left | `First_on_right ] -> 'a Core_kernel__.Import.option
binary_search_segmented t ~segment_of which
takes asegment_of
function that dividest
into two (possibly empty) segments:| segment_of elt = `Left | segment_of elt = `Right |
binary_search_segmented
returns the element on the boundary of the segments as specified bywhich
:`Last_on_left
yields the last element of the left segment, while`First_on_right
yields the first element of the right segment. It returnsNone
if the segment is empty.binary_search_segmented
does not check thatsegment_of
segmentst
as in the diagram, and behavior is unspecified ifsegment_of
doesn't segmentt
. Behavior is also unspecified ifsegment_of
mutatest
.
module Merge_to_sequence_element : sig ... end
Produces the elements of the two sets between
greater_or_equal_to
andless_or_equal_to
inorder
, 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
val to_map : ('key, 'cmp) t -> f:('key -> 'data) -> ('key, 'data, 'cmp) Base.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 toto_map
runs in constant time).
val of_map_keys : ('key, _, 'cmp) Base.Map.t -> ('key, 'cmp) t
val quickcheck_generator : ('key, 'cmp) comparator -> 'key Quickcheck.Generator.t -> ('key, 'cmp) t Quickcheck.Generator.t
val quickcheck_observer : 'key Quickcheck.Observer.t -> ('key, 'cmp) t Quickcheck.Observer.t
val quickcheck_shrinker : 'key Quickcheck.Shrinker.t -> ('key, 'cmp) t Quickcheck.Shrinker.t
Polymorphic sets
Module Poly
deals with sets that use OCaml's polymorphic comparison to compare elements.
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 acompare
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
module Elt_bin_io = Set_intf.Elt_bin_io
include Set_intf.For_deriving with type ('a, 'b) t := ('a, 'b) t
include Base.Set.For_deriving
module type Sexp_of_m = sig ... end
module type M_of_sexp = sig ... end
module type Compare_m = sig ... end
module type Equal_m = sig ... end
module type Hash_fold_m = Base.Hasher.S
val sexp_of_m__t : (module Sexp_of_m with type t = 'elt) -> ('elt, 'cmp) t -> Base.Sexp.t
val m__t_of_sexp : (module M_of_sexp with type comparator_witness = 'cmp and type t = 'elt) -> Base.Sexp.t -> ('elt, 'cmp) t
val compare_m__t : (module Compare_m) -> ('elt, 'cmp) t -> ('elt, 'cmp) t -> int
val equal_m__t : (module Equal_m) -> ('elt, 'cmp) t -> ('elt, 'cmp) t -> bool
val hash_fold_m__t : (module Hash_fold_m with type t = 'elt) -> Base.Hash.state -> ('elt, 'a) t -> Base.Hash.state
val hash_m__t : (module Hash_fold_m with type t = 'elt) -> ('elt, 'a) t -> int
module M = Base.Set.M
val bin_shape_m__t : ('a, 'b) Set_intf.Elt_bin_io.t -> Bin_prot.Shape.t
val bin_size_m__t : ('a, 'b) Set_intf.Elt_bin_io.t -> ('a, 'b) t Bin_prot.Size.sizer
val bin_write_m__t : ('a, 'b) Set_intf.Elt_bin_io.t -> ('a, 'b) t Bin_prot.Write.writer
val bin_read_m__t : ('a, 'b) Set_intf.Elt_bin_io.t -> ('a, 'b) t Bin_prot.Read.reader
val __bin_read_m__t__ : ('a, 'b) Set_intf.Elt_bin_io.t -> (Core_kernel__.Import.int -> ('a, 'b) t) Bin_prot.Read.reader
module type Quickcheck_generator_m = sig ... end
module type Quickcheck_observer_m = sig ... end
module type Quickcheck_shrinker_m = sig ... end
val quickcheck_generator_m__t : (module Quickcheck_generator_m with type comparator_witness = 'cmp and type t = 'a) -> ('a, 'cmp) t Quickcheck.Generator.t
val quickcheck_observer_m__t : (module Quickcheck_observer_m with type comparator_witness = 'cmp and type t = 'a) -> ('a, 'cmp) t Quickcheck.Observer.t
val quickcheck_shrinker_m__t : (module Quickcheck_shrinker_m with type comparator_witness = 'cmp and type t = 'a) -> ('a, 'cmp) t Quickcheck.Shrinker.t
module Stable : sig ... end
The following types and functors may be used to define stable modules.