module Core_map:sig
..end
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
, ...
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
type ('key, +'value, 'cmp)
t
val invariants : ('a, 'b, 'c) t -> bool
val comparator : ('a, 'b, 'cmp) t -> ('a, 'cmp) Comparator.t
val empty : comparator:('a, 'cmp) Comparator.t -> ('a, 'b, 'cmp) t
val singleton : comparator:('a, 'cmp) Comparator.t -> 'a -> 'b -> ('a, 'b, 'cmp) t
val of_alist : comparator:('a, 'cmp) Comparator.t ->
('a * 'b) list -> [ `Duplicate_key of 'a | `Ok of ('a, 'b, 'cmp) t ]
val of_alist_exn : comparator:('a, 'cmp) Comparator.t ->
('a * 'b) list -> ('a, 'b, 'cmp) t
val of_alist_multi : comparator:('a, 'cmp) Comparator.t ->
('a * 'b) list -> ('a, 'b list, 'cmp) t
val of_alist_fold : comparator:('a, 'cmp) Comparator.t ->
('a * 'b) list -> init:'c -> f:('c -> 'b -> 'c) -> ('a, 'c, 'cmp) t
val to_tree : ('k, 'v, 'cmp) t -> ('k, 'v, 'cmp) Tree.t
val of_tree : comparator:('k, 'cmp) Comparator.t ->
('k, 'v, 'cmp) Tree.t -> ('k, 'v, 'cmp) t
val of_sorted_array : comparator:('a, 'cmp) Comparator.t ->
('a * 'b) array -> ('a, 'b, 'cmp) t Or_error.t
val of_sorted_array_unchecked : comparator:('a, 'cmp) Comparator.t ->
('a * 'b) array -> ('a, 'b, 'cmp) t
of_sorted_array
except behavior is undefined when an Error
would have been
returned.val is_empty : ('a, 'b, 'c) t -> bool
val length : ('a, 'b, 'c) t -> int
length map
map
.val add : ('k, 'v, 'cmp) t -> key:'k -> data:'v -> ('k, 'v, 'cmp) t
val add_multi : ('k, 'v list, 'cmp) t ->
key:'k -> data:'v -> ('k, 'v list, 'cmp) t
val change : ('k, 'v, 'cmp) t ->
'k -> ('v option -> 'v option) -> ('k, 'v, 'cmp) t
change map key f
updates the given map by changing the value stored under key
according to 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).
val find : ('k, 'v, 'cmp) t -> 'k -> 'v option
Not_found
if none such existsval find_exn : ('k, 'v, 'cmp) t -> 'k -> 'v
val remove : ('k, 'v, 'cmp) t -> 'k -> ('k, 'v, 'cmp) t
val mem : ('k, 'a, 'cmp) t -> 'k -> bool
mem map key
tests whether map
contains a binding for key
val iter : ('k, 'v, 'a) t -> f:(key:'k -> data:'v -> unit) -> unit
val iter2 : ('k, 'v1, 'cmp) t ->
('k, 'v2, 'cmp) t ->
f:(key:'k ->
data:[ `Both of 'v1 * 'v2 | `Left of 'v1 | `Right of 'v2 ] -> unit) ->
unit
(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
val mapi : ('k, 'v1, 'cmp) t ->
f:(key:'k -> data:'v1 -> 'v2) -> ('k, 'v2, 'cmp) t
map
, but function takes both key and data as argumentsval fold : ('k, 'v, 'b) t -> init:'a -> f:(key:'k -> data:'v -> 'a -> 'a) -> 'a
val fold_right : ('k, 'v, 'b) t -> init:'a -> f:(key:'k -> data:'v -> 'a -> 'a) -> 'a
val filter : ('k, 'v, 'cmp) t ->
f:(key:'k -> data:'v -> bool) -> ('k, 'v, 'cmp) t
val filter_map : ('k, 'v1, 'cmp) t ->
f:('v1 -> 'v2 option) -> ('k, 'v2, 'cmp) t
val filter_mapi : ('k, 'v1, 'cmp) t ->
f:(key:'k -> data:'v1 -> 'v2 option) -> ('k, 'v2, 'cmp) t
filter_map
, but function takes both key and data as argumentsval compare_direct : ('v -> 'v -> int) ->
('k, 'v, 'cmp) t -> ('k, 'v, 'cmp) t -> int
val equal : ('v -> 'v -> bool) ->
('k, 'v, 'cmp) t -> ('k, 'v, 'cmp) t -> 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 keys : ('k, 'a, 'b) t -> 'k list
val data : ('a, 'v, 'b) t -> 'v list
val to_alist : ('k, 'v, 'a) t -> ('k * 'v) list
val validate : name:('k -> string) ->
'v Validate.check -> ('k, 'v, 'a) t Validate.check
val merge : ('k, 'v1, 'cmp) t ->
('k, 'v2, 'cmp) t ->
f:(key:'k ->
[ `Both of 'v1 * 'v2 | `Left of 'v1 | `Right of 'v2 ] -> 'v3 option) ->
('k, 'v3, 'cmp) t
val symmetric_diff : ('k, 'v, 'cmp) t ->
('k, 'v, 'cmp) t ->
data_equal:('v -> 'v -> bool) ->
('k * [ `Left of 'v | `Right of 'v | `Unequal of 'v * 'v ]) list
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.val min_elt : ('k, 'v, 'a) t -> ('k * 'v) option
min_elt map
(key, data)
pair corresponding to the minimum key in
map
, None if empty.val min_elt_exn : ('k, 'v, 'a) t -> 'k * 'v
val max_elt : ('k, 'v, 'a) t -> ('k * 'v) 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, 'a) t -> 'k * 'v
val for_all : ('k, 'v, 'a) t -> f:('v -> bool) -> bool
val exists : ('k, 'v, 'a) t -> f:('v -> bool) -> bool
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) 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 prev_key : ('k, 'v, 'cmp) t -> 'k -> ('k * 'v) option
prev_key t k
returns the largest (key, value) pair in t with key less than kval next_key : ('k, 'v, 'cmp) t -> 'k -> ('k * 'v) option
next_key t k
returns the smallest (key, value) pair in t with key greater than kval rank : ('k, 'v, 'cmp) t -> 'k -> int option
rank t k
if k is in t, returns the number of keys strictly less than k in t,
otherwise Nonemodule Poly:sig
..end
with type ('a, 'b, 'c) map = ('a, 'b, 'c) t
module type Key = Core_map_intf.Key
module type Key_binable = Core_map_intf.Key_binable
module type S =S
with type ('a, 'b, 'c) map := ('a, 'b, 'c) t
with type ('a, 'b, 'c) tree := ('a, 'b, 'c) Tree.t
module type S_binable =S_binable
with type ('a, 'b, 'c) map := ('a, 'b, 'c) t
with type ('a, 'b, 'c) tree := ('a, 'b, 'c) Tree.t
module Make:
module Make_using_comparator:
module Make_binable:
module Make_binable_using_comparator:functor (
Key
:
Comparator.S_binable
) ->
S_binable
with type Key.t = Key.t
with type Key.comparator = Key.comparator