1ListLabels(3)                      OCamldoc                      ListLabels(3)
2
3
4

NAME

6       ListLabels - List operations.
7

Module

9       Module   ListLabels
10

Documentation

12       Module ListLabels
13        : sig end
14
15
16       List operations.
17
18       Some  functions  are  flagged  as not tail-recursive.  A tail-recursive
19       function uses constant stack space, while a non-tail-recursive function
20       uses stack space proportional to the length of its list argument, which
21       can be a problem with very long lists.  When the function takes several
22       list  arguments,  an  approximate  formula  giving stack usage (in some
23       unspecified constant unit) is shown in parentheses.
24
25       The above considerations can usually be ignored if your lists  are  not
26       longer than about 10000 elements.
27
28
29
30
31
32
33       val length : 'a list -> int
34
35       Return the length (number of elements) of the given list.
36
37
38
39       val hd : 'a list -> 'a
40
41       Return  the  first  element  of the given list. Raise Failure hd if the
42       list is empty.
43
44
45
46       val compare_lengths : 'a list -> 'b list -> int
47
48       Compare the lengths of two lists.  compare_lengths l1 l2 is  equivalent
49       to  compare (length l1) (length l2) , except that the computation stops
50       after itering on the shortest list.
51
52
53       Since 4.05.0
54
55
56
57       val compare_length_with : 'a list -> len:int -> int
58
59       Compare the length of a list to an integer.  compare_length_with l n is
60       equivalent  to compare (length l) n , except that the computation stops
61       after at most n iterations on the list.
62
63
64       Since 4.05.0
65
66
67
68       val cons : 'a -> 'a list -> 'a list
69
70
71       cons x xs is x :: xs
72
73
74
75       Since 4.05.0
76
77
78
79       val tl : 'a list -> 'a list
80
81       Return the given list without its first element. Raise  Failure  tl  if
82       the list is empty.
83
84
85
86       val nth : 'a list -> int -> 'a
87
88       Return the n -th element of the given list.  The first element (head of
89       the list) is at position 0.  Raise Failure  nth  if  the  list  is  too
90       short.  Raise Invalid_argument List.nth if n is negative.
91
92
93
94       val nth_opt : 'a list -> int -> 'a option
95
96       Return the n -th element of the given list.  The first element (head of
97       the list) is at position 0.  Return None if  the  list  is  too  short.
98       Raise Invalid_argument List.nth if n is negative.
99
100
101       Since 4.05
102
103
104
105       val rev : 'a list -> 'a list
106
107       List reversal.
108
109
110
111       val append : 'a list -> 'a list -> 'a list
112
113       Catenate  two  lists.   Same  function  as  the infix operator @ .  Not
114       tail-recursive (length of the first argument).  The @ operator  is  not
115       tail-recursive either.
116
117
118
119       val rev_append : 'a list -> 'a list -> 'a list
120
121
122       List.rev_append  l1 l2 reverses l1 and concatenates it to l2 .  This is
123       equivalent to List.rev l1 @ l2 , but rev_append is  tail-recursive  and
124       more efficient.
125
126
127
128       val concat : 'a list list -> 'a list
129
130       Concatenate a list of lists.  The elements of the argument are all con‐
131       catenated together (in  the  same  order)  to  give  the  result.   Not
132       tail-recursive  (length  of  the  argument  +  length  of  the  longest
133       sub-list).
134
135
136
137       val flatten : 'a list list -> 'a list
138
139       Same as concat .  Not tail-recursive (length of the argument  +  length
140       of the longest sub-list).
141
142
143
144
145       === Iterators ===
146
147
148       val iter : f:('a -> unit) -> 'a list -> unit
149
150
151       List.iter  f  [a1; ...; an] applies function f in turn to a1; ...; an .
152       It is equivalent to begin f a1; f a2; ...; f an; () end .
153
154
155
156       val iteri : f:(int -> 'a -> unit) -> 'a list -> unit
157
158       Same as List.iter , but the function is applied to  the  index  of  the
159       element  as first argument (counting from 0), and the element itself as
160       second argument.
161
162
163       Since 4.00.0
164
165
166
167       val map : f:('a -> 'b) -> 'a list -> 'b list
168
169
170       List.map f [a1; ...; an] applies function f to a1, ..., an , and builds
171       the  list  [f  a1;  ...;  f  an]  with the results returned by f .  Not
172       tail-recursive.
173
174
175
176       val mapi : f:(int -> 'a -> 'b) -> 'a list -> 'b list
177
178       Same as List.map , but the function is applied to the index of the ele‐
179       ment  as  first  argument  (counting from 0), and the element itself as
180       second argument.
181
182
183       Since 4.00.0
184
185
186
187       val rev_map : f:('a -> 'b) -> 'a list -> 'b list
188
189
190       List.rev_map f l gives the same result as List.rev ( List.map  f  l)  ,
191       but is tail-recursive and more efficient.
192
193
194
195       val fold_left : f:('a -> 'b -> 'a) -> init:'a -> 'b list -> 'a
196
197
198       List.fold_left f a [b1; ...; bn] is f (... (f (f a b1) b2) ...) bn .
199
200
201
202       val fold_right : f:('a -> 'b -> 'b) -> 'a list -> init:'b -> 'b
203
204
205       List.fold_right  f [a1; ...; an] b is f a1 (f a2 (... (f an b) ...))  .
206       Not tail-recursive.
207
208
209
210
211       === Iterators on two lists ===
212
213
214       val iter2 : f:('a -> 'b -> unit) -> 'a list -> 'b list -> unit
215
216
217       List.iter2 f [a1; ...; an] [b1; ...; bn] calls in turn f a1 b1; ...;  f
218       an bn .  Raise Invalid_argument if the two lists are determined to have
219       different lengths.
220
221
222
223       val map2 : f:('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
224
225
226       List.map2 f [a1; ...; an] [b1; ...; bn] is [f a1 b1; ...; f  an  bn]  .
227       Raise  Invalid_argument if the two lists are determined to have differ‐
228       ent lengths.  Not tail-recursive.
229
230
231
232       val rev_map2 : f:('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
233
234
235       List.rev_map2 f l1 l2 gives the same result as List.rev (  List.map2  f
236       l1 l2) , but is tail-recursive and more efficient.
237
238
239
240       val  fold_left2  : f:('a -> 'b -> 'c -> 'a) -> init:'a -> 'b list -> 'c
241       list -> 'a
242
243
244       List.fold_left2 f a [b1; ...; bn] [c1; ...; cn] is f (... (f  (f  a  b1
245       c1)  b2  c2)  ...) bn cn .  Raise Invalid_argument if the two lists are
246       determined to have different lengths.
247
248
249
250       val fold_right2 : f:('a -> 'b -> 'c -> 'c) -> 'a list  ->  'b  list  ->
251       init:'c -> 'c
252
253
254       List.fold_right2  f  [a1;  ...; an] [b1; ...; bn] c is f a1 b1 (f a2 b2
255       (... (f an bn c) ...))  .  Raise Invalid_argument if the two lists  are
256       determined to have different lengths.  Not tail-recursive.
257
258
259
260
261       === List scanning ===
262
263
264       val for_all : f:('a -> bool) -> 'a list -> bool
265
266
267       for_all  p [a1; ...; an] checks if all elements of the list satisfy the
268       predicate p . That is, it returns (p a1) && (p a2) && ... && (p an) .
269
270
271
272       val exists : f:('a -> bool) -> 'a list -> bool
273
274
275       exists p [a1; ...; an] checks if at least one element of the list  sat‐
276       isfies the predicate p . That is, it returns (p a1) || (p a2) || ... ||
277       (p an) .
278
279
280
281       val for_all2 : f:('a -> 'b -> bool) -> 'a list -> 'b list -> bool
282
283       Same as  List.for_all  ,  but  for  a  two-argument  predicate.   Raise
284       Invalid_argument  if  the  two  lists  are determined to have different
285       lengths.
286
287
288
289       val exists2 : f:('a -> 'b -> bool) -> 'a list -> 'b list -> bool
290
291       Same  as  List.exists  ,  but  for  a  two-argument  predicate.   Raise
292       Invalid_argument  if  the  two  lists  are determined to have different
293       lengths.
294
295
296
297       val mem : 'a -> set:'a list -> bool
298
299
300       mem a l is true if and only if a is equal to an element of l .
301
302
303
304       val memq : 'a -> set:'a list -> bool
305
306       Same as List.mem , but uses physical  equality  instead  of  structural
307       equality to compare list elements.
308
309
310
311
312       === List searching ===
313
314
315       val find : f:('a -> bool) -> 'a list -> 'a
316
317
318       find  p  l  returns  the first element of the list l that satisfies the
319       predicate p .  Raise Not_found if there is no value that satisfies p in
320       the list l .
321
322
323
324       val find_opt : f:('a -> bool) -> 'a list -> 'a option
325
326
327       find  p  l  returns  the first element of the list l that satisfies the
328       predicate p .  Returns None if there is no value that  satisfies  p  in
329       the list l .
330
331
332       Since 4.05
333
334
335
336       val filter : f:('a -> bool) -> 'a list -> 'a list
337
338
339       filter  p  l  returns  all  the elements of the list l that satisfy the
340       predicate p .  The order of the elements in  the  input  list  is  pre‐
341       served.
342
343
344
345       val find_all : f:('a -> bool) -> 'a list -> 'a list
346
347
348       find_all is another name for List.filter .
349
350
351
352       val partition : f:('a -> bool) -> 'a list -> 'a list * 'a list
353
354
355       partition  p  l returns a pair of lists (l1, l2) , where l1 is the list
356       of all the elements of l that satisfy the predicate p , and l2  is  the
357       list of all the elements of l that do not satisfy p .  The order of the
358       elements in the input list is preserved.
359
360
361
362
363       === Association lists ===
364
365
366       val assoc : 'a -> ('a * 'b) list -> 'b
367
368
369       assoc a l returns the value associated with key a in the list of  pairs
370       l  .  That  is, assoc a [ ...; (a,b); ...] = b if (a,b) is the leftmost
371       binding of a in list l .  Raise Not_found if there is no value  associ‐
372       ated with a in the list l .
373
374
375
376       val assoc_opt : 'a -> ('a * 'b) list -> 'b option
377
378
379       assoc_opt  a  l  returns the value associated with key a in the list of
380       pairs l . That is, assoc a [ ...; (a,b); ...] = b if (a,b) is the left‐
381       most  binding of a in list l .  Returns None if there is no value asso‐
382       ciated with a in the list l .
383
384
385       Since 4.05
386
387
388
389       val assq : 'a -> ('a * 'b) list -> 'b
390
391       Same as List.assoc , but uses physical equality instead  of  structural
392       equality to compare keys.
393
394
395
396       val assq_opt : 'a -> ('a * 'b) list -> 'b option
397
398       Same  as  List.assoc_opt , but uses physical equality instead of struc‐
399       tural equality to compare keys.
400
401
402       Since 4.05.0
403
404
405
406       val mem_assoc : 'a -> map:('a * 'b) list -> bool
407
408       Same as List.assoc , but simply return true if a  binding  exists,  and
409       false if no bindings exist for the given key.
410
411
412
413       val mem_assq : 'a -> map:('a * 'b) list -> bool
414
415       Same  as  List.mem_assoc , but uses physical equality instead of struc‐
416       tural equality to compare keys.
417
418
419
420       val remove_assoc : 'a -> ('a * 'b) list -> ('a * 'b) list
421
422
423       remove_assoc a l returns the list of pairs l  without  the  first  pair
424       with key a , if any.  Not tail-recursive.
425
426
427
428       val remove_assq : 'a -> ('a * 'b) list -> ('a * 'b) list
429
430       Same  as  List.remove_assoc  ,  but  uses  physical equality instead of
431       structural equality to compare keys.  Not tail-recursive.
432
433
434
435
436       === Lists of pairs ===
437
438
439       val split : ('a * 'b) list -> 'a list * 'b list
440
441       Transform a list of pairs into a pair of lists:  split  [(a1,b1);  ...;
442       (an,bn)] is ([a1; ...; an], [b1; ...; bn]) .  Not tail-recursive.
443
444
445
446       val combine : 'a list -> 'b list -> ('a * 'b) list
447
448       Transform  a  pair of lists into a list of pairs: combine [a1; ...; an]
449       [b1; ...; bn] is [(a1,b1); ...; (an,bn)] .  Raise  Invalid_argument  if
450       the two lists have different lengths.  Not tail-recursive.
451
452
453
454
455       === Sorting ===
456
457
458       val sort : cmp:('a -> 'a -> int) -> 'a list -> 'a list
459
460       Sort  a  list  in  increasing order according to a comparison function.
461       The comparison function must return  0  if  its  arguments  compare  as
462       equal, a positive integer if the first is greater, and a negative inte‐
463       ger if the first is smaller (see Array.sort for a  complete  specifica‐
464       tion).   For example, Pervasives.compare is a suitable comparison func‐
465       tion.  The resulting list is sorted in increasing order.  List.sort  is
466       guaranteed  to  run  in constant heap space (in addition to the size of
467       the result list) and logarithmic stack space.
468
469       The current implementation uses Merge Sort. It runs  in  constant  heap
470       space and logarithmic stack space.
471
472
473
474       val stable_sort : cmp:('a -> 'a -> int) -> 'a list -> 'a list
475
476       Same  as List.sort , but the sorting algorithm is guaranteed to be sta‐
477       ble (i.e. elements that compare equal are kept in their original order)
478       .
479
480       The  current  implementation  uses Merge Sort. It runs in constant heap
481       space and logarithmic stack space.
482
483
484
485       val fast_sort : cmp:('a -> 'a -> int) -> 'a list -> 'a list
486
487       Same as List.sort or List.stable_sort , whichever is faster on  typical
488       input.
489
490
491
492       val sort_uniq : cmp:('a -> 'a -> int) -> 'a list -> 'a list
493
494       Same as List.sort , but also remove duplicates.
495
496
497       Since 4.03.0
498
499
500
501       val merge : cmp:('a -> 'a -> int) -> 'a list -> 'a list -> 'a list
502
503       Merge  two  lists:  Assuming that l1 and l2 are sorted according to the
504       comparison function cmp , merge cmp l1 l2 will  return  a  sorted  list
505       containting  all  the elements of l1 and l2 .  If several elements com‐
506       pare equal, the elements of l1 will be before the elements of l2 .  Not
507       tail-recursive (sum of the lengths of the arguments).
508
509
510
511
512
5132018-04-14                          source:                      ListLabels(3)