Previous  Up  Next

Module Set

module 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 Map. See the documentation in core_map.mli for a description of the approach.

type ('elt, 'cmp) t 
module Tree: sig .. end
val invariants : ('a, 'b) t -> bool
Test if invariants of internal AVL search tree hold.
val comparator : ('a, 'cmp) t -> ('a, 'cmp) Comparator.t
val empty : comparator:('a, 'cmp) Comparator.t -> ('a, 'cmp) t
val singleton : comparator:('a, 'cmp) Comparator.t -> 'a -> ('a, 'cmp) t
val length : ('a, 'b) t -> int
val is_empty : ('a, 'b) t -> bool
val mem : ('a, 'b) t -> 'a -> bool
val add : ('a, 'cmp) t -> 'a -> ('a, 'cmp) t
val remove : ('a, 'cmp) t -> 'a -> ('a, 'cmp) t
val union : ('a, 'cmp) t -> ('a, 'cmp) t -> ('a, 'cmp) t
val union_list : comparator:('a, 'cmp) Comparator.t ->
       ('a, 'cmp) t list -> ('a, 'cmp) t
val inter : ('a, 'cmp) t -> ('a, 'cmp) t -> ('a, 'cmp) t
val diff : ('a, 'cmp) t -> ('a, 'cmp) t -> ('a, 'cmp) t
val compare_direct : ('a, 'cmp) t -> ('a, 'cmp) t -> int
val equal : ('a, 'cmp) t -> ('a, 'cmp) t -> bool
val exists : ('a, 'b) t -> f:('a -> bool) -> bool
val for_all : ('a, 'b) t -> f:('a -> bool) -> bool
val count : ('a, 'b) t -> f:('a -> bool) -> int
val find : ('a, 'b) t -> f:('a -> bool) -> 'a option
val find_map : ('a, 'c) t -> f:('a -> 'b option) -> 'b option
val find_exn : ('a, 'b) t -> f:('a -> bool) -> 'a
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.
val remove_index : ('a, 'cmp) t -> int -> ('a, 'cmp) 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
val filter_map : comparator:('b, 'cmp) Comparator.t ->
       ('a, 'c) t -> f:('a -> 'b option) -> ('b, 'cmp) t
val filter : ('a, 'cmp) t -> f:('a -> bool) -> ('a, 'cmp) t
val fold : ('a, 'b) t -> init:'accum -> f:('accum -> 'a -> 'accum) -> 'accum
val fold_until : ('a, 'b) t ->
       init:'accum ->
       f:('accum -> 'a -> [ `Continue of 'accum | `Stop of 'accum ]) -> 'accum
val fold_right : ('a, 'b) t -> init:'accum -> f:('a -> 'accum -> 'accum) -> 'accum
val iter : ('a, 'b) t -> f:('a -> unit) -> unit
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 Set.to_list.
val min_elt : ('a, 'b) t -> 'a option
val min_elt_exn : ('a, 'b) t -> 'a
val max_elt : ('a, 'b) t -> 'a option
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.
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.

module Poly: sig .. end 
  with type ('a, 'b) set := ('a, 'b) t
module type Elt = Core_set_intf.Elt
module type Elt_binable = Core_set_intf.Elt_binable
module type S = S0 
  with type ('a, 'b) set  := ('a, 'b) t 
  with type ('a, 'b) tree := ('a, 'b) Tree.t
module type S_binable = S0_binable 
  with type ('a, 'b) set  := ('a, 'b) t 
  with type ('a, 'b) tree := ('a, 'b) Tree.t
module Make: 
functor (Elt : Elt) -> S  with type Elt.t = Elt.t
module Make_using_comparator: 
functor (Elt : Comparator.S) -> S 
    with type Elt.t = Elt.t 
    with type Elt.comparator = Elt.comparator
module Make_binable: 
functor (Elt : Elt_binable) -> S_binable  with type Elt.t = Elt.t
module Make_binable_using_comparator: 
functor (Elt : Comparator.S_binable) -> S_binable 
    with type Elt.t = Elt.t 
    with type Elt.comparator = Elt.comparator
val compare : ('elt -> 'elt -> int) ->
       ('cmp -> 'cmp -> int) ->
       ('elt, 'cmp) t -> ('elt, 'cmp) t -> int

Test if invariants of internal AVL search tree hold.

find_index t i returns the ith smallest element of t in O(log n) time. The smallest element has i = 0.

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.

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 Set.to_list.

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

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.

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.