This module defines the Map
module for Core.Std
. 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.
Test if invariants of internal AVL search tree hold.
creates map from association list with unique keys
creates map from association list with unique keys. Returns an error if duplicate 'a keys are found.
creates map from association list with unique keys. Raises an exception if duplicate 'a keys are found.
combines an association list into a map, folding together bound values with common keys
combines an association list into a map, reducing together bound values with common keys
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
.
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.
Like of_sorted_array
except behavior is undefined when an Error
would have been
returned.
Test whether a map is empty or not.
length map
map
. O(1), but Tree.length
is O(n).
returns the value bound to the given key, raising Not_found
if none such exists
mem map key
tests whether map
contains a binding for key
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)
folds over keys and data in map in increasing order of key.
folds over keys and data in map in decreasing order of key.
returns list of keys in map
returns list of data in map
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.
min_elt map
(key, data)
pair corresponding to the minimum key in
map
, None if empty.
max_elt map
(key, data)
pair corresponding to the maximum key in
map
, and None if map
is empty.
same semantics as similar functions in List
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).
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.
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.
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.
rank t k
if k is in t, returns the number of keys strictly less than k in t,
otherwise None
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.
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.