1Map.Make(3)                      OCaml library                     Map.Make(3)
2
3
4

NAME

6       Map.Make  -  Functor  building  an  implementation of the map structure
7       given a totally ordered type.
8

Module

10       Module   Map.Make
11

Documentation

13       Module Make
14        : functor (Ord : OrderedType) -> sig end
15
16
17       Functor building an implementation of the map structure given a totally
18       ordered type.
19
20
21       Parameters:
22
23       "Ord"
24
25       Map.OrderedType
26
27
28
29
30
31
32
33       type key
34
35
36       The type of the map keys.
37
38
39       type +'a t
40
41
42       The type of maps from type key to type 'a .
43
44
45
46       val empty : 'a t
47
48       The empty map.
49
50
51
52       val is_empty : 'a t -> bool
53
54       Test whether a map is empty or not.
55
56
57
58       val mem : key -> 'a t -> bool
59
60
61       mem  x  m returns true if m contains a binding for x , and false other‐
62       wise.
63
64
65
66       val add : key -> 'a -> 'a t -> 'a t
67
68
69       add key data m returns a map containing the same bindings as m , plus a
70       binding  of key to data . If key was already bound in m to a value that
71       is physically equal to data , m is returned unchanged  (the  result  of
72       the  function  is then physically equal to m ). Otherwise, the previous
73       binding of key in m disappears.
74
75
76       Before4.03 Physical equality was not ensured.
77
78
79
80
81       val update : key -> ('a option -> 'a option) -> 'a t -> 'a t
82
83
84       update key f m returns a map containing the same bindings as m , except
85       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
93
94       Since 4.06.0
95
96
97
98       val singleton : key -> 'a -> 'a t
99
100
101       singleton x y returns the one-element map that contains a binding y for
102       x .
103
104
105       Since 3.12.0
106
107
108
109       val remove : key -> 'a t -> 'a t
110
111
112       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
117
118       Before4.03 Physical equality was not ensured.
119
120
121
122
123       val  merge : (key -> 'a option -> 'b option -> 'c option) -> 'a t -> 'b
124       t -> 'c t
125
126
127       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
133
134       Since 3.12.0
135
136
137
138       val union : (key -> 'a -> 'a -> 'a option) -> 'a t -> 'a t -> 'a t
139
140
141       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
146       - f' _key None None = None
147
148
149       - f' _key (Some v) None = Some v
150
151
152       - f' _key None (Some v) = Some v
153
154
155       - f' key (Some v1) (Some v2) = f key v1 v2
156
157
158
159
160       Since 4.03.0
161
162
163
164       val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int
165
166       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
169
170
171       val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
172
173
174       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
178
179
180       val iter : (key -> 'a -> unit) -> 'a t -> unit
181
182
183       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
188
189
190       val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
191
192
193       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
197
198
199       val for_all : (key -> 'a -> bool) -> 'a t -> bool
200
201
202       for_all f m checks if all the bindings of the map satisfy the predicate
203       f .
204
205
206       Since 3.12.0
207
208
209
210       val exists : (key -> 'a -> bool) -> 'a t -> bool
211
212
213       exists f m checks if at least one binding  of  the  map  satisfies  the
214       predicate f .
215
216
217       Since 3.12.0
218
219
220
221       val filter : (key -> 'a -> bool) -> 'a t -> 'a t
222
223
224       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
228
229       Before4.03 Physical equality was not ensured.
230
231
232
233       Since 3.12.0
234
235
236
237       val filter_map : (key -> 'a -> 'b option) -> 'a t -> 'b t
238
239
240       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
244       -if f k v is None then k is not in the result,
245
246       -if f k v is Some v' then the binding (k, v') is in the output map.
247
248       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
253       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
256
257       Since 4.11.0
258
259
260
261       val partition : (key -> 'a -> bool) -> 'a t -> 'a t * 'a t
262
263
264       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
268
269       Since 3.12.0
270
271
272
273       val cardinal : 'a t -> int
274
275       Return the number of bindings of a map.
276
277
278       Since 3.12.0
279
280
281
282       val bindings : 'a t -> (key * 'a) list
283
284       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
288
289       Since 3.12.0
290
291
292
293       val min_binding : 'a t -> key * 'a
294
295       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
298
299       Since 3.12.0
300
301
302
303       val min_binding_opt : 'a t -> (key * 'a) option
304
305       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
308
309       Since 4.05
310
311
312
313       val max_binding : 'a t -> key * 'a
314
315       Same as Map.S.min_binding , but returns the binding  with  the  largest
316       key in the given map.
317
318
319       Since 3.12.0
320
321
322
323       val max_binding_opt : 'a t -> (key * 'a) option
324
325       Same  as  Map.S.min_binding_opt  ,  but  returns  the  binding with the
326       largest key in the given map.
327
328
329       Since 4.05
330
331
332
333       val choose : 'a t -> key * 'a
334
335       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
339
340       Since 3.12.0
341
342
343
344       val choose_opt : 'a t -> (key * 'a) option
345
346       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
350
351       Since 4.05
352
353
354
355       val split : key -> 'a t -> 'a t * 'a option * 'a t
356
357
358       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
363
364       Since 3.12.0
365
366
367
368       val find : key -> 'a t -> 'a
369
370
371       find  x  m returns the current value of x in m , or raises Not_found if
372       no binding for x exists.
373
374
375
376       val find_opt : key -> 'a t -> 'a option
377
378
379       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
382
383       Since 4.05
384
385
386
387       val find_first : (key -> bool) -> 'a t -> key * 'a
388
389
390       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
394       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
398
399       Since 4.05
400
401
402
403       val find_first_opt : (key -> bool) -> 'a t -> (key * 'a) option
404
405
406       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
410
411       Since 4.05
412
413
414
415       val find_last : (key -> bool) -> 'a t -> key * 'a
416
417
418       find_last f m , where f is a monotonically decreasing function, returns
419       the binding of m with the highest key k such  that  f  k  ,  or  raises
420       Not_found if no such key exists.
421
422
423       Since 4.05
424
425
426
427       val find_last_opt : (key -> bool) -> 'a t -> (key * 'a) option
428
429
430       find_last_opt f m , where f is a monotonically decreasing function, re‐
431       turns an option containing the binding of m with the highest key k such
432       that f k , or None if no such key exists.
433
434
435       Since 4.05
436
437
438
439       val map : ('a -> 'b) -> 'a t -> 'b t
440
441
442       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
447
448
449       val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t
450
451       Same as Map.S.map , but the function receives as arguments both the key
452       and the associated value for each binding of the map.
453
454
455
456
457   Maps and Sequences
458       val to_seq : 'a t -> (key * 'a) Seq.t
459
460       Iterate on the whole map, in ascending order of keys
461
462
463       Since 4.07
464
465
466
467       val to_rev_seq : 'a t -> (key * 'a) Seq.t
468
469       Iterate on the whole map, in descending order of keys
470
471
472       Since 4.12
473
474
475
476       val to_seq_from : key -> 'a t -> (key * 'a) Seq.t
477
478
479       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
482
483       Since 4.07
484
485
486
487       val add_seq : (key * 'a) Seq.t -> 'a t -> 'a t
488
489       Add the given bindings to the map, in order.
490
491
492       Since 4.07
493
494
495
496       val of_seq : (key * 'a) Seq.t -> 'a t
497
498       Build a map from the given bindings
499
500
501       Since 4.07
502
503
504
505
506
507OCamldoc                          2022-07-22                       Map.Make(3)
Impressum