1MoreLabels.Map.Make(3) OCaml library MoreLabels.Map.Make(3)
2
6 MoreLabels.Map.Make - Functor building an implementation of the map
7 structure given a totally ordered type.
8
10 Module MoreLabels.Map.Make
11
13 Module Make
14 : functor (Ord : OrderedType) -> sig end
15 Functor building an implementation of the map structure given a totally
18 ordered type.
19 Parameters:
22 "Ord"
24 MoreLabels.Map.OrderedType
26 type key
34 The type of the map keys.
37 type +'a t
40 The type of maps from type key to type 'a .
43 val empty : 'a t
47 The empty map.
49 val is_empty : 'a t -> bool
53 Test whether a map is empty or not.
55 val mem : key -> 'a t -> bool
59 mem x m returns true if m contains a binding for x , and false other‐
62 wise.
63 val add : key:key -> data:'a -> 'a t -> 'a t
67 add ~key ~data m returns a map containing the same bindings as m , plus
70 a binding of key to data . If key was already bound in m to a value
71 that is physically equal to data , m is returned unchanged (the result
72 of the function is then physically equal to m ). Otherwise, the previ‐
73 ous binding of key in m disappears.
74 Before4.03 Physical equality was not ensured.
77 val update : key:key -> f:('a option -> 'a option) -> 'a t -> 'a t
82 update ~key ~f m returns a map containing the same bindings as m , ex‐
85 cept for the binding of key . Depending on the value of y where y is f
86 (find_opt key m) , the binding of key is added, removed or updated. If
87 y is None , the binding is removed if it exists; otherwise, if y is
88 Some z then key is associated to z in the resulting map. If key was
89 already bound in m to a value that is physically equal to z , m is re‐
90 turned unchanged (the result of the function is then physically equal
91 to m ).
92 Since 4.06.0
95 val singleton : key -> 'a -> 'a t
99 singleton x y returns the one-element map that contains a binding y for
102 x .
103 Since 3.12.0
106 val remove : key -> 'a t -> 'a t
110 remove x m returns a map containing the same bindings as m , except for
113 x which is unbound in the returned map. If x was not in m , m is re‐
114 turned unchanged (the result of the function is then physically equal
115 to m ).
116 Before4.03 Physical equality was not ensured.
119 val merge : f:(key -> 'a option -> 'b option -> 'c option) -> 'a t ->
124 'b t -> 'c t
125 merge ~f m1 m2 computes a map whose keys are a subset of the keys of m1
128 and of m2 . The presence of each such binding, and the corresponding
129 value, is determined with the function f . In terms of the find_opt
130 operation, we have find_opt x (merge f m1 m2) = f x (find_opt x m1)
131 (find_opt x m2) for any key x , provided that f x None None = None .
132 Since 3.12.0
135 val union : f:(key -> 'a -> 'a -> 'a option) -> 'a t -> 'a t -> 'a t
139 union ~f m1 m2 computes a map whose keys are a subset of the keys of m1
142 and of m2 . When the same binding is defined in both arguments, the
143 function f is used to combine them. This is a special case of merge :
144 union f m1 m2 is equivalent to merge f' m1 m2 , where
145 - f' _key None None = None
147 - f' _key (Some v) None = Some v
150 - f' _key None (Some v) = Some v
153 - f' key (Some v1) (Some v2) = f key v1 v2
156 Since 4.03.0
161 val compare : cmp:('a -> 'a -> int) -> 'a t -> 'a t -> int
165 Total ordering between maps. The first argument is a total ordering
167 used to compare data associated with equal keys in the two maps.
168 val equal : cmp:('a -> 'a -> bool) -> 'a t -> 'a t -> bool
172 equal ~cmp m1 m2 tests whether the maps m1 and m2 are equal, that is,
175 contain equal keys and associate them with equal data. cmp is the
176 equality predicate used to compare the data associated with the keys.
177 val iter : f:(key:key -> data:'a -> unit) -> 'a t -> unit
181 iter ~f m applies f to all bindings in map m . f receives the key as
184 first argument, and the associated value as second argument. The bind‐
185 ings are passed to f in increasing order with respect to the ordering
186 over the type of the keys.
187 val fold : f:(key:key -> data:'a -> 'b -> 'b) -> 'a t -> init:'b -> 'b
191 fold ~f m ~init computes (f kN dN ... (f k1 d1 init)...) , where k1
194 ... kN are the keys of all bindings in m (in increasing order), and d1
195 ... dN are the associated data.
196 val for_all : f:(key -> 'a -> bool) -> 'a t -> bool
200 for_all ~f m checks if all the bindings of the map satisfy the predi‐
203 cate f .
204 Since 3.12.0
207 val exists : f:(key -> 'a -> bool) -> 'a t -> bool
211 exists ~f m checks if at least one binding of the map satisfies the
214 predicate f .
215 Since 3.12.0
218 val filter : f:(key -> 'a -> bool) -> 'a t -> 'a t
222 filter ~f m returns the map with all the bindings in m that satisfy
225 predicate p . If every binding in m satisfies f , m is returned un‐
226 changed (the result of the function is then physically equal to m )
227 Before4.03 Physical equality was not ensured.
230 Since 3.12.0
234 val filter_map : f:(key -> 'a -> 'b option) -> 'a t -> 'b t
238 filter_map ~f m applies the function f to every binding of m , and
241 builds a map from the results. For each binding (k, v) in the input
242 map:
243 -if f k v is None then k is not in the result,
245 -if f k v is Some v' then the binding (k, v') is in the output map.
247 For example, the following function on maps whose values are lists
249 filter_map
250 (fun _k li -> match li with [] -> None | _::tl -> Some tl)
251 m
252 drops all bindings of m whose value is an empty list, and pops the
254 first element of each value that is non-empty.
255 Since 4.11.0
258 val partition : f:(key -> 'a -> bool) -> 'a t -> 'a t * 'a t
262 partition ~f m returns a pair of maps (m1, m2) , where m1 contains all
265 the bindings of m that satisfy the predicate f , and m2 is the map with
266 all the bindings of m that do not satisfy f .
267 Since 3.12.0
270 val cardinal : 'a t -> int
274 Return the number of bindings of a map.
276 Since 3.12.0
279 val bindings : 'a t -> (key * 'a) list
283 Return the list of all bindings of the given map. The returned list is
285 sorted in increasing order of keys with respect to the ordering
286 Ord.compare , where Ord is the argument given to Map.Make .
287 Since 3.12.0
290 val min_binding : 'a t -> key * 'a
294 Return the binding with the smallest key in a given map (with respect
296 to the Ord.compare ordering), or raise Not_found if the map is empty.
297 Since 3.12.0
300 val min_binding_opt : 'a t -> (key * 'a) option
304 Return the binding with the smallest key in the given map (with respect
306 to the Ord.compare ordering), or None if the map is empty.
307 Since 4.05
310 val max_binding : 'a t -> key * 'a
314 Same as MoreLabels.Map.S.min_binding , but returns the binding with the
316 largest key in the given map.
317 Since 3.12.0
320 val max_binding_opt : 'a t -> (key * 'a) option
324 Same as MoreLabels.Map.S.min_binding_opt , but returns the binding with
326 the largest key in the given map.
327 Since 4.05
330 val choose : 'a t -> key * 'a
334 Return one binding of the given map, or raise Not_found if the map is
336 empty. Which binding is chosen is unspecified, but equal bindings will
337 be chosen for equal maps.
338 Since 3.12.0
341 val choose_opt : 'a t -> (key * 'a) option
345 Return one binding of the given map, or None if the map is empty. Which
347 binding is chosen is unspecified, but equal bindings will be chosen for
348 equal maps.
349 Since 4.05
352 val split : key -> 'a t -> 'a t * 'a option * 'a t
356 split x m returns a triple (l, data, r) , where l is the map with all
359 the bindings of m whose key is strictly less than x ; r is the map with
360 all the bindings of m whose key is strictly greater than x ; data is
361 None if m contains no binding for x , or Some v if m binds v to x .
362 Since 3.12.0
365 val find : key -> 'a t -> 'a
369 find x m returns the current value of x in m , or raises Not_found if
372 no binding for x exists.
373 val find_opt : key -> 'a t -> 'a option
377 find_opt x m returns Some v if the current value of x in m is v , or
380 None if no binding for x exists.
381 Since 4.05
384 val find_first : f:(key -> bool) -> 'a t -> key * 'a
388 find_first ~f m , where f is a monotonically increasing function, re‐
391 turns the binding of m with the lowest key k such that f k , or raises
392 Not_found if no such key exists.
393 For example, find_first (fun k -> Ord.compare k x >= 0) m will return
395 the first binding k, v of m where Ord.compare k x >= 0 (intuitively: k
396 >= x ), or raise Not_found if x is greater than any element of m .
397 Since 4.05
400 val find_first_opt : f:(key -> bool) -> 'a t -> (key * 'a) option
404 find_first_opt ~f m , where f is a monotonically increasing function,
407 returns an option containing the binding of m with the lowest key k
408 such that f k , or None if no such key exists.
409 Since 4.05
412 val find_last : f:(key -> bool) -> 'a t -> key * 'a
416 find_last ~f m , where f is a monotonically decreasing function, re‐
419 turns the binding of m with the highest key k such that f k , or raises
420 Not_found if no such key exists.
421 Since 4.05
424 val find_last_opt : f:(key -> bool) -> 'a t -> (key * 'a) option
428 find_last_opt ~f m , where f is a monotonically decreasing function,
431 returns an option containing the binding of m with the highest key k
432 such that f k , or None if no such key exists.
433 Since 4.05
436 val map : f:('a -> 'b) -> 'a t -> 'b t
440 map ~f m returns a map with same domain as m , where the associated
443 value a of all bindings of m has been replaced by the result of the ap‐
444 plication of f to a . The bindings are passed to f in increasing order
445 with respect to the ordering over the type of the keys.
446 val mapi : f:(key -> 'a -> 'b) -> 'a t -> 'b t
450 Same as MoreLabels.Map.S.map , but the function receives as arguments
452 both the key and the associated value for each binding of the map.
453 Maps and Sequences
458 val to_seq : 'a t -> (key * 'a) Seq.t
459 Iterate on the whole map, in ascending order of keys
461 Since 4.07
464 val to_rev_seq : 'a t -> (key * 'a) Seq.t
468 Iterate on the whole map, in descending order of keys
470 Since 4.12
473 val to_seq_from : key -> 'a t -> (key * 'a) Seq.t
477 to_seq_from k m iterates on a subset of the bindings of m , in ascend‐
480 ing order of keys, from key k or above.
481 Since 4.07
484 val add_seq : (key * 'a) Seq.t -> 'a t -> 'a t
488 Add the given bindings to the map, in order.
490 Since 4.07
493 val of_seq : (key * 'a) Seq.t -> 'a t
497 Build a map from the given bindings
499 Since 4.07
502OCamldoc 2023-01-23 MoreLabels.Map.Make(3)