package base

  1. Overview
  2. Docs
package base
Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source

Module Base.SetSource

Sets based on Comparator.S.

Creators require a comparator argument to be passed in, whereas accessors use the comparator provided by the input set.

Sourcetype ('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.

Sourceval compare : ('a -> 'a -> int) -> ('b -> 'b -> int) -> ('a, 'b) t -> ('a, 'b) t -> int
Sourcetype ('k, 'cmp) comparator = ('k, 'cmp) Comparator.Module.t
  • deprecated [since 2021-12] use [Comparator.Module.t] instead
Sourceval invariants : (_, _) t -> bool

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

Sourceval comparator_s : ('a, 'cmp) t -> ('a, 'cmp) Comparator.Module.t

Returns a first-class module that can be used to build other map/set/etc with the same notion of comparison.

Sourceval comparator : ('a, 'cmp) t -> ('a, 'cmp) Comparator.t
Sourceval empty : ('a, 'cmp) Comparator.Module.t -> ('a, 'cmp) t

Creates an empty set based on the provided comparator.

Sourceval singleton : ('a, 'cmp) Comparator.Module.t -> 'a -> ('a, 'cmp) t

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

Sourceval length : (_, _) t -> int

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

Sourceval is_empty : (_, _) t -> bool

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

Sourceval mem : ('a, _) t -> 'a -> bool

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

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

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

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

Sourceval union_list : ('a, 'cmp) Comparator.Module.t -> ('a, 'cmp) t list -> ('a, 'cmp) t

union c 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.

Sourceval inter : ('a, 'cmp) t -> ('a, 'cmp) t -> ('a, 'cmp) t

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

Sourceval 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(length t1 + length t2).

Sourceval 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.

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

Sourceval hash_fold_direct : 'a Hash.folder -> ('a, 'cmp) t 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.

Sourceval 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)

Sourceval exists : ('a, _) 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.

Sourceval for_all : ('a, _) 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).

Sourceval count : ('a, _) t -> f:('a -> bool) -> int

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

Sourceval sum : (module Container.Summable 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).

Sourceval find : ('a, _) 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.

Sourceval find_map : ('a, _) 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.

Sourceval find_exn : ('a, _) t -> f:('a -> bool) -> 'a

Like find, but throws an exception on failure.

Sourceval nth : ('a, _) t -> int -> 'a 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.

Sourceval 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.

Sourceval is_subset : ('a, 'cmp) t -> of_:('a, 'cmp) t -> bool

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

Sourceval are_disjoint : ('a, 'cmp) t -> ('a, 'cmp) t -> bool

are_disjoint t1 t2 returns true iff is_empty (inter t1 t2), but is more efficient.

Sourcemodule 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.

Sourceval of_list : ('a, 'cmp) Comparator.Module.t -> 'a list -> ('a, 'cmp) t

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

Sourceval of_sequence : ('a, 'cmp) Comparator.Module.t -> 'a Sequence.t -> ('a, 'cmp) t
Sourceval of_array : ('a, 'cmp) Comparator.Module.t -> 'a array -> ('a, 'cmp) t
Sourceval to_list : ('a, _) t -> 'a list

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

Sourceval to_array : ('a, _) t -> 'a array
Sourceval of_sorted_array : ('a, 'cmp) Comparator.Module.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).

Sourceval of_sorted_array_unchecked : ('a, 'cmp) Comparator.Module.t -> 'a array -> ('a, 'cmp) t

Similar to of_sorted_array, but without checking the input array.

Sourceval of_increasing_iterator_unchecked : ('a, 'cmp) Comparator.Module.t -> len:int -> f:(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.

Sourceval stable_dedup_list : ('a, _) Comparator.Module.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.

Sourceval map : ('b, 'cmp) Comparator.Module.t -> ('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 comparator. O(n log n).

Sourceval filter_map : ('b, 'cmp) Comparator.Module.t -> ('a, _) t -> f:('a -> 'b option) -> ('b, 'cmp) t

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

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

Sourceval 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.

Sourceval 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 _

Sourceval fold_until : ('a, _) t -> init:'accum -> f:('accum -> 'a -> ('accum, 'final) Container.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.

Sourceval fold_right : ('a, _) t -> init:'accum -> f:('a -> 'accum -> 'accum) -> 'accum

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

Sourceval iter : ('a, _) t -> f:('a -> unit) -> unit

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

Sourceval iter2 : ('a, 'cmp) t -> ('a, 'cmp) t -> f:([ `Left of 'a | `Right of 'a | `Both of 'a * '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.

Sourceval 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.

Sourceval elements : ('a, _) t -> 'a list

Same as to_list.

Sourceval min_elt : ('a, _) t -> 'a option

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

Sourceval min_elt_exn : ('a, _) t -> 'a

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

Sourceval max_elt : ('a, _) t -> 'a option

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

Sourceval max_elt_exn : ('a, _) t -> 'a

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

Sourceval choose : ('a, _) t -> 'a option

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

Sourceval choose_exn : ('a, _) t -> 'a

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

Sourceval 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.

Sourceval 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.

Sourceval 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.

binary_search t ~compare which elt returns the element in t specified by compare and which, if one exists.

t must be sorted in increasing order according to compare, where compare and elt divide t into three (possibly empty) segments:

  |  < elt  |  = elt  |  > elt  |

binary_search returns an element on the boundary of segments as specified by which. See the diagram below next to the which variants.

binary_search does not check that compare orders t, and behavior is unspecified if compare doesn't order t. Behavior is also unspecified if compare mutates t.

Sourceval binary_search_segmented : ('a, 'cmp) t -> segment_of:('a -> [ `Left | `Right ]) -> [ `Last_on_left | `First_on_right ] -> 'a option

binary_search_segmented t ~segment_of which takes a segment_of function that divides t 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 by which: `Last_on_left yields the last element of the left segment, while `First_on_right yields the first element of the right segment. It returns None if the segment is empty.

binary_search_segmented does not check that segment_of segments t as in the diagram, and behavior is unspecified if segment_of doesn't segment t. Behavior is also unspecified if segment_of mutates t.

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

Sourceval 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
Sourcemodule M (Elt : sig ... end) : sig ... end

M is meant to be used in combination with OCaml applicative functor types:

Sourcemodule type Sexp_of_m = sig ... end
Sourcemodule type M_of_sexp = sig ... end
Sourcemodule type M_sexp_grammar = sig ... end
Sourcemodule type Compare_m = sig ... end
Sourcemodule type Equal_m = sig ... end
Sourcemodule type Hash_fold_m = Hasher.S
Sourceval sexp_of_m__t : (module Sexp_of_m with type t = 'elt) -> ('elt, 'cmp) t -> Sexp.t
Sourceval m__t_of_sexp : (module M_of_sexp with type comparator_witness = 'cmp and type t = 'elt) -> Sexp.t -> ('elt, 'cmp) t
Sourceval m__t_sexp_grammar : (module M_sexp_grammar with type t = 'elt) -> ('elt, 'cmp) t Sexplib0.Sexp_grammar.t
Sourceval compare_m__t : (module Compare_m) -> ('elt, 'cmp) t -> ('elt, 'cmp) t -> int
Sourceval equal_m__t : (module Equal_m) -> ('elt, 'cmp) t -> ('elt, 'cmp) t -> bool
Sourceval hash_fold_m__t : (module Hash_fold_m with type t = 'elt) -> Hash.state -> ('elt, _) t -> Hash.state
Sourceval hash_m__t : (module Hash_fold_m with type t = 'elt) -> ('elt, _) t -> int
Sourcemodule Poly : sig ... end

A polymorphic Set.

Sourcemodule Using_comparator : sig ... end

Using comparator is a similar interface as the toplevel of Set, except the functions take a ~comparator:('elt, 'cmp) Comparator.t where the functions at the toplevel of Set takes a ('elt, 'cmp) comparator.

Modules and module types for extending Set

For use in extensions of Base, like Core.

Sourcemodule With_comparator : sig ... end
Sourcemodule With_first_class_module : sig ... end
Sourcemodule Without_comparator : sig ... end
Sourcemodule type For_deriving = sig ... end
Sourcemodule type S_poly = sig ... end
Sourcemodule type Accessors0 = sig ... end
Sourcemodule type Accessors1 = sig ... end
Sourcemodule type Accessors2 = sig ... end
Sourcemodule type Accessors2_with_comparator = sig ... end
Sourcemodule type Accessors_generic = sig ... end
Sourcemodule type Creators0 = sig ... end
Sourcemodule type Creators1 = sig ... end
Sourcemodule type Creators2 = sig ... end
Sourcemodule type Creators2_with_comparator = sig ... end
Sourcemodule type Creators_and_accessors0 = sig ... end
Sourcemodule type Creators_and_accessors1 = sig ... end
Sourcemodule type Creators_and_accessors2 = sig ... end
Sourcemodule type Creators_generic = sig ... end
Sourcemodule type Elt_plain = sig ... end
OCaml

Innovation. Community. Security.

GitHub Discord Twitter Peertube RSS
About
Changelog Releases Industrial Users Academic Users Why OCaml
Ecosystem
Packages Community Events OCaml Planet Jobs
Resources
Install OCaml Get Started Platform Tools Language Manual Standard Library API Books Exercises Papers OCaml Playground Logo
Policies
Carbon Footprint Governance Privacy Code of Conduct