1Map.Make(3) OCaml library Map.Make(3)
2
3
4
6 Map.Make - Functor building an implementation of the map structure
7 given a totally ordered type.
8
10 Module Map.Make
11
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
113 returned 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 is a subset of keys of m1 and
127 of m2 . The presence of each such binding, and the corresponding value,
128 is determined with the function f . In terms of the find_opt opera‐
129 tion, we have find_opt x (merge f m1 m2) = f (find_opt x m1) (find_opt
130 x m2) for any key x , provided that f 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 is the union of keys of m1 and
141 of m2 . When the same binding is defined in both arguments, the func‐
142 tion 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' None None = None
146
147
148 - f' (Some v) None = Some v
149
150
151 - f' None (Some v) = Some v
152
153
154 - f' (Some v1) (Some v2) = f 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 p satisfies every binding in m , m is returned
225 unchanged (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 partition : (key -> 'a -> bool) -> 'a t -> 'a t * 'a t
237
238
239 partition p m returns a pair of maps (m1, m2) , where m1 contains all
240 the bindings of s that satisfy the predicate p , and m2 is the map with
241 all the bindings of s that do not satisfy p .
242
243
244 Since 3.12.0
245
246
247
248 val cardinal : 'a t -> int
249
250 Return the number of bindings of a map.
251
252
253 Since 3.12.0
254
255
256
257 val bindings : 'a t -> (key * 'a) list
258
259 Return the list of all bindings of the given map. The returned list is
260 sorted in increasing order with respect to the ordering Ord.compare ,
261 where Ord is the argument given to Map.Make .
262
263
264 Since 3.12.0
265
266
267
268 val min_binding : 'a t -> key * 'a
269
270 Return the smallest binding of the given map (with respect to the
271 Ord.compare ordering), or raise Not_found if the map is empty.
272
273
274 Since 3.12.0
275
276
277
278 val min_binding_opt : 'a t -> (key * 'a) option
279
280 Return the smallest binding of the given map (with respect to the
281 Ord.compare ordering), or None if the map is empty.
282
283
284 Since 4.05
285
286
287
288 val max_binding : 'a t -> key * 'a
289
290 Same as Map.S.min_binding , but returns the largest binding of the
291 given map.
292
293
294 Since 3.12.0
295
296
297
298 val max_binding_opt : 'a t -> (key * 'a) option
299
300 Same as Map.S.min_binding_opt , but returns the largest binding of the
301 given map.
302
303
304 Since 4.05
305
306
307
308 val choose : 'a t -> key * 'a
309
310 Return one binding of the given map, or raise Not_found if the map is
311 empty. Which binding is chosen is unspecified, but equal bindings will
312 be chosen for equal maps.
313
314
315 Since 3.12.0
316
317
318
319 val choose_opt : 'a t -> (key * 'a) option
320
321 Return one binding of the given map, or None if the map is empty. Which
322 binding is chosen is unspecified, but equal bindings will be chosen for
323 equal maps.
324
325
326 Since 4.05
327
328
329
330 val split : key -> 'a t -> 'a t * 'a option * 'a t
331
332
333 split x m returns a triple (l, data, r) , where l is the map with all
334 the bindings of m whose key is strictly less than x ; r is the map with
335 all the bindings of m whose key is strictly greater than x ; data is
336 None if m contains no binding for x , or Some v if m binds v to x .
337
338
339 Since 3.12.0
340
341
342
343 val find : key -> 'a t -> 'a
344
345
346 find x m returns the current binding of x in m , or raises Not_found if
347 no such binding exists.
348
349
350
351 val find_opt : key -> 'a t -> 'a option
352
353
354 find_opt x m returns Some v if the current binding of x in m is v , or
355 None if no such binding exists.
356
357
358 Since 4.05
359
360
361
362 val find_first : (key -> bool) -> 'a t -> key * 'a
363
364
365 find_first f m , where f is a monotonically increasing function,
366 returns the binding of m with the lowest key k such that f k , or
367 raises Not_found if no such key exists.
368
369 For example, find_first (fun k -> Ord.compare k x >= 0) m will return
370 the first binding k, v of m where Ord.compare k x >= 0 (intuitively: k
371 >= x ), or raise Not_found if x is greater than any element of m .
372
373
374 Since 4.05
375
376
377
378 val find_first_opt : (key -> bool) -> 'a t -> (key * 'a) option
379
380
381 find_first_opt f m , where f is a monotonically increasing function,
382 returns an option containing the binding of m with the lowest key k
383 such that f k , or None if no such key exists.
384
385
386 Since 4.05
387
388
389
390 val find_last : (key -> bool) -> 'a t -> key * 'a
391
392
393 find_last f m , where f is a monotonically decreasing function, returns
394 the binding of m with the highest key k such that f k , or raises
395 Not_found if no such key exists.
396
397
398 Since 4.05
399
400
401
402 val find_last_opt : (key -> bool) -> 'a t -> (key * 'a) option
403
404
405 find_last_opt f m , where f is a monotonically decreasing function,
406 returns an option containing the binding of m with the highest 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 map : ('a -> 'b) -> 'a t -> 'b t
415
416
417 map f m returns a map with same domain as m , where the associated
418 value a of all bindings of m has been replaced by the result of the
419 application of f to a . The bindings are passed to f in increasing
420 order with respect to the ordering over the type of the keys.
421
422
423
424 val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t
425
426 Same as Map.S.map , but the function receives as arguments both the key
427 and the associated value for each binding of the map.
428
429
430
431
432 === Iterators ===
433
434
435 val to_seq : 'a t -> (key * 'a) Seq.t
436
437 Iterate on the whole map, in ascending order
438
439
440 Since 4.07
441
442
443
444 val to_seq_from : key -> 'a t -> (key * 'a) Seq.t
445
446
447 to_seq_from k m iterates on a subset of the bindings of m , in ascend‐
448 ing order, from key k or above.
449
450
451 Since 4.07
452
453
454
455 val add_seq : (key * 'a) Seq.t -> 'a t -> 'a t
456
457 Add the given bindings to the map, in order.
458
459
460 Since 4.07
461
462
463
464 val of_seq : (key * 'a) Seq.t -> 'a t
465
466 Build a map from the given bindings
467
468
469 Since 4.07
470
471
472
473
474
475OCamldoc 2019-02-02 Map.Make(3)