1ListLabels(3)                    OCaml library                   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 init : len:int -> f:(int -> 'a) -> 'a list
112
113
114       List.init len f is f 0; f 1; ...; f (len-1) , evaluated left to right.
115
116
117       Since 4.06.0
118
119
120       Raises Invalid_argument if len < 0 .
121
122
123
124       val append : 'a list -> 'a list -> 'a list
125
126       Catenate  two  lists.   Same  function  as  the infix operator @ .  Not
127       tail-recursive (length of the first argument).  The @ operator  is  not
128       tail-recursive either.
129
130
131
132       val rev_append : 'a list -> 'a list -> 'a list
133
134
135       List.rev_append  l1  l2 reverses l1 and concatenates it with l2 .  This
136       is equivalent to ( List.rev l1) @ l2 , but rev_append is tail-recursive
137       and more efficient.
138
139
140
141       val concat : 'a list list -> 'a list
142
143       Concatenate a list of lists.  The elements of the argument are all con‐
144       catenated together (in  the  same  order)  to  give  the  result.   Not
145       tail-recursive  (length  of  the  argument  +  length  of  the  longest
146       sub-list).
147
148
149
150       val flatten : 'a list list -> 'a list
151
152       Same as concat .  Not tail-recursive (length of the argument  +  length
153       of the longest sub-list).
154
155
156
157
158       === Iterators ===
159
160
161       val iter : f:('a -> unit) -> 'a list -> unit
162
163
164       List.iter  f  [a1; ...; an] applies function f in turn to a1; ...; an .
165       It is equivalent to begin f a1; f a2; ...; f an; () end .
166
167
168
169       val iteri : f:(int -> 'a -> unit) -> 'a list -> unit
170
171       Same as List.iter , but the function is applied to  the  index  of  the
172       element  as first argument (counting from 0), and the element itself as
173       second argument.
174
175
176       Since 4.00.0
177
178
179
180       val map : f:('a -> 'b) -> 'a list -> 'b list
181
182
183       List.map f [a1; ...; an] applies function f to a1, ..., an , and builds
184       the  list  [f  a1;  ...;  f  an]  with the results returned by f .  Not
185       tail-recursive.
186
187
188
189       val mapi : f:(int -> 'a -> 'b) -> 'a list -> 'b list
190
191       Same as List.map , but the function is applied to the index of the ele‐
192       ment  as  first  argument  (counting from 0), and the element itself as
193       second argument.
194
195
196       Since 4.00.0
197
198
199
200       val rev_map : f:('a -> 'b) -> 'a list -> 'b list
201
202
203       List.rev_map f l gives the same result as List.rev ( List.map  f  l)  ,
204       but is tail-recursive and more efficient.
205
206
207
208       val fold_left : f:('a -> 'b -> 'a) -> init:'a -> 'b list -> 'a
209
210
211       List.fold_left f a [b1; ...; bn] is f (... (f (f a b1) b2) ...) bn .
212
213
214
215       val fold_right : f:('a -> 'b -> 'b) -> 'a list -> init:'b -> 'b
216
217
218       List.fold_right  f [a1; ...; an] b is f a1 (f a2 (... (f an b) ...))  .
219       Not tail-recursive.
220
221
222
223
224       === Iterators on two lists ===
225
226
227       val iter2 : f:('a -> 'b -> unit) -> 'a list -> 'b list -> unit
228
229
230       List.iter2 f [a1; ...; an] [b1; ...; bn] calls in turn f a1 b1; ...;  f
231       an bn .  Raise Invalid_argument if the two lists are determined to have
232       different lengths.
233
234
235
236       val map2 : f:('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
237
238
239       List.map2 f [a1; ...; an] [b1; ...; bn] is [f a1 b1; ...; f  an  bn]  .
240       Raise  Invalid_argument if the two lists are determined to have differ‐
241       ent lengths.  Not tail-recursive.
242
243
244
245       val rev_map2 : f:('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
246
247
248       List.rev_map2 f l1 l2 gives the same result as List.rev (  List.map2  f
249       l1 l2) , but is tail-recursive and more efficient.
250
251
252
253       val  fold_left2  : f:('a -> 'b -> 'c -> 'a) -> init:'a -> 'b list -> 'c
254       list -> 'a
255
256
257       List.fold_left2 f a [b1; ...; bn] [c1; ...; cn] is f (... (f  (f  a  b1
258       c1)  b2  c2)  ...) bn cn .  Raise Invalid_argument if the two lists are
259       determined to have different lengths.
260
261
262
263       val fold_right2 : f:('a -> 'b -> 'c -> 'c) -> 'a list  ->  'b  list  ->
264       init:'c -> 'c
265
266
267       List.fold_right2  f  [a1;  ...; an] [b1; ...; bn] c is f a1 b1 (f a2 b2
268       (... (f an bn c) ...))  .  Raise Invalid_argument if the two lists  are
269       determined to have different lengths.  Not tail-recursive.
270
271
272
273
274       === List scanning ===
275
276
277       val for_all : f:('a -> bool) -> 'a list -> bool
278
279
280       for_all  p [a1; ...; an] checks if all elements of the list satisfy the
281       predicate p . That is, it returns (p a1) && (p a2) && ... && (p an) .
282
283
284
285       val exists : f:('a -> bool) -> 'a list -> bool
286
287
288       exists p [a1; ...; an] checks if at least one element of the list  sat‐
289       isfies the predicate p . That is, it returns (p a1) || (p a2) || ... ||
290       (p an) .
291
292
293
294       val for_all2 : f:('a -> 'b -> bool) -> 'a list -> 'b list -> bool
295
296       Same as  List.for_all  ,  but  for  a  two-argument  predicate.   Raise
297       Invalid_argument  if  the  two  lists  are determined to have different
298       lengths.
299
300
301
302       val exists2 : f:('a -> 'b -> bool) -> 'a list -> 'b list -> bool
303
304       Same  as  List.exists  ,  but  for  a  two-argument  predicate.   Raise
305       Invalid_argument  if  the  two  lists  are determined to have different
306       lengths.
307
308
309
310       val mem : 'a -> set:'a list -> bool
311
312
313       mem a l is true if and only if a is equal to an element of l .
314
315
316
317       val memq : 'a -> set:'a list -> bool
318
319       Same as List.mem , but uses physical  equality  instead  of  structural
320       equality to compare list elements.
321
322
323
324
325       === List searching ===
326
327
328       val find : f:('a -> bool) -> 'a list -> 'a
329
330
331       find  p  l  returns  the first element of the list l that satisfies the
332       predicate p .  Raise Not_found if there is no value that satisfies p in
333       the list l .
334
335
336
337       val find_opt : f:('a -> bool) -> 'a list -> 'a option
338
339
340       find  p  l  returns  the first element of the list l that satisfies the
341       predicate p .  Returns None if there is no value that  satisfies  p  in
342       the list l .
343
344
345       Since 4.05
346
347
348
349       val filter : f:('a -> bool) -> 'a list -> 'a list
350
351
352       filter  p  l  returns  all  the elements of the list l that satisfy the
353       predicate p .  The order of the elements in  the  input  list  is  pre‐
354       served.
355
356
357
358       val find_all : f:('a -> bool) -> 'a list -> 'a list
359
360
361       find_all is another name for List.filter .
362
363
364
365       val partition : f:('a -> bool) -> 'a list -> 'a list * 'a list
366
367
368       partition  p  l returns a pair of lists (l1, l2) , where l1 is the list
369       of all the elements of l that satisfy the predicate p , and l2  is  the
370       list of all the elements of l that do not satisfy p .  The order of the
371       elements in the input list is preserved.
372
373
374
375
376       === Association lists ===
377
378
379       val assoc : 'a -> ('a * 'b) list -> 'b
380
381
382       assoc a l returns the value associated with key a in the list of  pairs
383       l  .  That  is, assoc a [ ...; (a,b); ...] = b if (a,b) is the leftmost
384       binding of a in list l .  Raise Not_found if there is no value  associ‐
385       ated with a in the list l .
386
387
388
389       val assoc_opt : 'a -> ('a * 'b) list -> 'b option
390
391
392       assoc_opt  a  l  returns the value associated with key a in the list of
393       pairs l . That is, assoc a [ ...; (a,b); ...] = b if (a,b) is the left‐
394       most  binding of a in list l .  Returns None if there is no value asso‐
395       ciated with a in the list l .
396
397
398       Since 4.05
399
400
401
402       val assq : 'a -> ('a * 'b) list -> 'b
403
404       Same as List.assoc , but uses physical equality instead  of  structural
405       equality to compare keys.
406
407
408
409       val assq_opt : 'a -> ('a * 'b) list -> 'b option
410
411       Same  as  List.assoc_opt , but uses physical equality instead of struc‐
412       tural equality to compare keys.
413
414
415       Since 4.05.0
416
417
418
419       val mem_assoc : 'a -> map:('a * 'b) list -> bool
420
421       Same as List.assoc , but simply return true if a  binding  exists,  and
422       false if no bindings exist for the given key.
423
424
425
426       val mem_assq : 'a -> map:('a * 'b) list -> bool
427
428       Same  as  List.mem_assoc , but uses physical equality instead of struc‐
429       tural equality to compare keys.
430
431
432
433       val remove_assoc : 'a -> ('a * 'b) list -> ('a * 'b) list
434
435
436       remove_assoc a l returns the list of pairs l  without  the  first  pair
437       with key a , if any.  Not tail-recursive.
438
439
440
441       val remove_assq : 'a -> ('a * 'b) list -> ('a * 'b) list
442
443       Same  as  List.remove_assoc  ,  but  uses  physical equality instead of
444       structural equality to compare keys.  Not tail-recursive.
445
446
447
448
449       === Lists of pairs ===
450
451
452       val split : ('a * 'b) list -> 'a list * 'b list
453
454       Transform a list of pairs into a pair of lists:  split  [(a1,b1);  ...;
455       (an,bn)] is ([a1; ...; an], [b1; ...; bn]) .  Not tail-recursive.
456
457
458
459       val combine : 'a list -> 'b list -> ('a * 'b) list
460
461       Transform  a  pair of lists into a list of pairs: combine [a1; ...; an]
462       [b1; ...; bn] is [(a1,b1); ...; (an,bn)] .  Raise  Invalid_argument  if
463       the two lists have different lengths.  Not tail-recursive.
464
465
466
467
468       === Sorting ===
469
470
471       val sort : cmp:('a -> 'a -> int) -> 'a list -> 'a list
472
473       Sort  a  list  in  increasing order according to a comparison function.
474       The comparison function must return  0  if  its  arguments  compare  as
475       equal, a positive integer if the first is greater, and a negative inte‐
476       ger if the first is smaller (see Array.sort for a  complete  specifica‐
477       tion).   For example, Pervasives.compare is a suitable comparison func‐
478       tion.  The resulting list is sorted in increasing order.  List.sort  is
479       guaranteed  to  run  in constant heap space (in addition to the size of
480       the result list) and logarithmic stack space.
481
482       The current implementation uses Merge Sort. It runs  in  constant  heap
483       space and logarithmic stack space.
484
485
486
487       val stable_sort : cmp:('a -> 'a -> int) -> 'a list -> 'a list
488
489       Same  as List.sort , but the sorting algorithm is guaranteed to be sta‐
490       ble (i.e. elements that compare equal are kept in their original order)
491       .
492
493       The  current  implementation  uses Merge Sort. It runs in constant heap
494       space and logarithmic stack space.
495
496
497
498       val fast_sort : cmp:('a -> 'a -> int) -> 'a list -> 'a list
499
500       Same as List.sort or List.stable_sort , whichever is faster on  typical
501       input.
502
503
504
505       val sort_uniq : cmp:('a -> 'a -> int) -> 'a list -> 'a list
506
507       Same as List.sort , but also remove duplicates.
508
509
510       Since 4.03.0
511
512
513
514       val merge : cmp:('a -> 'a -> int) -> 'a list -> 'a list -> 'a list
515
516       Merge  two  lists:  Assuming that l1 and l2 are sorted according to the
517       comparison function cmp , merge cmp l1 l2 will  return  a  sorted  list
518       containing all the elements of l1 and l2 .  If several elements compare
519       equal, the elements of l1 will be before the  elements  of  l2  .   Not
520       tail-recursive (sum of the lengths of the arguments).
521
522
523
524
525       === Iterators ===
526
527
528       val to_seq : 'a list -> 'a Seq.t
529
530       Iterate on the list
531
532
533       Since 4.07
534
535
536
537       val of_seq : 'a Seq.t -> 'a list
538
539       Create a list from the iterator
540
541
542       Since 4.07
543
544
545
546
547
548OCamldoc                          2019-02-02                     ListLabels(3)