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
[root: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.
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.
change map key f updates the given map by changing the value stored under
f. Thus, for example, one might write:
change m k (function None -> Some 0 | Some x -> Some (x + 1))
to produce a new map where the integer stored under key
k is incremented by one
(treating an unknown key as zero).
returns the value bound to the given key, raising
Not_found if none such exists
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.
creates association list from map. No guarantee about order.
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
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
prev_key t k returns the largest (key, value) pair in t with key less than k
next_key t k returns the smallest (key, value) pair in t with key greater than k
rank t k if k is in t, returns the number of keys strictly less than k in t,
to_sequence ~keys_in t converts the map
t to a sequence of key-value pairs
in order and with keys according to