.TH "Map.S" 3o source: 2019-01-25 OCamldoc "OCaml library"
.SH NAME
Map.S \- Output signature of the functor Map.Make.
.SH Module type
Module type   Map.S
.SH Documentation
.sp
Module type
.BI "S"
 = 
.B sig  end

.sp
Output signature of the functor 
.B Map\&.Make
\&.

.sp

.sp
.sp
.I type key 

.sp
The type of the map keys\&.

.sp
.I type 
.B +'a
.I t 

.sp
The type of maps from type 
.B key
to type 
.B \&'a
\&.

.sp

.I val empty 
: 
.B 'a t
.sp
The empty map\&.

.sp

.I val is_empty 
: 
.B 'a t -> bool
.sp
Test whether a map is empty or not\&.

.sp

.I val mem 
: 
.B key -> 'a t -> bool
.sp

.B mem x m
returns 
.B true
if 
.B m
contains a binding for 
.B x
,
and 
.B false
otherwise\&.

.sp

.I val add 
: 
.B key -> 'a -> 'a t -> 'a t
.sp

.B add x y m
returns a map containing the same bindings as
.B m
, plus a binding of 
.B x
to 
.B y
\&. If 
.B x
was already bound
in 
.B m
to a value that is physically equal to 
.B y
,
.B m
is returned unchanged (the result of the function is
then physically equal to 
.B m
)\&. Otherwise, the previous binding
of 
.B x
in 
.B m
disappears\&.

.sp
.B "Before4.03"
Physical equality was not ensured\&.


.sp

.I val singleton 
: 
.B key -> 'a -> 'a t
.sp

.B singleton x y
returns the one\-element map that contains a binding 
.B y
for 
.B x
\&.

.sp
.B "Since"
3.12.0

.sp

.I val remove 
: 
.B key -> 'a t -> 'a t
.sp

.B remove x m
returns a map containing the same bindings as
.B m
, except for 
.B x
which is unbound in the returned map\&.
If 
.B x
was not in 
.B m
, 
.B m
is returned unchanged
(the result of the function is then physically equal to 
.B m
)\&.

.sp
.B "Before4.03"
Physical equality was not ensured\&.


.sp

.I val merge 
: 
.B (key -> 'a option -> 'b option -> 'c option) ->
.B   'a t -> 'b t -> 'c t
.sp

.B merge f m1 m2
computes a map whose keys is a subset of keys of 
.B m1
and of 
.B m2
\&. The presence of each such binding, and the corresponding
value, is determined with the function 
.B f
\&.
In terms of the 
.B find_opt
operation, we have
.B find_opt x (merge f m1 m2) = f (find_opt x m1) (find_opt x m2)
for any key 
.B x
, provided that 
.B f None None = None
\&.

.sp
.B "Since"
3.12.0

.sp

.I val union 
: 
.B (key -> 'a -> 'a -> 'a option) ->
.B   'a t -> 'a t -> 'a t
.sp

.B union f m1 m2
computes a map whose keys is the union of keys
of 
.B m1
and of 
.B m2
\&.  When the same binding is defined in both
arguments, the function 
.B f
is used to combine them\&.
This is a special case of 
.B merge
: 
.B union f m1 m2
is equivalent
to 
.B merge f\&' m1 m2
, where
.sp
\-
.B f\&' None None = None

.sp
\-
.B f\&' (Some v) None = Some v

.sp
\-
.B f\&' None (Some v) = Some v

.sp
\-
.B f\&' (Some v1) (Some v2) = f v1 v2



.sp
.B "Since"
4.03.0

.sp

.I val compare 
: 
.B ('a -> 'a -> int) -> 'a t -> 'a t -> int
.sp
Total ordering between maps\&.  The first argument is a total ordering
used to compare data associated with equal keys in the two maps\&.

.sp

.I val equal 
: 
.B ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
.sp

.B equal cmp m1 m2
tests whether the maps 
.B m1
and 
.B m2
are
equal, that is, contain equal keys and associate them with
equal data\&.  
.B cmp
is the equality predicate used to compare
the data associated with the keys\&.

.sp

.I val iter 
: 
.B (key -> 'a -> unit) -> 'a t -> unit
.sp

.B iter f m
applies 
.B f
to all bindings in map 
.B m
\&.
.B f
receives the key as first argument, and the associated value
as second argument\&.  The bindings are passed to 
.B f
in increasing
order with respect to the ordering over the type of the keys\&.

.sp

.I val fold 
: 
.B (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
.sp

.B fold f m a
computes 
.B (f kN dN \&.\&.\&. (f k1 d1 a)\&.\&.\&.)
,
where 
.B k1 \&.\&.\&. kN
are the keys of all bindings in 
.B m
(in increasing order), and 
.B d1 \&.\&.\&. dN
are the associated data\&.

.sp

.I val for_all 
: 
.B (key -> 'a -> bool) -> 'a t -> bool
.sp

.B for_all p m
checks if all the bindings of the map
satisfy the predicate 
.B p
\&.

.sp
.B "Since"
3.12.0

.sp

.I val exists 
: 
.B (key -> 'a -> bool) -> 'a t -> bool
.sp

.B exists p m
checks if at least one binding of the map
satisfies the predicate 
.B p
\&.

.sp
.B "Since"
3.12.0

.sp

.I val filter 
: 
.B (key -> 'a -> bool) -> 'a t -> 'a t
.sp

.B filter p m
returns the map with all the bindings in 
.B m
that satisfy predicate 
.B p
\&. If 
.B p
satisfies every binding in 
.B m
,
.B m
is returned unchanged (the result of the function is then
physically equal to 
.B m
)

.sp
.B "Before4.03"
Physical equality was not ensured\&.


.sp
.B "Since"
3.12.0

.sp

.I val partition 
: 
.B (key -> 'a -> bool) -> 'a t -> 'a t * 'a t
.sp

.B partition p m
returns a pair of maps 
.B (m1, m2)
, where
.B m1
contains all the bindings of 
.B s
that satisfy the
predicate 
.B p
, and 
.B m2
is the map with all the bindings of
.B s
that do not satisfy 
.B p
\&.

.sp
.B "Since"
3.12.0

.sp

.I val cardinal 
: 
.B 'a t -> int
.sp
Return the number of bindings of a map\&.

.sp
.B "Since"
3.12.0

.sp

.I val bindings 
: 
.B 'a t -> (key * 'a) list
.sp
Return the list of all bindings of the given map\&.
The returned list is sorted in increasing order with respect
to the ordering 
.B Ord\&.compare
, where 
.B Ord
is the argument
given to 
.B Map\&.Make
\&.

.sp
.B "Since"
3.12.0

.sp

.I val min_binding 
: 
.B 'a t -> key * 'a
.sp
Return the smallest binding of the given map
(with respect to the 
.B Ord\&.compare
ordering), or raise
.B Not_found
if the map is empty\&.

.sp
.B "Since"
3.12.0

.sp

.I val min_binding_opt 
: 
.B 'a t -> (key * 'a) option
.sp
Return the smallest binding of the given map
(with respect to the 
.B Ord\&.compare
ordering), or 
.B None
if the map is empty\&.

.sp
.B "Since"
4.05

.sp

.I val max_binding 
: 
.B 'a t -> key * 'a
.sp
Same as 
.B Map\&.S\&.min_binding
, but returns the largest binding
of the given map\&.

.sp
.B "Since"
3.12.0

.sp

.I val max_binding_opt 
: 
.B 'a t -> (key * 'a) option
.sp
Same as 
.B Map\&.S\&.min_binding_opt
, but returns the largest binding
of the given map\&.

.sp
.B "Since"
4.05

.sp

.I val choose 
: 
.B 'a t -> key * 'a
.sp
Return one binding of the given map, or raise 
.B Not_found
if
the map is empty\&. Which binding is chosen is unspecified,
but equal bindings will be chosen for equal maps\&.

.sp
.B "Since"
3.12.0

.sp

.I val choose_opt 
: 
.B 'a t -> (key * 'a) option
.sp
Return one binding of the given map, or 
.B None
if
the map is empty\&. Which binding is chosen is unspecified,
but equal bindings will be chosen for equal maps\&.

.sp
.B "Since"
4.05

.sp

.I val split 
: 
.B key -> 'a t -> 'a t * 'a option * 'a t
.sp

.B split x m
returns a triple 
.B (l, data, r)
, where
.B l
is the map with all the bindings of 
.B m
whose key
is strictly less than 
.B x
;
.B r
is the map with all the bindings of 
.B m
whose key
is strictly greater than 
.B x
;
.B data
is 
.B None
if 
.B m
contains no binding for 
.B x
,
or 
.B Some v
if 
.B m
binds 
.B v
to 
.B x
\&.

.sp
.B "Since"
3.12.0

.sp

.I val find 
: 
.B key -> 'a t -> 'a
.sp

.B find x m
returns the current binding of 
.B x
in 
.B m
,
or raises 
.B Not_found
if no such binding exists\&.

.sp

.I val find_opt 
: 
.B key -> 'a t -> 'a option
.sp

.B find_opt x m
returns 
.B Some v
if the current binding of 
.B x
in 
.B m
is 
.B v
, or 
.B None
if no such binding exists\&.

.sp
.B "Since"
4.05

.sp

.I val find_first 
: 
.B (key -> bool) -> 'a t -> key * 'a
.sp

.B find_first f m
, where 
.B f
is a monotonically increasing function,
returns the binding of 
.B m
with the lowest key 
.B k
such that 
.B f k
,
or raises 
.B Not_found
if no such key exists\&.
.sp
For example, 
.B find_first (fun k \-> Ord\&.compare k x >= 0) m
will return
the first binding 
.B k, v
of 
.B m
where 
.B Ord\&.compare k x >= 0
(intuitively: 
.B k >= x
), or raise 
.B Not_found
if 
.B x
is greater than any
element of 
.B m
\&.

.sp
.B "Since"
4.05

.sp

.I val find_first_opt 
: 
.B (key -> bool) -> 'a t -> (key * 'a) option
.sp

.B find_first_opt f m
, where 
.B f
is a monotonically increasing function,
returns an option containing the binding of 
.B m
with the lowest key 
.B k
such that 
.B f k
, or 
.B None
if no such key exists\&.

.sp
.B "Since"
4.05

.sp

.I val find_last 
: 
.B (key -> bool) -> 'a t -> key * 'a
.sp

.B find_last f m
, where 
.B f
is a monotonically decreasing function,
returns the binding of 
.B m
with the highest key 
.B k
such that 
.B f k
,
or raises 
.B Not_found
if no such key exists\&.

.sp
.B "Since"
4.05

.sp

.I val find_last_opt 
: 
.B (key -> bool) -> 'a t -> (key * 'a) option
.sp

.B find_last_opt f m
, where 
.B f
is a monotonically decreasing function,
returns an option containing the binding of 
.B m
with the highest key 
.B k
such that 
.B f k
, or 
.B None
if no such key exists\&.

.sp
.B "Since"
4.05

.sp

.I val map 
: 
.B ('a -> 'b) -> 'a t -> 'b t
.sp

.B map f m
returns a map with same domain as 
.B m
, where the
associated value 
.B a
of all bindings of 
.B m
has been
replaced by the result of the application of 
.B f
to 
.B a
\&.
The bindings are passed to 
.B f
in increasing order
with respect to the ordering over the type of the keys\&.

.sp

.I val mapi 
: 
.B (key -> 'a -> 'b) -> 'a t -> 'b t
.sp
Same as 
.B Map\&.S\&.map
, but the function receives as arguments both the
key and the associated value for each binding of the map\&.

.sp