1Map.S(3) OCaml library Map.S(3)
2
6 Map.S - Output signature of the functor Map.Make.
7
9 Module type Map.S
10
12 Module type S
13 = sig end
14 Output signature of the functor Map.Make .
17 type key
23 The type of the map keys.
26 type +'a t
29 The type of maps from type key to type 'a .
32 val empty : 'a t
36 The empty map.
38 val is_empty : 'a t -> bool
42 Test whether a map is empty or not.
44 val mem : key -> 'a t -> bool
48 mem x m returns true if m contains a binding for x , and false other‐
51 wise.
52 val add : key -> 'a -> 'a t -> 'a t
56 add x y m returns a map containing the same bindings as m , plus a
59 binding of x to y . If x was already bound in m to a value that is
60 physically equal to y , m is returned unchanged (the result of the
61 function is then physically equal to m ). Otherwise, the previous bind‐
62 ing of x in m disappears.
63 Before4.03 Physical equality was not ensured.
66 val update : key -> ('a option -> 'a option) -> 'a t -> 'a t
71 update x f m returns a map containing the same bindings as m , except
74 for the binding of x . Depending on the value of y where y is f
75 (find_opt x m) , the binding of x is added, removed or updated. If y is
76 None , the binding is removed if it exists; otherwise, if y is Some z
77 then x is associated to z in the resulting map. If x was already bound
78 in m to a value that is physically equal to z , m is returned unchanged
79 (the result of the function is then physically equal to m ).
80 Since 4.06.0
83 val singleton : key -> 'a -> 'a t
87 singleton x y returns the one-element map that contains a binding y for
90 x .
91 Since 3.12.0
94 val remove : key -> 'a t -> 'a t
98 remove x m returns a map containing the same bindings as m , except for
101 x which is unbound in the returned map. If x was not in m , m is re‐
102 turned unchanged (the result of the function is then physically equal
103 to m ).
104 Before4.03 Physical equality was not ensured.
107 val merge : (key -> 'a option -> 'b option -> 'c option) -> 'a t -> 'b
112 t -> 'c t
113 merge f m1 m2 computes a map whose keys are a subset of the keys of m1
116 and of m2 . The presence of each such binding, and the corresponding
117 value, is determined with the function f . In terms of the find_opt
118 operation, we have find_opt x (merge f m1 m2) = f x (find_opt x m1)
119 (find_opt x m2) for any key x , provided that f x None None = None .
120 Since 3.12.0
123 val union : (key -> 'a -> 'a -> 'a option) -> 'a t -> 'a t -> 'a t
127 union f m1 m2 computes a map whose keys are a subset of the keys of m1
130 and of m2 . When the same binding is defined in both arguments, the
131 function f is used to combine them. This is a special case of merge :
132 union f m1 m2 is equivalent to merge f' m1 m2 , where
133 - f' _key None None = None
135 - f' _key (Some v) None = Some v
138 - f' _key None (Some v) = Some v
141 - f' key (Some v1) (Some v2) = f key v1 v2
144 Since 4.03.0
149 val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int
153 Total ordering between maps. The first argument is a total ordering
155 used to compare data associated with equal keys in the two maps.
156 val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
160 equal cmp m1 m2 tests whether the maps m1 and m2 are equal, that is,
163 contain equal keys and associate them with equal data. cmp is the
164 equality predicate used to compare the data associated with the keys.
165 val iter : (key -> 'a -> unit) -> 'a t -> unit
169 iter f m applies f to all bindings in map m . f receives the key as
172 first argument, and the associated value as second argument. The bind‐
173 ings are passed to f in increasing order with respect to the ordering
174 over the type of the keys.
175 val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
179 fold f m a computes (f kN dN ... (f k1 d1 a)...) , where k1 ... kN are
182 the keys of all bindings in m (in increasing order), and d1 ... dN are
183 the associated data.
184 val for_all : (key -> 'a -> bool) -> 'a t -> bool
188 for_all p m checks if all the bindings of the map satisfy the predicate
191 p .
192 Since 3.12.0
195 val exists : (key -> 'a -> bool) -> 'a t -> bool
199 exists p m checks if at least one binding of the map satisfies the
202 predicate p .
203 Since 3.12.0
206 val filter : (key -> 'a -> bool) -> 'a t -> 'a t
210 filter p m returns the map with all the bindings in m that satisfy
213 predicate p . If every binding in m satisfies p , m is returned un‐
214 changed (the result of the function is then physically equal to m )
215 Before4.03 Physical equality was not ensured.
218 Since 3.12.0
222 val filter_map : (key -> 'a -> 'b option) -> 'a t -> 'b t
226 filter_map f m applies the function f to every binding of m , and
229 builds a map from the results. For each binding (k, v) in the input
230 map:
231 -if f k v is None then k is not in the result,
233 -if f k v is Some v' then the binding (k, v') is in the output map.
235 For example, the following function on maps whose values are lists
237 filter_map
238 (fun _k li -> match li with [] -> None | _::tl -> Some tl)
239 m
240 drops all bindings of m whose value is an empty list, and pops the
242 first element of each value that is non-empty.
243 Since 4.11.0
246 val partition : (key -> 'a -> bool) -> 'a t -> 'a t * 'a t
250 partition p m returns a pair of maps (m1, m2) , where m1 contains all
253 the bindings of m that satisfy the predicate p , and m2 is the map with
254 all the bindings of m that do not satisfy p .
255 Since 3.12.0
258 val cardinal : 'a t -> int
262 Return the number of bindings of a map.
264 Since 3.12.0
267 val bindings : 'a t -> (key * 'a) list
271 Return the list of all bindings of the given map. The returned list is
273 sorted in increasing order of keys with respect to the ordering
274 Ord.compare , where Ord is the argument given to Map.Make .
275 Since 3.12.0
278 val min_binding : 'a t -> key * 'a
282 Return the binding with the smallest key in a given map (with respect
284 to the Ord.compare ordering), or raise Not_found if the map is empty.
285 Since 3.12.0
288 val min_binding_opt : 'a t -> (key * 'a) option
292 Return the binding with the smallest key in the given map (with respect
294 to the Ord.compare ordering), or None if the map is empty.
295 Since 4.05
298 val max_binding : 'a t -> key * 'a
302 Same as Map.S.min_binding , but returns the binding with the largest
304 key in the given map.
305 Since 3.12.0
308 val max_binding_opt : 'a t -> (key * 'a) option
312 Same as Map.S.min_binding_opt , but returns the binding with the
314 largest key in the given map.
315 Since 4.05
318 val choose : 'a t -> key * 'a
322 Return one binding of the given map, or raise Not_found if the map is
324 empty. Which binding is chosen is unspecified, but equal bindings will
325 be chosen for equal maps.
326 Since 3.12.0
329 val choose_opt : 'a t -> (key * 'a) option
333 Return one binding of the given map, or None if the map is empty. Which
335 binding is chosen is unspecified, but equal bindings will be chosen for
336 equal maps.
337 Since 4.05
340 val split : key -> 'a t -> 'a t * 'a option * 'a t
344 split x m returns a triple (l, data, r) , where l is the map with all
347 the bindings of m whose key is strictly less than x ; r is the map with
348 all the bindings of m whose key is strictly greater than x ; data is
349 None if m contains no binding for x , or Some v if m binds v to x .
350 Since 3.12.0
353 val find : key -> 'a t -> 'a
357 find x m returns the current value of x in m , or raises Not_found if
360 no binding for x exists.
361 val find_opt : key -> 'a t -> 'a option
365 find_opt x m returns Some v if the current value of x in m is v , or
368 None if no binding for x exists.
369 Since 4.05
372 val find_first : (key -> bool) -> 'a t -> key * 'a
376 find_first f m , where f is a monotonically increasing function, re‐
379 turns the binding of m with the lowest key k such that f k , or raises
380 Not_found if no such key exists.
381 For example, find_first (fun k -> Ord.compare k x >= 0) m will return
383 the first binding k, v of m where Ord.compare k x >= 0 (intuitively: k
384 >= x ), or raise Not_found if x is greater than any element of m .
385 Since 4.05
388 val find_first_opt : (key -> bool) -> 'a t -> (key * 'a) option
392 find_first_opt f m , where f is a monotonically increasing function,
395 returns an option containing the binding of m with the lowest key k
396 such that f k , or None if no such key exists.
397 Since 4.05
400 val find_last : (key -> bool) -> 'a t -> key * 'a
404 find_last f m , where f is a monotonically decreasing function, returns
407 the binding of m with the highest key k such that f k , or raises
408 Not_found if no such key exists.
409 Since 4.05
412 val find_last_opt : (key -> bool) -> 'a t -> (key * 'a) option
416 find_last_opt f m , where f is a monotonically decreasing function, re‐
419 turns an option containing the binding of m with the highest key k such
420 that f k , or None if no such key exists.
421 Since 4.05
424 val map : ('a -> 'b) -> 'a t -> 'b t
428 map f m returns a map with same domain as m , where the associated
431 value a of all bindings of m has been replaced by the result of the ap‐
432 plication of f to a . The bindings are passed to f in increasing order
433 with respect to the ordering over the type of the keys.
434 val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t
438 Same as Map.S.map , but the function receives as arguments both the key
440 and the associated value for each binding of the map.
441 Iterators
446 val to_seq : 'a t -> (key * 'a) Seq.t
447 Iterate on the whole map, in ascending order of keys
449 Since 4.07
452 val to_seq_from : key -> 'a t -> (key * 'a) Seq.t
456 to_seq_from k m iterates on a subset of the bindings of m , in ascend‐
459 ing order of keys, from key k or above.
460 Since 4.07
463 val add_seq : (key * 'a) Seq.t -> 'a t -> 'a t
467 Add the given bindings to the map, in order.
469 Since 4.07
472 val of_seq : (key * 'a) Seq.t -> 'a t
476 Build a map from the given bindings
478 Since 4.07
481OCamldoc 2021-01-26 Map.S(3)