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 |
Key is any module defining values that can be used as keys of a map, like
String, etc. To add this functionality to an arbitrary module, use the
One should use
Map for functions that access existing maps, like
to_alist. For functions that create maps, like
of_alist, one should strive to use the corresponding
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
Key.Map.Tree. A tree is a bare representation of a map,
without the comparator. Thus tree operations need to obtain the comparator from
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
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
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
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
Depending on the number of type variables
N, the type of accessor (resp. creator)
functions are defined in the module type
Core_map_intf. Also for creators, when the comparison function is not fixed,
'cmp variable of
Map.t is free, we need to pass a comparator to the
function creating the map. The module type is called
There is also a module type
Accessors3_with_comparator in addition to
which used for trees since the comparator is not known.
Test if invariants of internal AVL search tree hold.
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.
Test whether a map is empty or not.
map. O(1), but
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
Iterate two maps side by side. Complexity of this function is O(M+N). If two inputs
(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
creates association list from map.
symmetric_diff t1 t2 ~data_equal returns a list of changes between
It is intended to be efficient in the case where
t2 share a large amount of
(key, data)pair corresponding to the minimum key in
map, None if empty.
(key, data)pair corresponding to the maximum key in
map, and None if
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
closest_key t dir k returns the
(key, value) pair in
key closest to
k, which satisfies the given inequality bound.
closest_key t `Less_than k would be the pair with the closest key to
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,
to_sequence ?order ?keys_greater_or_equal_to ?keys_less_or_equal_to t gives a
sequence of key-value pairs between
keys_greater_or_equal_to inclusive, presented in
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.