Module Core_kernel.Map
Map
is a functional data structure (balanced binary tree) implementing finite maps over a totally-ordered domain, called a "key".
For example:
let empty = Map.empty (module String)
let numbers =
Map.of_alist_exn (module String)
["three", Substr "three"; "four", Substr "four"]
Note that the functions in Map are polymorphic over the type of the key and of the data; you just need to pass in the first-class module for the key type (here, String
).
Suppose you wanted to define a new module Foo
to use in a map. You would write:
module Foo = struct
module T = struct
type t = int * int
let compare x y = Tuple2.compare Int.compare Int.compare
let sexp_of_t = Tuple2.sexp_of_t Int.sexp_of_t Int.sexp_of_t
end
include T
include Comparable.Make(T)
end
This gives you a module Foo
with the appropriate comparator in it, and then this:
let m = Map.empty (module Foo)
lets you create a map keyed by Foo
. The reason you need to write a sexp-converter and a comparison function for this to work is that maps both need comparison and the ability to serialize the key for generating useful errors. It's yet nicer to do this with the appropriate PPXs:
module Foo = struct
module T =
struct type t = int * int [@@deriving sexp_of, compare] end
include T
include Comparable.Make(T)
end
The interface
type ('key, +'value, 'cmp) t
= ('key, 'value, 'cmp) Base.Map.t
type ('k, 'cmp) comparator
= (module Comparator.S with type comparator_witness = 'cmp and type t = 'k)
val invariants : (_, _, _) t -> Core_kernel__.Import.bool
Test if invariants of internal AVL search tree hold.
val comparator : ('a, _, 'cmp) t -> ('a, 'cmp) Comparator.t
val comparator_s : ('a, _, 'cmp) t -> ('a, 'cmp) comparator
val empty : ('a, 'cmp) comparator -> ('a, 'b, 'cmp) t
The empty map.
val singleton : ('a, 'cmp) comparator -> 'a -> 'b -> ('a, 'b, 'cmp) t
Map with one (key, data) pair.
val of_alist : ('a, 'cmp) comparator -> ('a * 'b) Core_kernel__.Import.list -> [ `Ok of ('a, 'b, 'cmp) t | `Duplicate_key of 'a ]
Creates map from an association list with unique keys.
val of_alist_or_error : ('a, 'cmp) comparator -> ('a * 'b) Core_kernel__.Import.list -> ('a, 'b, 'cmp) t Or_error.t
Creates map from an association list with unique keys. Returns an error if duplicate
'a
keys are found.
val of_alist_exn : ('a, 'cmp) comparator -> ('a * 'b) Core_kernel__.Import.list -> ('a, 'b, 'cmp) t
Creates map from an association list with unique keys. Raises an exception if duplicate
'a
keys are found.
val of_hashtbl_exn : ('a, 'cmp) comparator -> ('a, 'b) Hashtbl.t -> ('a, 'b, 'cmp) t
of_hashtbl_exn
creates a map from bindings present in a hash table.of_hashtbl_exn
raises if there are distinct keysa1
anda2
in the table withcomparator.compare a1 a2 = 0
, which is only possible if the hash-table comparison function is different thancomparator.compare
. In the common case, the comparison is the same, in which caseof_hashtbl_exn
does not raise, regardless of the keys present in the table.
val of_alist_multi : ('a, 'cmp) comparator -> ('a * 'b) Core_kernel__.Import.list -> ('a, 'b Core_kernel__.Import.list, 'cmp) t
Creates map from an association list with possibly repeated keys.
val of_alist_fold : ('a, 'cmp) comparator -> ('a * 'b) Core_kernel__.Import.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) Core_kernel__.Import.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 -> Core_kernel__.Import.unit) -> Core_kernel__.Import.unit) -> [ `Ok of ('a, 'b, 'cmp) t | `Duplicate_key of 'a ]
of_iteri ~iteri
behaves likeof_alist
, except that instead of taking a concrete datastruture, 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.
Trees
Parallel to the three kinds of map modules Map
, Map.Poly
, and Key.Map
, there are also tree modules Map.Tree
, Map.Poly.Tree
, and Key.Map.Tree
. A tree is a bare representation of a map, without the comparator. Thus tree operations need to obtain the comparator from somewhere. For Map.Poly.Tree
and Key.Map.Tree
, the comparator is implicit in the module name. For Map.Tree
, the comparator must be passed to each operation.
The main advantages of trees over maps are slightly improved space usage (there is no outer container holding the comparator) and the ability to marshal trees, because a tree doesn't contain a closure, the way a map does.
The main disadvantages of using trees are needing to be more explicit about the comparator, and the possibility of accidentally using polymorphic equality on a tree (for which maps dynamically detect failure due to the presence of a closure in the data structure).
module Tree : sig ... end
val to_tree : ('k, 'v, 'cmp) t -> ('k, 'v, 'cmp) Tree.t
val of_tree : ('k, 'cmp) comparator -> ('k, 'v, 'cmp) Tree.t -> ('k, 'v, 'cmp) t
Creates a
t
from aTree.t
and aComparator.t
. This is an O(n) operation as it must discover the length of theTree.t
.
More interface
val of_sorted_array : ('a, 'cmp) comparator -> ('a * 'b) Core_kernel__.Import.array -> ('a, 'b, 'cmp) t Or_error.t
Creates map from a sorted array of key-data pairs. The input array must be sorted, as given by the relevant comparator (either in ascending or descending order), and must not contain any duplicate keys. If either of these conditions does not hold, an error is returned.
val of_sorted_array_unchecked : ('a, 'cmp) comparator -> ('a * 'b) Core_kernel__.Import.array -> ('a, 'b, 'cmp) t
Like
of_sorted_array
except it returns a map with broken invariants when anError
would have been returned.
val of_increasing_iterator_unchecked : ('a, 'cmp) comparator -> len:Core_kernel__.Import.int -> f:(Core_kernel__.Import.int -> 'a * 'b) -> ('a, 'b, '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 of_increasing_sequence : ('k, 'cmp) comparator -> ('k * 'v) Sequence.t -> ('k, 'v, 'cmp) t Or_error.t
of_increasing_sequence c seq
behaves likeof_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 likeof_alist c (Sequence.to_list seq)
but does not allocate the intermediate list.If your sequence is increasing, use
of_increasing_sequence
for better performance.
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 likeof_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 likeof_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 Core_kernel__.Import.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 likeof_alist_multi 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 likeof_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 likeof_alist_reduce c (Sequence.to_list seq) ~f
but does not allocate the intermediate list.
val is_empty : (_, _, _) t -> Core_kernel__.Import.bool
Tests whether a map is empty or not.
val length : (_, _, _) t -> Core_kernel__.Import.int
length map
returns number of elements inmap
. O(1), butTree.length
is O(n).
val add : ('k, 'v, 'cmp) t -> key:'k -> data:'v -> ('k, 'v, 'cmp) t Map_intf.Or_duplicate.t
add_exn t ~key ~data
returnst
extended withkey
mapped todata
, raising ifmem key t
.
val add_exn : ('k, 'v, 'cmp) t -> key:'k -> data:'v -> ('k, 'v, 'cmp) t
val set : ('k, 'v, 'cmp) t -> key:'k -> data:'v -> ('k, 'v, 'cmp) t
Returns a new map with the specified new binding; if the key was already bound, its previous binding disappears.
val add_multi : ('k, 'v Core_kernel__.Import.list, 'cmp) t -> key:'k -> data:'v -> ('k, 'v Core_kernel__.Import.list, 'cmp) t
If
key
is not present then add a singleton list, otherwise, cons data onto the head of the existing list.
val remove_multi : ('k, 'v Core_kernel__.Import.list, 'cmp) t -> 'k -> ('k, 'v Core_kernel__.Import.list, 'cmp) t
If
k
is present then remove its head element; if result is empty, remove the key.
val find_multi : ('k, 'v Core_kernel__.Import.list, 'cmp) t -> 'k -> 'v Core_kernel__.Import.list
find_multi t key
returnst
's values forkey
ifkey
is present in the table, and returns the empty list otherwise.
val change : ('k, 'v, 'cmp) t -> 'k -> f:('v Core_kernel__.Import.option -> 'v Core_kernel__.Import.option) -> ('k, 'v, 'cmp) t
change t key ~f
returns a new mapm
that is the same ast
on all keys except forkey
, and whose value forkey
is defined byf
, i.e.,find m key = f (find t key)
.
val update : ('k, 'v, 'cmp) t -> 'k -> f:('v Core_kernel__.Import.option -> 'v) -> ('k, 'v, 'cmp) t
update t key ~f
ischange t key ~f:(fun o -> Some (f o))
.
val find : ('k, 'v, 'cmp) t -> 'k -> 'v Core_kernel__.Import.option
Returns the value bound to the given key if it exists, and
None
otherwise.
val find_exn : ('k, 'v, 'cmp) t -> 'k -> 'v
Returns the value bound to the given key, raising
Caml.Not_found
orNot_found_s
if none exists.
val find_or_error : ('k, 'v, 'cmp) t -> 'k -> 'v Or_error.t
val remove : ('k, 'v, 'cmp) t -> 'k -> ('k, 'v, 'cmp) t
Returns a new map with any binding for the key in question removed.
val mem : ('k, _, 'cmp) t -> 'k -> Core_kernel__.Import.bool
mem map key
tests whethermap
contains a binding forkey
.
val iter_keys : ('k, _, _) t -> f:('k -> Core_kernel__.Import.unit) -> Core_kernel__.Import.unit
val iter : (_, 'v, _) t -> f:('v -> Core_kernel__.Import.unit) -> Core_kernel__.Import.unit
val iteri : ('k, 'v, _) t -> f:(key:'k -> data:'v -> Core_kernel__.Import.unit) -> Core_kernel__.Import.unit
module Continue_or_stop : sig ... end
module Finished_or_unfinished : sig ... end
val iteri_until : ('k, 'v, _) t -> f:(key:'k -> data:'v -> Continue_or_stop.t) -> Finished_or_unfinished.t
Iterates until
f
returnsStop
. Iff
returnsStop
, the final result isUnfinished
. Otherwise, the final result isFinished
.
val iter2 : ('k, 'v1, 'cmp) t -> ('k, 'v2, 'cmp) t -> f:(key:'k -> data:[ `Left of 'v1 | `Right of 'v2 | `Both of 'v1 * 'v2 ] -> Core_kernel__.Import.unit) -> Core_kernel__.Import.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)]
val map : ('k, 'v1, 'cmp) t -> f:('v1 -> 'v2) -> ('k, 'v2, 'cmp) t
Returns new map with bound values replaced by the result of
f
applied to them.
val mapi : ('k, 'v1, 'cmp) t -> f:(key:'k -> data:'v1 -> 'v2) -> ('k, 'v2, 'cmp) t
Like
map
, butf
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 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 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
.
val filter_keys : ('k, 'v, 'cmp) t -> f:('k -> Core_kernel__.Import.bool) -> ('k, 'v, 'cmp) t
val filter : ('k, 'v, 'cmp) t -> f:('v -> Core_kernel__.Import.bool) -> ('k, 'v, 'cmp) t
val filteri : ('k, 'v, 'cmp) t -> f:(key:'k -> data:'v -> Core_kernel__.Import.bool) -> ('k, 'v, 'cmp) t
val filter_map : ('k, 'v1, 'cmp) t -> f:('v1 -> 'v2 Core_kernel__.Import.option) -> ('k, 'v2, 'cmp) t
Returns new map with bound values filtered by the result of
f
applied to them.
val filter_mapi : ('k, 'v1, 'cmp) t -> f:(key:'k -> data:'v1 -> 'v2 Core_kernel__.Import.option) -> ('k, 'v2, 'cmp) t
Like
filter_map
, but 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 newt
s, with each key int
appearing in exactly one of the result maps depending on its mapping inf
.
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 -> Core_kernel__.Import.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 -> Core_kernel__.Import.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 isOk
, or anError
including all errors otherwise.
val compare_direct : ('v -> 'v -> Core_kernel__.Import.int) -> ('k, 'v, 'cmp) t -> ('k, 'v, 'cmp) t -> Core_kernel__.Import.int
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 Core_kernel__.Import.Hash.folder -> 'v Core_kernel__.Import.Hash.folder -> ('k, 'v, 'cmp) t Core_kernel__.Import.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 withcompare_direct
iffhash_fold_key
is compatible with(comparator m).compare
of the mapm
being hashed.
val equal : ('v -> 'v -> Core_kernel__.Import.bool) -> ('k, 'v, 'cmp) t -> ('k, 'v, 'cmp) t -> Core_kernel__.Import.bool
equal cmp m1 m2
tests whether the mapsm1
andm2
are equal, that is, contain equal keys and associate them with equal data.cmp
is the equality predicate used to compare the data associated with the keys.
val keys : ('k, _, _) t -> 'k Core_kernel__.Import.list
Returns list of keys in map.
val data : (_, 'v, _) t -> 'v Core_kernel__.Import.list
Returns list of data in map.
val to_alist : ?key_order:[ `Increasing | `Decreasing ] -> ('k, 'v, _) t -> ('k * 'v) Core_kernel__.Import.list
Creates association list from map.
- parameter key_order
default is
`Increasing
val validate : name:('k -> Core_kernel__.Import.string) -> 'v Core_kernel__.Import.Validate.check -> ('k, 'v, _) t Core_kernel__.Import.Validate.check
val validatei : name:('k -> Core_kernel__.Import.string) -> ('k * 'v) Core_kernel__.Import.Validate.check -> ('k, 'v, _) t Core_kernel__.Import.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 Core_kernel__.Import.option) -> ('k, 'v3, 'cmp) t
Merges two maps. The runtime is O(length(t1) + length(t2)). In particular, 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 oft1
andt2
. Bindings that appear in botht1
andt2
are merged using thecombine
function. In a callcombine ~key v1 v2
the valuev1
comes fromt1
andv2
fromt2
.The runtime of
merge_skewed
isO(l1 * log(l2))
, wherel1
is the length of the smaller map andl2
the length of the larger map. This is likely to be faster thanmerge
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 -> Core_kernel__.Import.bool) -> ('k, 'v) Symmetric_diff_element.t Sequence.t
symmetric_diff t1 t2 ~data_equal
returns a list of changes betweent1
andt2
. It is intended to be efficient in the case wheret1
andt2
share a large amount of structure. The keys in the output sequence will be in sorted order.
val fold_symmetric_diff : ('k, 'v, 'cmp) t -> ('k, 'v, 'cmp) t -> data_equal:('v -> 'v -> Core_kernel__.Import.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 betweent1
andt2
, in sorted order by keys. Equivalent toSequence.fold (symmetric_diff t1 t2 ~data_equal)
, and more efficient.
val min_elt : ('k, 'v, _) t -> ('k * 'v) Core_kernel__.Import.option
min_elt map
returnsSome (key, data)
pair corresponding to the minimum key inmap
,None
ifmap
is empty.
val min_elt_exn : ('k, 'v, _) t -> 'k * 'v
val max_elt : ('k, 'v, _) t -> ('k * 'v) Core_kernel__.Import.option
max_elt map
returnsSome (key, data)
pair corresponding to the maximum key inmap
, andNone
ifmap
is empty.
val max_elt_exn : ('k, 'v, _) t -> 'k * 'v
val for_all : ('k, 'v, _) t -> f:('v -> Core_kernel__.Import.bool) -> Core_kernel__.Import.bool
val for_alli : ('k, 'v, _) t -> f:(key:'k -> data:'v -> Core_kernel__.Import.bool) -> Core_kernel__.Import.bool
val exists : ('k, 'v, _) t -> f:('v -> Core_kernel__.Import.bool) -> Core_kernel__.Import.bool
val existsi : ('k, 'v, _) t -> f:(key:'k -> data:'v -> Core_kernel__.Import.bool) -> Core_kernel__.Import.bool
val count : ('k, 'v, _) t -> f:('v -> Core_kernel__.Import.bool) -> Core_kernel__.Import.int
val counti : ('k, 'v, _) t -> f:(key:'k -> data:'v -> Core_kernel__.Import.bool) -> Core_kernel__.Import.int
val split : ('k, 'v, 'cmp) t -> 'k -> ('k, 'v, 'cmp) t * ('k * 'v) Core_kernel__.Import.option * ('k, 'v, 'cmp) t
split t key
returns a map of keys strictly less thankey
, the mapping ofkey
if any, and a map of keys strictly greater thankey
.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
wheremap
contains all the(key, value)
pairs from the two input maps if all the keys fromlower_part
are less than all the keys fromupper_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 repeatedMap.add
.assert (match Map.append ~lower_part ~upper_part with | `Ok whole_map -> whole_map = Map.(of_alist_exn (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 fromt
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
foldsf
(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) Core_kernel__.Import.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) Core_kernel__.Import.option
closest_key t dir k
returns the(key, value)
pair int
withkey
closest tok
, which satisfies the given inequality bound.For example,
closest_key t `Less_than k
would be the pair with the closest key tok
wherekey < k
.to_sequence
can be used to get the same results asclosest_key
. It is less efficient for individual lookups but more efficient for finding many elements starting at some value.
val nth : ('k, 'v, _) t -> Core_kernel__.Import.int -> ('k * 'v) Core_kernel__.Import.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 -> Core_kernel__.Import.int -> 'k * 'v
val rank : ('k, 'v, 'cmp) t -> 'k -> Core_kernel__.Import.int Core_kernel__.Import.option
rank t k
ifk
is int
, returns the number of keys strictly less thank
int
, otherwiseNone
.
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 betweenkeys_less_or_equal_to
andkeys_greater_or_equal_to
inclusive, presented inorder
. Ifkeys_greater_or_equal_to > keys_less_or_equal_to
, the sequence is empty. Cost is O(log n) up front and amortized O(1) to produce each element.- parameter order
`Increasing_key
is the default
val binary_search : ('k, 'v, 'cmp) t -> compare:(key:'k -> data:'v -> '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 -> ('k * 'v) Core_kernel__.Import.option
binary_search t ~compare which elt
returns the(key, value)
pair 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 : ('k, 'v, 'cmp) t -> segment_of:(key:'k -> data:'v -> [ `Left | `Right ]) -> [ `Last_on_left | `First_on_right ] -> ('k * 'v) 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(key, value)
pair 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
.
val of_key_set : ('key, 'cmp) Base.Set.t -> f:('key -> 'data) -> ('key, 'data, 'cmp) t
Convert a set to a map. Runs in
O(length t)
time plus a call tof
for each key to compute the associated data.
val key_set : ('key, _, 'cmp) t -> ('key, 'cmp) Base.Set.t
Converts a map to a set of its keys. Runs in
O(length t)
time.
val quickcheck_generator : ('k, 'cmp) comparator -> 'k Quickcheck.Generator.t -> 'v Quickcheck.Generator.t -> ('k, 'v, 'cmp) t Quickcheck.Generator.t
val quickcheck_observer : 'k Quickcheck.Observer.t -> 'v Quickcheck.Observer.t -> ('k, 'v, 'cmp) t Quickcheck.Observer.t
val quickcheck_shrinker : 'k Quickcheck.Shrinker.t -> 'v Quickcheck.Shrinker.t -> ('k, 'v, 'cmp) t Quickcheck.Shrinker.t
This shrinker and the other shrinkers for maps and trees produce a shrunk value by dropping a key-value pair, shrinking a key or shrinking a value. A shrunk key will override an existing key's value.
Which Map module should you use?
The map types and operations appear in three places:
- Map: polymorphic map operations
- Map.Poly: maps that use polymorphic comparison to order keys
- Key.Map: maps with a fixed key type that use
Key.compare
to order keys
where Key
is any module defining values that can be used as keys of a map, like Int
, String
, etc. To add this functionality to an arbitrary module, use the Comparable.Make
functor.
You should use Map
for functions that access existing maps, like find
, mem
, add
, fold
, iter
, and to_alist
. For functions that create maps, like empty
, singleton
, and of_alist
, strive to use the corresponding Key.Map
function, which will use the comparison function specifically for Key
. As a last resort, if you don't have easy access to a comparison function for the keys in your map, use Map.Poly
to create the map. This will use OCaml's built-in polymorphic comparison to compare keys, with all the usual performance and robustness problems that entails.
Interface design details
An instance of the map type is determined by the types of the map's keys and values, and the comparison function used to order the keys:
type ('key, 'value, 'cmp) Map.t
'cmp
is a phantom type uniquely identifying the comparison function, as generated by Comparator.Make
.
Map.Poly
supports arbitrary key and value types, but enforces that the comparison function used to order the keys is polymorphic comparison. Key.Map
has a fixed key type and comparison function, and supports arbitrary values.
type ('key, 'value) Map.Poly.t = ('key , 'value, Comparator.Poly.t ) Map.t
type 'value Key.Map.t = (Key.t, 'value, Key.comparator_witness) Map.t
The same map operations exist in Map
, Map.Poly
, and Key.Map
, albeit with different types. For example:
val Map.length : (_, _, _) Map.t -> int
val Map.Poly.length : (_, _) Map.Poly.t -> int
val Key.Map.length : _ Key.Map.t -> int
Because Map.Poly.t
and Key.Map.t
are exposed as instances of the more general Map.t
type, one can use Map.length
on any map. The same is true for all of the functions that access an existing map, such as add
, change
, find
, fold
, iter
, map
, to_alist
, etc.
Depending on the number of type variables N
, the type of accessor (resp. creator) functions is defined in the module type AccessorsN
(CreatorsN
) in Map_intf
. Also for creators, when the comparison function is not fixed, i.e., the 'cmp
variable of Map.t
is free, we need to pass a comparator to the function creating the map. The module type is called Creators3_with_comparator
. There is also a module type Accessors3_with_comparator
in addition to Accessors3
which used for trees since the comparator is not known.
module Using_comparator : sig ... end
module type Key_plain = Map_intf.Key_plain
module type Key = Map_intf.Key
module type Key_binable = Map_intf.Key_binable
module type S_plain = Map_intf.S_plain
module type S = Map_intf.S
module type S_binable = Map_intf.S_binable
module Make_plain_using_comparator : functor (Key : sig ... end) -> S_plain with type Key.t = Key.t with type Key.comparator_witness = Key.comparator_witness
module Make_using_comparator : functor (Key : sig ... end) -> S with type Key.t = Key.t with type Key.comparator_witness = Key.comparator_witness
module Make_binable : functor (Key : Key_binable) -> S_binable with type Key.t = Key.t
module Make_binable_using_comparator : functor (Key : sig ... end) -> S_binable with type Key.t = Key.t with type Key.comparator_witness = Key.comparator_witness
module Key_bin_io = Map_intf.Key_bin_io
include Map_intf.For_deriving with type ('a, 'b, 'c) t := ('a, 'b, 'c) t
include Base.Map.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 = 'k) -> ('v -> Base.Sexp.t) -> ('k, 'v, 'cmp) t -> Base.Sexp.t
val m__t_of_sexp : (module M_of_sexp with type comparator_witness = 'cmp and type t = 'k) -> (Base.Sexp.t -> 'v) -> Base.Sexp.t -> ('k, 'v, 'cmp) t
val m__t_sexp_grammar : Base.Sexp.Private.Raw_grammar.t
val compare_m__t : (module Compare_m) -> ('v -> 'v -> int) -> ('k, 'v, 'cmp) t -> ('k, 'v, 'cmp) t -> int
val equal_m__t : (module Equal_m) -> ('v -> 'v -> bool) -> ('k, 'v, 'cmp) t -> ('k, 'v, 'cmp) t -> bool
val hash_fold_m__t : (module Hash_fold_m with type t = 'k) -> (Base.Hash.state -> 'v -> Base.Hash.state) -> Base.Hash.state -> ('k, 'v, 'a) t -> Base.Hash.state
module M = Base.Map.M
val bin_shape_m__t : ('a, 'c) Map_intf.Key_bin_io.t -> Bin_prot.Shape.t -> Bin_prot.Shape.t
val bin_size_m__t : ('a, 'c) Map_intf.Key_bin_io.t -> 'b Bin_prot.Size.sizer -> ('a, 'b, 'c) t Bin_prot.Size.sizer
val bin_write_m__t : ('a, 'c) Map_intf.Key_bin_io.t -> 'b Bin_prot.Write.writer -> ('a, 'b, 'c) t Bin_prot.Write.writer
val bin_read_m__t : ('a, 'c) Map_intf.Key_bin_io.t -> 'b Bin_prot.Read.reader -> ('a, 'b, 'c) t Bin_prot.Read.reader
val __bin_read_m__t__ : ('a, 'c) Map_intf.Key_bin_io.t -> 'b Bin_prot.Read.reader -> (Core_kernel__.Import.int -> ('a, 'b, 'c) 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 = 'k) -> 'v Quickcheck.Generator.t -> ('k, 'v, 'cmp) t Quickcheck.Generator.t
val quickcheck_observer_m__t : (module Quickcheck_observer_m with type comparator_witness = 'cmp and type t = 'k) -> 'v Quickcheck.Observer.t -> ('k, 'v, 'cmp) t Quickcheck.Observer.t
val quickcheck_shrinker_m__t : (module Quickcheck_shrinker_m with type comparator_witness = 'cmp and type t = 'k) -> 'v Quickcheck.Shrinker.t -> ('k, 'v, 'cmp) t Quickcheck.Shrinker.t
module Stable : sig ... end
The following functors may be used to define stable modules