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 x y m returns a map containing the same bindings  as  m  ,  plus  a
70       binding  of  x  to  y  . If x was already bound in m to a value that is
71       physically equal to y , m is returned  unchanged  (the  result  of  the
72       function is then physically equal to m ). Otherwise, the previous bind‐
73       ing of x 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 x f m returns a map containing the same bindings as m  ,  except
85       for  the  binding  of  x  .  Depending  on  the value of y where y is f
86       (find_opt x m) , the binding of x is added, removed or updated. If y is
87       None  ,  the binding is removed if it exists; otherwise, if y is Some z
88       then x is associated to z in the resulting map.  If x was already bound
89       in m to a value that is physically equal to z , m is returned unchanged
90       (the result of the function is then physically equal to m ).
91
92
93       Since 4.06.0
94
95
96
97       val singleton : key -> 'a -> 'a t
98
99
100       singleton x y returns the one-element map that contains a binding y for
101       x .
102
103
104       Since 3.12.0
105
106
107
108       val remove : key -> 'a t -> 'a t
109
110
111       remove x m returns a map containing the same bindings as m , except for
112       x which is unbound in the returned map.  If x was not in m , m  is  re‐
113       turned  unchanged  (the result of the function is then physically equal
114       to m ).
115
116
117       Before4.03 Physical equality was not ensured.
118
119
120
121
122       val merge : (key -> 'a option -> 'b option -> 'c option) -> 'a t ->  'b
123       t -> 'c t
124
125
126       merge  f m1 m2 computes a map whose keys are a subset of the keys of m1
127       and of m2 . The presence of each such binding,  and  the  corresponding
128       value,  is  determined  with the function f .  In terms of the find_opt
129       operation, we have find_opt x (merge f m1 m2) = f  x  (find_opt  x  m1)
130       (find_opt x m2) for any key x , provided that f x None None = None .
131
132
133       Since 3.12.0
134
135
136
137       val union : (key -> 'a -> 'a -> 'a option) -> 'a t -> 'a t -> 'a t
138
139
140       union  f m1 m2 computes a map whose keys are a subset of the keys of m1
141       and of m2 .  When the same binding is defined in  both  arguments,  the
142       function  f is used to combine them.  This is a special case of merge :
143       union f m1 m2 is equivalent to merge f' m1 m2 , where
144
145       - f' _key None None = None
146
147
148       - f' _key (Some v) None = Some v
149
150
151       - f' _key None (Some v) = Some v
152
153
154       - f' key (Some v1) (Some v2) = f key v1 v2
155
156
157
158
159       Since 4.03.0
160
161
162
163       val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int
164
165       Total ordering between maps.  The first argument is  a  total  ordering
166       used to compare data associated with equal keys in the two maps.
167
168
169
170       val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
171
172
173       equal  cmp  m1  m2 tests whether the maps m1 and m2 are equal, that is,
174       contain equal keys and associate them with  equal  data.   cmp  is  the
175       equality predicate used to compare the data associated with the keys.
176
177
178
179       val iter : (key -> 'a -> unit) -> 'a t -> unit
180
181
182       iter  f  m  applies f to all bindings in map m .  f receives the key as
183       first argument, and the associated value as second argument.  The bind‐
184       ings  are  passed to f in increasing order with respect to the ordering
185       over the type of the keys.
186
187
188
189       val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
190
191
192       fold f m a computes (f kN dN ... (f k1 d1 a)...)  , where k1 ... kN are
193       the  keys of all bindings in m (in increasing order), and d1 ... dN are
194       the associated data.
195
196
197
198       val for_all : (key -> 'a -> bool) -> 'a t -> bool
199
200
201       for_all p m checks if all the bindings of the map satisfy the predicate
202       p .
203
204
205       Since 3.12.0
206
207
208
209       val exists : (key -> 'a -> bool) -> 'a t -> bool
210
211
212       exists  p  m  checks  if  at least one binding of the map satisfies the
213       predicate p .
214
215
216       Since 3.12.0
217
218
219
220       val filter : (key -> 'a -> bool) -> 'a t -> 'a t
221
222
223       filter p m returns the map with all the  bindings  in  m  that  satisfy
224       predicate  p  .  If  every binding in m satisfies p , m is returned un‐
225       changed (the result of the function is then physically equal to m )
226
227
228       Before4.03 Physical equality was not ensured.
229
230
231
232       Since 3.12.0
233
234
235
236       val filter_map : (key -> 'a -> 'b option) -> 'a t -> 'b t
237
238
239       filter_map f m applies the function f to  every  binding  of  m  ,  and
240       builds  a  map  from  the results. For each binding (k, v) in the input
241       map:
242
243       -if f k v is None then k is not in the result,
244
245       -if f k v is Some v' then the binding (k, v') is in the output map.
246
247       For example, the following function on maps whose values are lists
248               filter_map
249                 (fun _k li -> match li with [] -> None | _::tl -> Some tl)
250                 m
251
252       drops all bindings of m whose value is an  empty  list,  and  pops  the
253       first element of each value that is non-empty.
254
255
256       Since 4.11.0
257
258
259
260       val partition : (key -> 'a -> bool) -> 'a t -> 'a t * 'a t
261
262
263       partition  p  m returns a pair of maps (m1, m2) , where m1 contains all
264       the bindings of m that satisfy the predicate p , and m2 is the map with
265       all the bindings of m that do not satisfy p .
266
267
268       Since 3.12.0
269
270
271
272       val cardinal : 'a t -> int
273
274       Return the number of bindings of a map.
275
276
277       Since 3.12.0
278
279
280
281       val bindings : 'a t -> (key * 'a) list
282
283       Return the list of all bindings of the given map.  The returned list is
284       sorted in increasing  order  of  keys  with  respect  to  the  ordering
285       Ord.compare , where Ord is the argument given to Map.Make .
286
287
288       Since 3.12.0
289
290
291
292       val min_binding : 'a t -> key * 'a
293
294       Return  the  binding with the smallest key in a given map (with respect
295       to the Ord.compare ordering), or raise Not_found if the map is empty.
296
297
298       Since 3.12.0
299
300
301
302       val min_binding_opt : 'a t -> (key * 'a) option
303
304       Return the binding with the smallest key in the given map (with respect
305       to the Ord.compare ordering), or None if the map is empty.
306
307
308       Since 4.05
309
310
311
312       val max_binding : 'a t -> key * 'a
313
314       Same  as  Map.S.min_binding  , but returns the binding with the largest
315       key in the given map.
316
317
318       Since 3.12.0
319
320
321
322       val max_binding_opt : 'a t -> (key * 'a) option
323
324       Same as Map.S.min_binding_opt  ,  but  returns  the  binding  with  the
325       largest key in the given map.
326
327
328       Since 4.05
329
330
331
332       val choose : 'a t -> key * 'a
333
334       Return  one  binding of the given map, or raise Not_found if the map is
335       empty. Which binding is chosen is unspecified, but equal bindings  will
336       be chosen for equal maps.
337
338
339       Since 3.12.0
340
341
342
343       val choose_opt : 'a t -> (key * 'a) option
344
345       Return one binding of the given map, or None if the map is empty. Which
346       binding is chosen is unspecified, but equal bindings will be chosen for
347       equal maps.
348
349
350       Since 4.05
351
352
353
354       val split : key -> 'a t -> 'a t * 'a option * 'a t
355
356
357       split  x  m returns a triple (l, data, r) , where l is the map with all
358       the bindings of m whose key is strictly less than x ; r is the map with
359       all  the  bindings  of m whose key is strictly greater than x ; data is
360       None if m contains no binding for x , or Some v if m binds v to x .
361
362
363       Since 3.12.0
364
365
366
367       val find : key -> 'a t -> 'a
368
369
370       find x m returns the current value of x in m , or raises  Not_found  if
371       no binding for x exists.
372
373
374
375       val find_opt : key -> 'a t -> 'a option
376
377
378       find_opt  x  m  returns Some v if the current value of x in m is v , or
379       None if no binding for x exists.
380
381
382       Since 4.05
383
384
385
386       val find_first : (key -> bool) -> 'a t -> key * 'a
387
388
389       find_first f m , where f is a monotonically  increasing  function,  re‐
390       turns  the binding of m with the lowest key k such that f k , or raises
391       Not_found if no such key exists.
392
393       For example, find_first (fun k -> Ord.compare k x >= 0) m  will  return
394       the  first binding k, v of m where Ord.compare k x >= 0 (intuitively: k
395       >= x ), or raise Not_found if x is greater than any element of m .
396
397
398       Since 4.05
399
400
401
402       val find_first_opt : (key -> bool) -> 'a t -> (key * 'a) option
403
404
405       find_first_opt f m , where f is a  monotonically  increasing  function,
406       returns  an  option  containing  the binding of m with the lowest key k
407       such that f k , or None if no such key exists.
408
409
410       Since 4.05
411
412
413
414       val find_last : (key -> bool) -> 'a t -> key * 'a
415
416
417       find_last f m , where f is a monotonically decreasing function, returns
418       the  binding  of  m  with  the  highest key k such that f k , or raises
419       Not_found if no such key exists.
420
421
422       Since 4.05
423
424
425
426       val find_last_opt : (key -> bool) -> 'a t -> (key * 'a) option
427
428
429       find_last_opt f m , where f is a monotonically decreasing function, re‐
430       turns an option containing the binding of m with the highest key k such
431       that f k , or None if no such key exists.
432
433
434       Since 4.05
435
436
437
438       val map : ('a -> 'b) -> 'a t -> 'b t
439
440
441       map f m returns a map with same domain as  m  ,  where  the  associated
442       value a of all bindings of m has been replaced by the result of the ap‐
443       plication of f to a .  The bindings are passed to f in increasing order
444       with respect to the ordering over the type of the keys.
445
446
447
448       val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t
449
450       Same as Map.S.map , but the function receives as arguments both the key
451       and the associated value for each binding of the map.
452
453
454
455
456   Iterators
457       val to_seq : 'a t -> (key * 'a) Seq.t
458
459       Iterate on the whole map, in ascending order of keys
460
461
462       Since 4.07
463
464
465
466       val to_seq_from : key -> 'a t -> (key * 'a) Seq.t
467
468
469       to_seq_from k m iterates on a subset of the bindings of m , in  ascend‐
470       ing order of keys, from key k or above.
471
472
473       Since 4.07
474
475
476
477       val add_seq : (key * 'a) Seq.t -> 'a t -> 'a t
478
479       Add the given bindings to the map, in order.
480
481
482       Since 4.07
483
484
485
486       val of_seq : (key * 'a) Seq.t -> 'a t
487
488       Build a map from the given bindings
489
490
491       Since 4.07
492
493
494
495
496
497OCamldoc                          2021-01-26                       Map.Make(3)