This module defines the Map
module for Core
. We use "core_map" as the file
name rather than "map" to avoid conflicts with OCaml's standard map module. In this
documentation, we use Map
to mean this module, not the OCaml standard one.
Map
is a functional datastructure (balanced binary tree) implementing finite maps
over a totally-ordered domain, called a "key". 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.
One 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
, one should strive to use the corresponding Key.Map
function, which will use the comparison function specifically for Key
. As a last
resort, if one does not have easy access to a comparison function for the keys in
one's map, use Map.Poly
to create the map. This will use OCaml's built-in
polymorphic comparison to compare keys, which has all the usual performance and
robustness problems that entails.
Parallel to the three kinds of map modules, 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, unlike a map. The main disadvantages of using trees
are needing to be more explicit about the comparator, and the possibility of
accidental use of polymorphic equality on a tree (for which maps dynamically detect
failure due to the presence of a closure in the data structure).
For a detailed explanation of the interface design, read on.
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 ) 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 are defined in the module type AccessorsN
(resp. CreatorsN
) in
Core_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 Tree : sig ... end
val invariants : (_, _, _) t ‑> Core_kernel__.Import.bool
Test if invariants of internal AVL search tree hold.
val comparator : ('a, _, 'cmp) t ‑> ('a, 'cmp) Core_kernel.Comparator.t
val singleton : comparator:('a, 'cmp) Core_kernel.Comparator.t ‑> 'a ‑> 'b ‑> ('a, 'b, 'cmp) t
map with one key, data pair
val of_alist : comparator:('a, 'cmp) Core_kernel.Comparator.t ‑> ('a * 'b) Core_kernel__.Import.list ‑> [ `Ok of ('a, 'b, 'cmp) t | `Duplicate_key of 'a ]
creates map from association list with unique keys
val of_alist_or_error : comparator:('a, 'cmp) Core_kernel.Comparator.t ‑> ('a * 'b) Core_kernel__.Import.list ‑> ('a, 'b, 'cmp) t Core_kernel.Or_error.t
creates map from association list with unique keys. Returns an error if duplicate 'a keys are found.
val of_alist_exn : comparator:('a, 'cmp) Core_kernel.Comparator.t ‑> ('a * 'b) Core_kernel__.Import.list ‑> ('a, 'b, 'cmp) t
creates map from association list with unique keys. Raises an exception if duplicate 'a keys are found.
val of_hashtbl_exn : comparator:('a, 'cmp) Core_kernel.Comparator.t ‑> ('a, 'b) Core_kernel__.Core_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 keys a1
and a2
in the table with
comparator.compare a1 a2 = 0
, which is only possible if the hash-table comparison
function is different than comparator.compare
. In the common case, the comparison
is the same, in which case of_hashtbl_exn
does not raise, regardless of the keys
present in the table.
val of_alist_multi : comparator:('a, 'cmp) Core_kernel.Comparator.t ‑> ('a * 'b) Core_kernel__.Import.list ‑> ('a, 'b Core_kernel__.Import.list, 'cmp) t
creates map from association list with possibly repeated keys.
val of_alist_fold : comparator:('a, 'cmp) Core_kernel.Comparator.t ‑> ('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 : comparator:('a, 'cmp) Core_kernel.Comparator.t ‑> ('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 : comparator:('a, 'cmp) Core_kernel.Comparator.t ‑> 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 like of_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 ~comparator ~f:(Hashtbl.iteri table)
.
It is faster than adding the elements one by one.
val of_tree : comparator:('k, 'cmp) Core_kernel.Comparator.t ‑> ('k, 'v, 'cmp) Tree.t ‑> ('k, 'v, 'cmp) t
Creates a t
from a Tree.t
and a Comparator.t
. This is an O(n) operation as it
must discover the length of the Tree.t
.
val of_sorted_array : comparator:('a, 'cmp) Core_kernel.Comparator.t ‑> ('a * 'b) Core_kernel__.Import.array ‑> ('a, 'b, 'cmp) t Core_kernel.Or_error.t
creates map from 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 do not hold, an error is returned.
val of_sorted_array_unchecked : comparator:('a, 'cmp) Core_kernel.Comparator.t ‑> ('a * 'b) Core_kernel__.Import.array ‑> ('a, 'b, 'cmp) t
Like of_sorted_array
except it returns a map with broken invariants when an Error
would have been returned.
val of_increasing_iterator_unchecked : comparator:('a, 'cmp) Core_kernel.Comparator.t ‑> len:Core_kernel__.Import.int ‑> f:(Core_kernel__.Import.int ‑> 'a * 'b) ‑> ('a, 'b, 'cmp) t
if_increasing_iterator_unchecked ~comparator ~len ~f
behaves like
of_sorted_array_unchecked ~comparator (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 length : (_, _, _) t ‑> Core_kernel__.Import.int
length map
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_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 on 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 key is present then remove its head element; if result is empty, remove the key.
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 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)
.
val update : ('k, 'v, 'cmp) t ‑> 'k ‑> f:('v Core_kernel__.Import.option ‑> 'v) ‑> ('k, 'v, 'cmp) t
update t key ~f
is change 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, raising Not_found
if none such exists
val find_exn : ('k, 'v, 'cmp) t ‑> 'k ‑> 'v
val mem : ('k, _, 'cmp) t ‑> 'k ‑> Core_kernel__.Import.bool
mem map key
tests whether map
contains a binding for key
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
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
Iterate two maps side by side. 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 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
filter
, filteri
, filter_keys
, filter_map
, and filter_mapi
run in O(n * lg n)
time; they simply accumulate each key & data retained by f
into a new map using
add
.
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 f applied to the bound values
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 ‑> [ `Fst of 'v2 | `Snd of 'v3 ]) ‑> ('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 result maps depending on its mapping in f
.
val partition_map : ('k, 'v1, 'cmp) t ‑> f:('v1 ‑> [ `Fst of 'v2 | `Snd of 'v3 ]) ‑> ('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 `Fst data
else `Snd 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 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 with
compare_direct
iff hash_fold_key
is compatible with (comparator m).compare
of the map m
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 maps m1
and m2
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 to_alist : ?key_order:[ `Increasing | `Decreasing ] ‑> ('k, 'v, _) t ‑> ('k * 'v) Core_kernel__.Import.list
creates association list from map.
val validate : name:('k ‑> Core_kernel__.Import.string) ‑> 'v Core_kernel__.Import.Validate.check ‑> ('k, 'v, _) t Core_kernel__.Import.Validate.check
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
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 Core_kernel.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.
val min_elt : ('k, 'v, _) t ‑> ('k * 'v) Core_kernel__.Import.option
min_elt map
(key, data)
pair corresponding to the minimum key in
map
, None if 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
(key, data)
pair corresponding to the maximum key in
map
, and None if map
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
same semantics as similar functions in List
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 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 ->
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 Core_kernel.Maybe_bound.t ‑> upper_bound:'k Core_kernel.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) 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 in t
with key
closest to
k
, which 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 ‑> 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
if k is in t, returns the number of keys strictly less than k in t,
otherwise None
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) Core_kernel.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. Cost is
O(log n) up front and amortized O(1) to produce each element.
val gen : comparator:('k, 'cmp) Core_kernel.Comparator.t ‑> 'k Core_kernel.Quickcheck.Generator.t ‑> 'v Core_kernel.Quickcheck.Generator.t ‑> ('k, 'v, 'cmp) t Core_kernel.Quickcheck.Generator.t
val obs : 'k Core_kernel.Quickcheck.Observer.t ‑> 'v Core_kernel.Quickcheck.Observer.t ‑> ('k, 'v, 'cmp) t Core_kernel.Quickcheck.Observer.t
val shrinker : 'k Core_kernel.Quickcheck.Shrinker.t ‑> 'v Core_kernel.Quickcheck.Shrinker.t ‑> ('k, 'v, 'cmp) t Core_kernel.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.
module type Key_plain = Core_kernel.Core_map_intf.Key_plain
module type Key = Core_kernel.Core_map_intf.Key
module type Key_binable = Core_kernel.Core_map_intf.Key_binable
module type S_plain = Core_kernel.Core_map_intf.S_plain
module type S = Core_kernel.Core_map_intf.S
module type S_binable = Core_kernel.Core_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