map: association tables over ordered types
This module implements applicative association tables, also known as
finite maps or dictionaries, given a total ordering function
over the keys.
All operations over maps are purely applicative (no side-effects).
The implementation uses balanced binary trees, and therefore searching
and insertion take time logarithmic in the size of the map.
type ('a, 'b) t
The type of maps from type 'a to type 'b.
value empty: ('a -> 'a -> int) -> ('a, 'b) t
The empty map.
The argument is a total ordering function over the set elements.
This is a two-argument function f such that
f e1 e2 is zero if the elements e1 and e2 are equal,
f e1 e2 is strictly negative if e1 is smaller than e2,
and f e1 e2 is strictly positive if e1 is greater than e2.
Examples: a suitable ordering function for type int
is prefix -. You can also use the generic structural comparison
value add: 'a -> 'b -> ('a, 'b) t -> ('a, 'b) t
add x y m returns a map containing the same bindings as
m, plus a binding of x to y. Previous bindings for x
in m are not removed, but simply hidden: they reappear
after performing a remove operation.
(This is the semantics of association lists.)
value find:'a -> ('a, 'b) t -> 'b
find x m returns the current binding of x in m,
or raises Not_found if no such binding exists.
value remove: 'a -> ('a, 'b) t -> ('a, 'b) t
remove x m returns a map containing the same bindings
as m except the current binding for x. The previous
binding for x is restored if it exists. m is returned
unchanged if x is not bound in m.
value iter: ('a -> 'b -> unit) -> ('a, 'b) t -> unit
iter f m applies f to all bindings in map m,
discarding the results.
f receives the key as first argument, and the associated value
as second argument. The order in which the bindings are passed to
f is unspecified. Only current bindings are presented to f:
bindings hidden by more recent bindings are not passed to f.