# package containers

Library

Module

Module type

Parameter

Class

Class type

## Parameters

`module O : Map.OrderedType`

## Signature

`include Map.S with type 'a t = 'a Map.Make(O).t with type key = O.t`

## Maps

`type key = O.t`

The type of the map keys.

`type 'a t = 'a Map.Make(O).t`

The type of maps from type `key`

to type `'a`

.

`val empty : 'a t`

The empty map.

`add key data m`

returns a map containing the same bindings as `m`

, plus a binding of `key`

to `data`

. If `key`

was already bound in `m`

to a value that is physically equal to `data`

, `m`

is returned unchanged (the result of the function is then physically equal to `m`

). Otherwise, the previous binding of `key`

in `m`

disappears.

`add_to_list key data m`

is `m`

with `key`

mapped to `l`

such that `l`

is `data :: Map.find key m`

if `key`

was bound in `m`

and `[v]`

otherwise.

`singleton x y`

returns the one-element map that contains a binding `y`

for `x`

.

`remove x m`

returns a map containing the same bindings as `m`

, except for `x`

which is unbound in the returned map. If `x`

was not in `m`

, `m`

is returned unchanged (the result of the function is then physically equal to `m`

).

`merge f m1 m2`

computes a map whose keys are a subset of the keys of `m1`

and of `m2`

. The presence of each such binding, and the corresponding value, is determined with the function `f`

. In terms of the `find_opt`

operation, we have `find_opt x (merge f m1 m2) = f x (find_opt x m1) (find_opt x m2)`

for any key `x`

, provided that `f x None None = None`

.

`union f m1 m2`

computes a map whose keys are a subset of the keys of `m1`

and of `m2`

. When the same binding is defined in both arguments, the function `f`

is used to combine them. This is a special case of `merge`

: `union f m1 m2`

is equivalent to `merge f' m1 m2`

, where

`f' _key None None = None`

`f' _key (Some v) None = Some v`

`f' _key None (Some v) = Some v`

`f' key (Some v1) (Some v2) = f key v1 v2`

`val cardinal : 'a t -> int`

Return the number of bindings of a map.

## Bindings

Return the list of all bindings of the given map. The returned list is sorted in increasing order of keys with respect to the ordering `Ord.compare`

, where `Ord`

is the argument given to `Map.Make`

.

Return the binding with the smallest key in a given map (with respect to the `Ord.compare`

ordering), or raise `Not_found`

if the map is empty.

Same as `min_binding`

, but returns the binding with the largest key in the given map.

Return one binding of the given map, or raise `Not_found`

if the map is empty. Which binding is chosen is unspecified, but equal bindings will be chosen for equal maps.

## Searching

`find x m`

returns the current value of `x`

in `m`

, or raises `Not_found`

if no binding for `x`

exists.

`find_last f m`

, where `f`

is a monotonically decreasing function, returns the binding of `m`

with the highest key `k`

such that `f k`

, or raises `Not_found`

if no such key exists.

`find_last_opt f m`

, where `f`

is a monotonically decreasing function, returns an option containing the binding of `m`

with the highest key `k`

such that `f k`

, or `None`

if no such key exists.

## Traversing

`iter f m`

applies `f`

to all bindings in map `m`

. `f`

receives the key as first argument, and the associated value as second argument. The bindings are passed to `f`

in increasing order with respect to the ordering over the type of the keys.

`fold f m init`

computes `(f kN dN ... (f k1 d1 init)...)`

, where `k1 ... kN`

are the keys of all bindings in `m`

(in increasing order), and `d1 ... dN`

are the associated data.

## Transforming

`map f m`

returns a map with same domain as `m`

, where the associated value `a`

of all bindings of `m`

has been replaced by the result of the application of `f`

to `a`

. The bindings are passed to `f`

in increasing order with respect to the ordering over the type of the keys.

Same as `map`

, but the function receives as arguments both the key and the associated value for each binding of the map.

`filter f m`

returns the map with all the bindings in `m`

that satisfy predicate `p`

. If every binding in `m`

satisfies `f`

, `m`

is returned unchanged (the result of the function is then physically equal to `m`

)

`filter_map f m`

applies the function `f`

to every binding of `m`

, and builds a map from the results. For each binding `(k, v)`

in the input map:

- if
`f k v`

is`None`

then`k`

is not in the result, - if
`f k v`

is`Some v'`

then the binding`(k, v')`

is in the output map.

For example, the following function on maps whose values are lists

```
filter_map
(fun _k li -> match li with [] -> None | _::tl -> Some tl)
m
```

drops all bindings of `m`

whose value is an empty list, and pops the first element of each value that is non-empty.

`partition f m`

returns a pair of maps `(m1, m2)`

, where `m1`

contains all the bindings of `m`

that satisfy the predicate `f`

, and `m2`

is the map with all the bindings of `m`

that do not satisfy `f`

.

`split x m`

returns a triple `(l, data, r)`

, where `l`

is the map with all the bindings of `m`

whose key is strictly less than `x`

; `r`

is the map with all the bindings of `m`

whose key is strictly greater than `x`

; `data`

is `None`

if `m`

contains no binding for `x`

, or `Some v`

if `m`

binds `v`

to `x`

.

## Predicates and comparisons

`val is_empty : 'a t -> bool`

Test whether a map is empty or not.

`mem x m`

returns `true`

if `m`

contains a binding for `x`

, and `false`

otherwise.

`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.

Total ordering between maps. The first argument is a total ordering used to compare data associated with equal keys in the two maps.

`for_all f m`

checks if all the bindings of the map satisfy the predicate `f`

.

`exists f m`

checks if at least one binding of the map satisfies the predicate `f`

.

## Converting

`get k m`

returns `Some v`

if the current binding of `k`

in `m`

is `v`

, or `None`

if the key `k`

is not present. Safe version of `find`

.

`get_or k m ~default`

returns the value associated to `k`

if present, and returns `default`

otherwise (if `k`

doesn't belong in `m`

).

`update k f m`

calls `f (Some v)`

if `find k m = v`

, otherwise it calls `f None`

. In any case, if the result is `None`

`k`

is removed from `m`

, and if the result is `Some v'`

then `add k v' m`

is returned.

`choose_opt m`

returns one binding of the given map `m`

, or `None`

if `m`

is empty. Safe version of `choose`

.

`min_binding_opt m`

returns the smallest binding of the given map `m`

, or `None`

if `m`

is empty. Safe version of `min_binding`

.

`max_binding_opt m`

returns the largest binding of the given map `m`

, or `None`

if `m`

is empty. Safe version of `max_binding`

.

`find_opt k m`

returns `Some v`

if the current binding of `k`

in `m`

is `v`

, or `None`

if the key `k`

is not present. Safe version of `find`

.

`find_first f m`

where `f`

is a monotonically increasing function, returns the binding of `m`

with the lowest key `k`

such that `f k`

, or raises `Not_found`

if no such key exists. See `Map.S.find_first`

.

`find_first_opt f m`

where `f`

is a monotonically increasing function, returns an option containing the binding of `m`

with the lowest key `k`

such that `f k`

, or `None`

if no such key exists. Safe version of `find_first`

.

```
val merge_safe :
f:(key -> [ `Left of 'a | `Right of 'b | `Both of 'a * 'b ] -> 'c option) ->
'a t ->
'b t ->
'c t
```

`merge_safe ~f a b`

merges the maps `a`

and `b`

together.

`add_seq m seq`

adds the given `Seq.t`

of bindings to the map `m`

. Like `add_list`

. Renamed from `add_std_seq`

since 3.0.

`add_seq ~f m l`

adds the given seq `l`

of bindings to the map `m`

, using `f`

to combine values that have the same key. If a key occurs several times, all its bindings are combined using the function `f`

, with `f key v1 v2`

being called with `v1`

occurring later in the seq than `v2`

.

`of_seq seq`

builds a map from the given `Seq.t`

of bindings. Like `of_list`

. Renamed from `of_std_seq`

since 3.0.

`of_seq_with ~f l`

builds a map from the given seq `l`

of bindings `k_i -> v_i`

, added in order using `add`

. If a key occurs several times, all its bindings are combined using the function `f`

, with `f key v1 v2`

being called with `v1`

occurring later in the seq than `v2`

.

`add_iter m iter`

adds the given `iter`

of bindings to the map `m`

. Like `add_list`

.

`add_iter ~f m l`

adds the given iter `l`

of bindings to the map `m`

, using `f`

to combine values that have the same key. If a key occurs several times, all its bindings are combined using the function `f`

, with `f key v1 v2`

being called with `v1`

occurring later in the seq than `v2`

.

`of_iter iter`

builds a map from the given `iter`

of bindings. Like `of_list`

.

`of_iter_with ~f l`

builds a map from the given iter `l`

of bindings `k_i -> v_i`

, added in order using `add`

. If a key occurs several times, all its bindings are combined using the function `f`

, with `f key v1 v2`

being called with `v1`

occurring later in the iter than `v2`

.

`to_iter m`

iterates on the whole map `m`

, creating an `iter`

of bindings. Like `to_list`

.

`of_list l`

builds a map from the given list `l`

of bindings `k_i -> v_i`

, added in order using `add`

. If a key occurs several times, only its last binding will be present in the result.

`of_list_with ~f l`

builds a map from the given list `l`

of bindings `k_i -> v_i`

, added in order using `add`

. If a key occurs several times, all its bindings are combined using the function `f`

, with `f key v1 v2`

being called with `v1`

occurring later in the list than `v2`

.

`add_list m l`

adds the given list `l`

of bindings to the map `m`

.

`add_list ~f m l`

adds the given list `l`

of bindings to the map `m`

, using `f`

to combine values that have the same key. If a key occurs several times, all its bindings are combined using the function `f`

, with `f key v1 v2`

being called with `v1`

occurring later in the seq than `v2`

.

`to_list m`

builds a list of the bindings of the given map `m`

. The order is unspecified.