base
-
library base
-
module Base
-
module Applicative
-
module type Applicative_infix
-
module type Applicative_infix2
-
module type Applicative_infix3
-
module type Basic
-
module type Basic2
-
module type Basic2_using_map2
-
module type Basic3
-
module type Basic3_using_map2
-
module type Basic_using_map2
-
module Compose
-
argument 1-F
-
module Applicative_infix
-
-
argument 2-G
-
module Applicative_infix
-
-
module Applicative_infix
-
-
module type Let_syntax
-
module Let_syntax
-
module Let_syntax
-
-
module Open_on_rhs_intf
-
-
module type Let_syntax2
-
module Let_syntax
-
module Let_syntax
-
-
module Open_on_rhs_intf
-
-
module type Let_syntax3
-
module Let_syntax
-
module Let_syntax
-
-
module Open_on_rhs_intf
-
-
module Make
-
argument 1-X
-
module Applicative_infix
-
-
module Make2
-
argument 1-X
-
module Applicative_infix
-
-
module Make2_using_map2
-
argument 1-X
-
module Applicative_infix
-
-
module Make3
-
argument 1-X
-
module Applicative_infix
-
-
module Make3_using_map2
-
argument 1-X
-
module Applicative_infix
-
-
module Make_let_syntax
-
argument 1-X
-
argument 2-Intf
-
module Let_syntax
-
module Let_syntax
-
-
-
module Make_let_syntax2
-
argument 1-X
-
argument 2-Intf
-
module Let_syntax
-
module Let_syntax
-
-
-
module Make_let_syntax3
-
argument 1-X
-
argument 2-Intf
-
module Let_syntax
-
module Let_syntax
-
-
-
module Make_using_map2
-
argument 1-X
-
module Applicative_infix
-
-
module Of_monad
-
argument 1-M
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module Applicative_infix
-
-
module Of_monad2
-
argument 1-M
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module Applicative_infix
-
-
module Pair
-
argument 1-F
-
module Applicative_infix
-
-
argument 2-G
-
module Applicative_infix
-
-
module Applicative_infix
-
-
module type S
-
module Applicative_infix
-
-
module type S2
-
module Applicative_infix
-
-
module S2_to_S
-
argument 1-X
-
module Applicative_infix
-
-
module Applicative_infix
-
-
module S2_to_S3
-
argument 1-X
-
module Applicative_infix
-
-
module Applicative_infix
-
-
module type S3
-
module Applicative_infix
-
-
module S3_to_S2
-
argument 1-X
-
module Applicative_infix
-
-
module Applicative_infix
-
-
module S_to_S2
-
argument 1-X
-
module Applicative_infix
-
-
module Applicative_infix
-
-
-
module Array
-
module Avltree
-
module Binary_search
-
module Binary_searchable
-
module type Indexable
-
module type Indexable1
-
module type S
-
module type S1
-
-
module Blit
-
module Make
-
argument 1-Sequence
-
-
module Make1
-
argument 1-Sequence
-
-
module Make1_generic
-
argument 1-Sequence
-
-
module Make_distinct
-
module Make_to_string
-
argument 1-T
-
argument 2-To_bytes
-
-
module type S
-
module type S1
-
module type S1_distinct
-
module type S_distinct
-
module type S_to_string
-
module type Sequence
-
module type Sequence1
-
-
module Bool
-
module Non_short_circuiting
-
-
module Bytes
-
module From_string
-
module To_string
-
-
module Comparable
-
module Make_using_comparator
-
argument 1-T
-
-
module Polymorphic_compare
-
argument 1-T
-
-
module type S
-
module Validate_with_zero
-
argument 1-T
-
-
module Comparisons
-
module Container
-
module Continue_or_stop
-
module type Generic
-
module type Generic_phantom
-
module type S0
-
module type S0_phantom
-
module type S1
-
module type S1_phantom
-
module type S1_phantom_invariant
-
module type Summable
-
-
module Continue_or_stop
-
module Either
-
module First
-
module Applicative_infix
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module type Focused
-
module Applicative_infix
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module Second
-
module Applicative_infix
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
-
module Error
-
module Internal_repr
-
-
module Exn
-
module Export
-
module Field
-
module Fn
-
module Formatter
-
module Hashtbl
-
module type Accessors
-
module type For_deriving
-
module type M_of_sexp
-
module Merge_into_action
-
module type Multi
-
module Poly
-
module type S_poly
-
module type S_without_submodules
-
module type Sexp_of_m
-
-
module Identifiable
-
module Make_using_comparator
-
argument 1-M
-
-
module type S
-
module Indexed_container
-
module type S1
-
module Info
-
module Internal_repr
-
module type S
-
module Internal_repr
-
-
-
module Int
-
module Hex
-
module type Int_without_module_types
-
module O
-
module type Operators
-
module type Operators_unbounded
-
module type Round
-
module type S_unbounded
-
-
module Int63
-
module Hex
-
module O
-
module Overflow_exn
-
-
module Lazy
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
module T_unforcing
-
-
module Linked_queue
-
module List
-
module Assoc
-
module Infix
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
module Or_unequal_lengths
-
-
module Map
-
module type Accessors1
-
module type Accessors2
-
module type Accessors3
-
module type Accessors3_with_comparator
-
module type Accessors_generic
-
module type Compare_m
-
module Continue_or_stop
-
module type Creators1
-
module type Creators2
-
module type Creators3_with_comparator
-
module type Creators_and_accessors1
-
module type Creators_and_accessors2
-
module type Creators_and_accessors3_with_comparator
-
module type Creators_and_accessors_generic
-
module type Creators_generic
-
module type Equal_m
-
module Finished_or_unfinished
-
module type For_deriving
-
module type M_of_sexp
-
module Or_duplicate
-
module Poly
-
module type S_poly
-
module type Sexp_of_m
-
module Symmetric_diff_element
-
module Using_comparator
-
module Empty_without_value_restriction
-
argument 1-K
-
-
module Tree
-
-
module With_comparator
-
module With_first_class_module
-
module Without_comparator
-
-
module Maybe_bound
-
module Monad
-
module type Basic
-
module type Basic2
-
module type Basic3
-
module type Basic_indexed
-
module Ident
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module type Infix
-
module type Infix2
-
module type Infix3
-
module type Infix_indexed
-
module Make
-
argument 1-X
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module Make2
-
argument 1-X
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module Make3
-
argument 1-X
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module Make_indexed
-
argument 1-X
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module type S
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module type S2
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module type S3
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module type S_indexed
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module type S_without_syntax
-
module Monad_infix
-
-
module type Syntax
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
-
module type Syntax2
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
-
module type Syntax3
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
-
module type Syntax_indexed
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
-
-
module Nothing
-
module Option
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module Option_array
-
module Or_error
-
module Applicative_infix
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module Ordered_collection_common
-
module Private
-
-
module Poly
-
module Popcount
-
module Pretty_printer
-
module Register_pp
-
argument 1-M
-
-
module type S
-
module Printf
-
module Result
-
module Export
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module Sequence
-
module Expert
-
module Generator
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module Infix
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
module Step
-
-
module Set
-
module type Accessors0
-
module Named
-
-
module type Accessors1
-
module Named
-
-
module type Accessors2
-
module Named
-
-
module type Accessors2_with_comparator
-
module Named
-
-
module type Accessors_generic
-
module Named
-
-
module type Compare_m
-
module type Creators0
-
module type Creators1
-
module type Creators2
-
module type Creators2_with_comparator
-
module type Creators_and_accessors0
-
module Named
-
-
module type Creators_and_accessors1
-
module Named
-
-
module type Creators_and_accessors2
-
module Named
-
-
module type Creators_and_accessors2_with_comparator
-
module Named
-
-
module type Creators_generic
-
module type Elt_plain
-
module type Equal_m
-
module type For_deriving
-
module type M_of_sexp
-
module Merge_to_sequence_element
-
module Named
-
module type Sexp_of_m
-
module Using_comparator
-
module Empty_without_value_restriction
-
argument 1-Elt
-
-
module Named
-
-
module With_comparator
-
module With_first_class_module
-
module Without_comparator
-
-
module Sexp
-
module Private
-
module Raw_grammar
-
-
-
module Sexpable
-
module Of_sexpable
-
argument 1-Sexpable
-
argument 2-M
-
-
module Of_sexpable1
-
argument 1-Sexpable
-
argument 2-M
-
-
module Of_sexpable2
-
argument 1-Sexpable
-
argument 2-M
-
-
module Of_sexpable3
-
argument 1-Sexpable
-
argument 2-M
-
-
module Of_stringable
-
argument 1-M
-
-
module type S
-
module type S1
-
module type S2
-
module type S3
-
-
module Sign
-
module Sign_or_nan
-
module Source_code_position
-
module Staged
-
module String
-
module Caseless
-
module Escaping
-
module Search_pattern
-
-
module Stringable
-
module type S
-
-
module Sys
-
module type T1
-
module type T2
-
module type T3
-
module Type_equal
-
module type Injective
-
module type Injective2
-
module Uchar
-
module Uniform_array
-
module Unit
-
module Variant
-
module With_return
-
module Word_size
-
-
-
library base.base_internalhash_types
-
module Base_internalhash_types
-
-
library base.caml
-
module Caml
-
-
library base.md5
-
module Md5_lib
-
-
library base.shadow_stdlib
-
module Shadow_stdlib
-
module Or_duplicate : sig ... end
module Continue_or_stop : sig ... end
module Finished_or_unfinished : sig ... end
type ('k, 'cmp) comparator =
(module Comparator.S
with type comparator_witness = 'cmp
and type t = 'k)
val invariants : ( _, _, _ ) t -> bool
Test if the invariants of the internal AVL search tree hold.
val comparator_s : ( 'a, _, 'cmp ) t -> ( 'a, 'cmp ) comparator
Returns a first-class module that can be used to build other map/set/etc. with the same notion of comparison.
val comparator : ( 'a, _, 'cmp ) t -> ( 'a, 'cmp ) Comparator.t
val empty : ( 'a, 'cmp ) comparator -> ( 'a, 'b, 'cmp ) t
The empty map.
val singleton : ( 'a, 'cmp ) comparator -> 'a -> 'b -> ( 'a, 'b, 'cmp ) t
A map with one (key, data) pair.
val of_alist :
( 'a, 'cmp ) comparator ->
('a * 'b) list ->
[ `Ok of ( 'a, 'b, 'cmp ) t | `Duplicate_key of 'a ]
Creates a map from an association list with unique keys.
val of_alist_or_error :
( 'a, 'cmp ) comparator ->
('a * 'b) list ->
( 'a, 'b, 'cmp ) t Or_error.t
Creates a map from an association list with unique keys, returning an error if duplicate 'a
keys are found.
val of_alist_exn :
( 'a, 'cmp ) comparator ->
('a * 'b) list ->
( 'a, 'b, 'cmp ) t
Creates a map from an association list with unique keys, raising an exception if duplicate 'a
keys are found.
val of_alist_multi :
( 'a, 'cmp ) comparator ->
('a * 'b) list ->
( 'a, 'b list, 'cmp ) t
Creates a map from an association list with possibly repeated keys. The values in the map for a given key appear in the same order as they did in the association list.
val of_alist_fold :
( 'a, 'cmp ) comparator ->
('a * 'b) list ->
init:'c ->
f:( 'c -> 'b -> 'c ) ->
( 'a, 'c, 'cmp ) t
Combines an association list into a map, folding together bound values with common keys.
val of_alist_reduce :
( 'a, 'cmp ) comparator ->
('a * 'b) list ->
f:( 'b -> 'b -> 'b ) ->
( 'a, 'b, 'cmp ) t
Combines an association list into a map, reducing together bound values with common keys.
val of_iteri :
( 'a, 'cmp ) comparator ->
iteri:( f:( key:'a -> data:'b -> unit ) -> unit ) ->
[ `Ok of ( 'a, 'b, 'cmp ) t | `Duplicate_key of 'a ]
of_iteri ~iteri
behaves like of_alist
, except that instead of taking a concrete data structure, it takes an iteration function. For instance, to convert a string table into a map: of_iteri (module String) ~f:(Hashtbl.iteri table)
. It is faster than adding the elements one by one.
val of_sorted_array :
( 'a, 'cmp ) comparator ->
('a * 'b) array ->
( 'a, 'b, 'cmp ) t Or_error.t
Creates a map from a sorted array of key-data pairs. The input array must be sorted (either in ascending or descending order), as given by the relevant comparator, and must not contain duplicate keys. If either of these conditions does not hold, an error is returned.
val of_sorted_array_unchecked :
( 'a, 'cmp ) comparator ->
('a * 'b) array ->
( 'a, 'b, 'cmp ) t
Like of_sorted_array
except that it returns a map with broken invariants when an Error
would have been returned.
val of_increasing_iterator_unchecked :
( 'a, 'cmp ) comparator ->
len:int ->
f:( int -> 'a * 'b ) ->
( 'a, 'b, '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 of_increasing_sequence :
( 'k, 'cmp ) comparator ->
('k * 'v) Sequence.t ->
( 'k, 'v, 'cmp ) t Or_error.t
of_increasing_sequence c seq
behaves like of_sorted_array c (Sequence.to_array
seq)
, but does not allocate the intermediate array.
The sequence will be folded over once, and the additional time complexity is O(n).
val of_sequence :
( 'k, 'cmp ) comparator ->
('k * 'v) Sequence.t ->
[ `Ok of ( 'k, 'v, 'cmp ) t | `Duplicate_key of 'k ]
Creates a map from an association sequence with unique keys.
of_sequence c seq
behaves like of_alist c (Sequence.to_list seq)
but does not allocate the intermediate list.
If your sequence is increasing, use of_increasing_sequence
.
val of_sequence_or_error :
( 'a, 'cmp ) comparator ->
('a * 'b) Sequence.t ->
( 'a, 'b, 'cmp ) t Or_error.t
Creates a map from an association sequence with unique keys, returning an error if duplicate 'a
keys are found.
of_sequence_or_error c seq
behaves like of_alist_or_error c (Sequence.to_list seq)
but does not allocate the intermediate list.
val of_sequence_exn :
( 'a, 'cmp ) comparator ->
('a * 'b) Sequence.t ->
( 'a, 'b, 'cmp ) t
Creates a map from an association sequence with unique keys, raising an exception if duplicate 'a
keys are found.
of_sequence_exn c seq
behaves like of_alist_exn c (Sequence.to_list seq)
but does not allocate the intermediate list.
val of_sequence_multi :
( 'a, 'cmp ) comparator ->
('a * 'b) Sequence.t ->
( 'a, 'b list, 'cmp ) t
Creates a map from an association sequence with possibly repeated keys. The values in the map for a given key appear in the same order as they did in the association list.
of_sequence_multi c seq
behaves like of_alist_exn c (Sequence.to_list seq)
but does not allocate the intermediate list.
val of_sequence_fold :
( 'a, 'cmp ) comparator ->
('a * 'b) Sequence.t ->
init:'c ->
f:( 'c -> 'b -> 'c ) ->
( 'a, 'c, 'cmp ) t
Combines an association sequence into a map, folding together bound values with common keys.
of_sequence_fold c seq ~init ~f
behaves like of_alist_fold c (Sequence.to_list seq) ~init ~f
but does not allocate the intermediate list.
val of_sequence_reduce :
( 'a, 'cmp ) comparator ->
('a * 'b) Sequence.t ->
f:( 'b -> 'b -> 'b ) ->
( 'a, 'b, 'cmp ) t
Combines an association sequence into a map, reducing together bound values with common keys.
of_sequence_reduce c seq ~f
behaves like of_alist_reduce c (Sequence.to_list seq) ~f
but does not allocate the intermediate list.
val is_empty : ( _, _, _ ) t -> bool
Tests whether a map is empty.
val length : ( _, _, _ ) t -> int
length map
returns the number of elements in map
. O(1), but Tree.length
is O(n).
Returns a new map with the specified new binding; if the key was already bound, its previous binding disappears.
val add :
( 'k, 'v, 'cmp ) t ->
key:'k ->
data:'v ->
( 'k, 'v, 'cmp ) t Or_duplicate.t
add t ~key ~data
adds a new entry to t
mapping key
to data
and returns `Ok
with the new map, or if key
is already present in t
, returns `Duplicate
.
If key
is not present then add a singleton list, otherwise, cons data onto the head of the existing list.
If the key is present, then remove its head element; if the result is empty, remove the key.
val find_multi : ( 'k, 'v list, 'cmp ) t -> 'k -> 'v list
Returns the value bound to the given key, or the empty list if there is none.
change t key ~f
returns a new map m
that is the same as t
on all keys except for key
, and whose value for key
is defined by f
, i.e., find m key = f (find
t key)
.
update t key ~f
is change t key ~f:(fun o -> Some (f o))
.
val find : ( 'k, 'v, 'cmp ) t -> 'k -> 'v option
Returns Some value
bound to the given key, or None
if none exists.
val find_exn : ( 'k, 'v, 'cmp ) t -> 'k -> 'v
Returns the value bound to the given key, raising Caml.Not_found
or Not_found_s
if none exists.
Returns a new map with any binding for the key in question removed.
val mem : ( 'k, _, 'cmp ) t -> 'k -> bool
mem map key
tests whether map
contains a binding for key
.
val iter_keys : ( 'k, _, _ ) t -> f:( 'k -> unit ) -> unit
val iter : ( _, 'v, _ ) t -> f:( 'v -> unit ) -> unit
val iteri : ( 'k, 'v, _ ) t -> f:( key:'k -> data:'v -> unit ) -> unit
val iteri_until :
( 'k, 'v, _ ) t ->
f:( key:'k -> data:'v -> Continue_or_stop.t ) ->
Finished_or_unfinished.t
Iterates until the first time f
returns Stop
. If f
returns Stop
, the final result is Unfinished
. Otherwise, the final result is Finished
.
val iter2 :
( 'k, 'v1, 'cmp ) t ->
( 'k, 'v2, 'cmp ) t ->
f:
( key:'k ->
data:[ `Left of 'v1 | `Right of 'v2 | `Both of 'v1 * 'v2 ] ->
unit ) ->
unit
Iterates two maps side by side. The complexity of this function is O(M + N). If two inputs are [(0, a); (1, a)]
and [(1, b); (2, b)]
, f
will be called with [(0,
`Left a); (1, `Both (a, b)); (2, `Right b)]
.
Returns a new map with bound values replaced by f
applied to the bound values.
Like map
, but the passed function takes both key
and data
as arguments.
val fold :
( 'k, 'v, _ ) t ->
init:'a ->
f:( key:'k -> data:'v -> 'a -> 'a ) ->
'a
Folds over keys and data in the map in increasing order of key
.
val fold_right :
( 'k, 'v, _ ) t ->
init:'a ->
f:( key:'k -> data:'v -> 'a -> 'a ) ->
'a
Folds over keys and data in the map in decreasing order of key
.
val fold2 :
( 'k, 'v1, 'cmp ) t ->
( 'k, 'v2, 'cmp ) t ->
init:'a ->
f:
( key:'k ->
data:[ `Left of 'v1 | `Right of 'v2 | `Both of 'v1 * 'v2 ] ->
'a ->
'a ) ->
'a
Folds over two maps side by side, like iter2
.
filter
, filteri
, filter_keys
, filter_map
, and filter_mapi
run in O(n * lg n) time; they simply accumulate each key & data pair retained by f
into a new map using add
.
Returns a new map with bound values filtered by f
applied to the bound values.
val filter_mapi :
( 'k, 'v1, 'cmp ) t ->
f:( key:'k -> data:'v1 -> 'v2 option ) ->
( 'k, 'v2, 'cmp ) t
Like filter_map
, but the passed function takes both key
and data
as arguments.
val partition_mapi :
( 'k, 'v1, 'cmp ) t ->
f:( key:'k -> data:'v1 -> ( 'v2, 'v3 ) Either.t ) ->
( 'k, 'v2, 'cmp ) t * ( 'k, 'v3, 'cmp ) t
partition_mapi t ~f
returns two new t
s, with each key in t
appearing in exactly one of the resulting maps depending on its mapping in f
.
val partition_map :
( 'k, 'v1, 'cmp ) t ->
f:( 'v1 -> ( 'v2, 'v3 ) Either.t ) ->
( 'k, 'v2, 'cmp ) t * ( 'k, 'v3, 'cmp ) t
partition_map t ~f = partition_mapi t ~f:(fun ~key:_ ~data -> f data)
val partitioni_tf :
( 'k, 'v, 'cmp ) t ->
f:( key:'k -> data:'v -> bool ) ->
( 'k, 'v, 'cmp ) t * ( 'k, 'v, 'cmp ) t
partitioni_tf t ~f
=
partition_mapi t ~f:(fun ~key ~data ->
if f ~key ~data
then First data
else Second data)
val partition_tf :
( 'k, 'v, 'cmp ) t ->
f:( 'v -> bool ) ->
( 'k, 'v, 'cmp ) t * ( 'k, 'v, 'cmp ) t
partition_tf t ~f = partitioni_tf t ~f:(fun ~key:_ ~data -> f data)
val combine_errors :
( 'k, 'v Or_error.t, 'cmp ) t ->
( 'k, 'v, 'cmp ) t Or_error.t
Produces Ok
of a map including all keys if all data is Ok
, or an Error
including all errors otherwise.
Returns a total ordering between maps. The first argument is a total ordering used to compare data associated with equal keys in the two maps.
val hash_fold_direct :
'k Hash.folder ->
'v Hash.folder ->
( 'k, 'v, 'cmp ) t Hash.folder
Hash function: a building block to use when hashing data structures containing maps in them. hash_fold_direct hash_fold_key
is compatible with compare_direct
iff hash_fold_key
is compatible with (comparator m).compare
of the map m
being hashed.
equal cmp m1 m2
tests whether the maps m1
and m2
are equal, that is, contain the same keys and associate each key with the same value. cmp
is the equality predicate used to compare the values associated with the keys.
val keys : ( 'k, _, _ ) t -> 'k list
Returns a list of the keys in the given map.
val data : ( _, 'v, _ ) t -> 'v list
Returns a list of the data in the given map.
val to_alist :
?key_order:[ `Increasing | `Decreasing ] ->
( 'k, 'v, _ ) t ->
('k * 'v) list
Creates an association list from the given map.
val validate :
name:( 'k -> string ) ->
'v Validate.check ->
( 'k, 'v, _ ) t Validate.check
val validatei :
name:( 'k -> string ) ->
('k * 'v) Validate.check ->
( 'k, 'v, _ ) t Validate.check
Additional operations on maps
val merge :
( 'k, 'v1, 'cmp ) t ->
( 'k, 'v2, 'cmp ) t ->
f:
( key:'k ->
[ `Left of 'v1 | `Right of 'v2 | `Both of 'v1 * 'v2 ] ->
'v3 option ) ->
( 'k, 'v3, 'cmp ) t
Merges two maps. The runtime is O(length(t1) + length(t2)). You shouldn't use this function to merge a list of maps; consider using merge_skewed
instead.
val merge_skewed :
( 'k, 'v, 'cmp ) t ->
( 'k, 'v, 'cmp ) t ->
combine:( key:'k -> 'v -> 'v -> 'v ) ->
( 'k, 'v, 'cmp ) t
A special case of merge
, merge_skewed t1 t2
is a map containing all the bindings of t1
and t2
. Bindings that appear in both t1
and t2
are combined into a single value using the combine
function. In a call combine ~key v1 v2
, the value v1
comes from t1
and v2
from t2
.
The runtime of merge_skewed
is O(l1 * log(l2))
, where l1
is the length of the smaller map and l2
the length of the larger map. This is likely to be faster than merge
when one of the maps is a lot smaller, or when you merge a list of maps.
module Symmetric_diff_element : sig ... end
val symmetric_diff :
( 'k, 'v, 'cmp ) t ->
( 'k, 'v, 'cmp ) t ->
data_equal:( 'v -> 'v -> bool ) ->
( 'k, 'v ) Symmetric_diff_element.t Sequence.t
symmetric_diff t1 t2 ~data_equal
returns a list 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. The keys in the output sequence will be in sorted order.
It is assumed that data_equal
is at least as equating as physical equality: that phys_equal x y
implies data_equal x y
. Otherwise, symmetric_diff
may behave in unexpected ways. For example, with ~data_equal:(fun _ _ -> false)
it is NOT necessarily the case the resulting change sequence will contain an element (k, `Unequal _)
for every key k
shared by both maps.
Warning: Float equality violates this property! phys_equal Float.nan Float.nan
is true, but Float.(=) Float.nan Float.nan
is false.
val fold_symmetric_diff :
( 'k, 'v, 'cmp ) t ->
( 'k, 'v, 'cmp ) t ->
data_equal:( 'v -> 'v -> bool ) ->
init:'a ->
f:( 'a -> ( 'k, 'v ) Symmetric_diff_element.t -> 'a ) ->
'a
fold_symmetric_diff t1 t2 ~data_equal
folds across an implicit sequence of changes between t1
and t2
, in sorted order by keys. Equivalent to Sequence.fold (symmetric_diff t1 t2 ~data_equal)
, and more efficient.
val min_elt : ( 'k, 'v, _ ) t -> ('k * 'v) option
min_elt map
returns Some (key, data)
pair corresponding to the minimum key in map
, or None
if empty.
val min_elt_exn : ( 'k, 'v, _ ) t -> 'k * 'v
val max_elt : ( 'k, 'v, _ ) t -> ('k * 'v) option
max_elt map
returns Some (key, data)
pair corresponding to the maximum key in map
, or None
if map
is empty.
val max_elt_exn : ( 'k, 'v, _ ) t -> 'k * 'v
These functions have the same semantics as similar functions in List
.
val for_all : ( 'k, 'v, _ ) t -> f:( 'v -> bool ) -> bool
val for_alli : ( 'k, 'v, _ ) t -> f:( key:'k -> data:'v -> bool ) -> bool
val exists : ( 'k, 'v, _ ) t -> f:( 'v -> bool ) -> bool
val existsi : ( 'k, 'v, _ ) t -> f:( key:'k -> data:'v -> bool ) -> bool
val count : ( 'k, 'v, _ ) t -> f:( 'v -> bool ) -> int
val counti : ( 'k, 'v, _ ) t -> f:( key:'k -> data:'v -> bool ) -> int
split t key
returns a map of keys strictly less than key
, the mapping of key
if any, and a map of keys strictly greater than key
.
Runtime is O(m + log n), where n is the size of the input map and m is the size of the smaller of the two output maps. The O(m) term is due to the need to calculate the length of the output maps.
val append :
lower_part:( 'k, 'v, 'cmp ) t ->
upper_part:( 'k, 'v, 'cmp ) t ->
[ `Ok of ( 'k, 'v, 'cmp ) t | `Overlapping_key_ranges ]
append ~lower_part ~upper_part
returns `Ok map
where map
contains all the (key, value)
pairs from the two input maps if all the keys from lower_part
are less than all the keys from upper_part
. Otherwise it returns `Overlapping_key_ranges
.
Runtime is O(log n) where n is the size of the larger input map. This can be significantly faster than Map.merge
or repeated Map.add
.
assert (match Map.append ~lower_part ~upper_part with
| `Ok whole_map ->
Map.to_alist whole_map
= List.append (to_alist lower_part) (to_alist upper_part)
| `Overlapping_key_ranges -> true);
val subrange :
( 'k, 'v, 'cmp ) t ->
lower_bound:'k Maybe_bound.t ->
upper_bound:'k Maybe_bound.t ->
( 'k, 'v, 'cmp ) t
subrange t ~lower_bound ~upper_bound
returns a map containing all the entries from t
whose keys lie inside the interval indicated by ~lower_bound
and ~upper_bound
. If this interval is empty, an empty map is returned.
Runtime is O(m + log n), where n is the size of the input map and m is the size of the output map. The O(m) term is due to the need to calculate the length of the output map.
val fold_range_inclusive :
( 'k, 'v, 'cmp ) t ->
min:'k ->
max:'k ->
init:'a ->
f:( key:'k -> data:'v -> 'a -> 'a ) ->
'a
fold_range_inclusive t ~min ~max ~init ~f
folds f
(with initial value ~init
) over all keys (and their associated values) that are in the range [min, max]
(inclusive).
val range_to_alist : ( 'k, 'v, 'cmp ) t -> min:'k -> max:'k -> ('k * 'v) list
range_to_alist t ~min ~max
returns an associative list of the elements whose keys lie in [min, max]
(inclusive), with the smallest key being at the head of the list.
val closest_key :
( 'k, 'v, 'cmp ) t ->
[ `Greater_or_equal_to | `Greater_than | `Less_or_equal_to | `Less_than ] ->
'k ->
('k * 'v) option
closest_key t dir k
returns the (key, value)
pair in t
with key
closest to k
that satisfies the given inequality bound.
For example, closest_key t `Less_than k
would be the pair with the closest key to k
where key < k
.
to_sequence
can be used to get the same results as closest_key
. It is less efficient for individual lookups but more efficient for finding many elements starting at some value.
val nth : ( 'k, 'v, _ ) t -> int -> ('k * 'v) option
nth t n
finds the (key, value) pair of rank n (i.e., such that there are exactly n keys strictly less than the found key), if one exists. O(log(length t) + n) time.
val nth_exn : ( 'k, 'v, _ ) t -> int -> 'k * 'v
val rank : ( 'k, 'v, 'cmp ) t -> 'k -> int option
rank t k
If k
is in t
, returns the number of keys strictly less than k
in t
, and None
otherwise.
val to_sequence :
?order:[ `Increasing_key | `Decreasing_key ] ->
?keys_greater_or_equal_to:'k ->
?keys_less_or_equal_to:'k ->
( 'k, 'v, 'cmp ) t ->
('k * 'v) Sequence.t
to_sequence ?order ?keys_greater_or_equal_to ?keys_less_or_equal_to t
gives a sequence of key-value pairs between keys_less_or_equal_to
and keys_greater_or_equal_to
inclusive, presented in order
. If keys_greater_or_equal_to > keys_less_or_equal_to
, the sequence is empty.
When neither keys_greater_or_equal_to
nor keys_less_or_equal_to
are provided, the cost is O(log n) up front and amortized O(1) to produce each element. If either is provided (and is used by the order parameter provided), then the the cost is O(n) up front, and amortized O(1) to produce each element.
val binary_search :
( 'k, 'v, 'cmp ) t ->
compare:( key:'k -> data:'v -> 'key -> 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 ->
('k * 'v) option
binary_search t ~compare which elt
returns the (key, value)
pair 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
.
val binary_search_segmented :
( 'k, 'v, 'cmp ) t ->
segment_of:( key:'k -> data:'v -> [ `Left | `Right ] ) ->
[ `Last_on_left | `First_on_right ] ->
('k * 'v) 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 (key, value)
pair 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
.
M
is meant to be used in combination with OCaml applicative functor types:
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 = Hasher.S
val m__t_sexp_grammar : Sexp.Private.Raw_grammar.t
val hash_fold_m__t :
(module Hash_fold_m with type t = 'k) ->
( Hash.state -> 'v -> Hash.state ) ->
Hash.state ->
( 'k, 'v, _ ) t ->
Hash.state
module Poly : sig ... end
A polymorphic Map.
module Using_comparator : sig ... end
Using_comparator
is a similar interface as the toplevel of Map
, except the functions take a ~comparator:('k, 'cmp) Comparator.t
, whereas the functions at the toplevel of Map
take a ('k, 'cmp) comparator
.
Modules and module types for extending Map
For use in extensions of Base, like Core_kernel
.
module With_comparator : sig ... end
module With_first_class_module : sig ... end
module Without_comparator : sig ... end
module type For_deriving = sig ... end
module type S_poly = sig ... end
module type Accessors1 = sig ... end
module type Accessors2 = sig ... end
module type Accessors3 = sig ... end
module type Accessors3_with_comparator = sig ... end
module type Accessors_generic = sig ... end
module type Creators1 = sig ... end
module type Creators2 = sig ... end
module type Creators3_with_comparator = sig ... end
module type Creators_and_accessors1 = sig ... end
module type Creators_and_accessors2 = sig ... end
module type Creators_and_accessors3_with_comparator = sig ... end
module type Creators_and_accessors_generic = sig ... end
module type Creators_generic = sig ... end