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 un‐
23       specified 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       The labeled version of this module can be used as described in the Std‐
29       Labels module.
30
31
32
33
34
35       type 'a t = 'a list =
36        | []
37        | (::) of 'a * 'a list
38
39
40       An alias for the type of lists.
41
42
43
44       val length : 'a list -> int
45
46       Return the length (number of elements) of the given list.
47
48
49
50       val compare_lengths : 'a list -> 'b list -> int
51
52       Compare the lengths of two lists.  compare_lengths l1 l2 is  equivalent
53       to  compare (length l1) (length l2) , except that the computation stops
54       after reaching the end of the shortest list.
55
56
57       Since 4.05.0
58
59
60
61       val compare_length_with : 'a list -> len:int -> int
62
63       Compare the length of a list to an integer.  compare_length_with l  len
64       is  equivalent  to compare (length l) len , except that the computation
65       stops after at most len iterations on the list.
66
67
68       Since 4.05.0
69
70
71
72       val cons : 'a -> 'a list -> 'a list
73
74
75       cons x xs is x :: xs
76
77
78
79       Since 4.05.0
80
81
82
83       val hd : 'a list -> 'a
84
85       Return the first element of the given list.
86
87
88       Raises Failure if the list is empty.
89
90
91
92       val tl : 'a list -> 'a list
93
94       Return the given list without its first element.
95
96
97       Raises Failure if the list is empty.
98
99
100
101       val nth : 'a list -> int -> 'a
102
103       Return the n -th element of the given list.  The first element (head of
104       the list) is at position 0.
105
106
107       Raises Failure if the list is too short.
108
109
110       Raises Invalid_argument if n is negative.
111
112
113
114       val nth_opt : 'a list -> int -> 'a option
115
116       Return the n -th element of the given list.  The first element (head of
117       the list) is at position 0.  Return None if the list is too short.
118
119
120       Since 4.05
121
122
123       Raises Invalid_argument if n is negative.
124
125
126
127       val rev : 'a list -> 'a list
128
129       List reversal.
130
131
132
133       val init : len:int -> f:(int -> 'a) -> 'a list
134
135
136       init ~len ~f is f 0; f 1; ...; f (len-1) , evaluated left to right.
137
138
139       Since 4.06.0
140
141
142       Raises Invalid_argument if len < 0 .
143
144
145
146       val append : 'a list -> 'a list -> 'a list
147
148       Concatenate two lists. Same function as the infix  operator  @  .   Not
149       tail-recursive  (length  of  the first argument). The @ operator is not
150       tail-recursive either.
151
152
153
154       val rev_append : 'a list -> 'a list -> 'a list
155
156
157       rev_append l1 l2 reverses l1 and concatenates it with  l2  .   This  is
158       equivalent to ( ListLabels.rev l1) @ l2 , but rev_append is tail-recur‐
159       sive and more efficient.
160
161
162
163       val concat : 'a list list -> 'a list
164
165       Concatenate a list of lists. The elements of the argument are all  con‐
166       catenated  together  (in  the  same  order)  to  give  the result.  Not
167       tail-recursive  (length  of  the  argument  +  length  of  the  longest
168       sub-list).
169
170
171
172       val flatten : 'a list list -> 'a list
173
174       Same  as ListLabels.concat . Not tail-recursive (length of the argument
175       + length of the longest sub-list).
176
177
178
179
180   Comparison
181       val equal : eq:('a -> 'a -> bool) -> 'a list -> 'a list -> bool
182
183
184       equal eq [a1; ...; an] [b1; ..; bm] holds when the two input lists have
185       the  same length, and for each pair of elements ai , bi at the same po‐
186       sition we have eq ai bi .
187
188       Note: the eq function may be called even if the  lists  have  different
189       length.  If  you know your equality function is costly, you may want to
190       check ListLabels.compare_lengths first.
191
192
193       Since 4.12.0
194
195
196
197       val compare : cmp:('a -> 'a -> int) -> 'a list -> 'a list -> int
198
199
200       compare cmp [a1; ...; an] [b1; ...; bm] performs a  lexicographic  com‐
201       parison  of  the two input lists, using the same 'a -> 'a -> int inter‐
202       face as compare :
203
204
205       - a1 :: l1 is smaller than a2 :: l2 (negative result) if a1 is  smaller
206       than a2 , or if they are equal (0 result) and l1 is smaller than l2
207
208
209       -the empty list [] is strictly smaller than non-empty lists
210
211       Note:  the cmp function will be called even if the lists have different
212       lengths.
213
214
215       Since 4.12.0
216
217
218
219
220   Iterators
221       val iter : f:('a -> unit) -> 'a list -> unit
222
223
224       iter ~f [a1; ...; an] applies function f in turn to a1; ...; an . It is
225       equivalent to begin f a1; f a2; ...; f an; () end .
226
227
228
229       val iteri : f:(int -> 'a -> unit) -> 'a list -> unit
230
231       Same  as  ListLabels.iter , but the function is applied to the index of
232       the element as first argument (counting from 0), and the element itself
233       as second argument.
234
235
236       Since 4.00.0
237
238
239
240       val map : f:('a -> 'b) -> 'a list -> 'b list
241
242
243       map ~f [a1; ...; an] applies function f to a1, ..., an , and builds the
244       list [f a1; ...; f an] with the results returned by f . Not tail-recur‐
245       sive.
246
247
248
249       val mapi : f:(int -> 'a -> 'b) -> 'a list -> 'b list
250
251       Same  as  ListLabels.map  , but the function is applied to the index of
252       the element as first argument (counting from 0), and the element itself
253       as second argument. Not tail-recursive.
254
255
256       Since 4.00.0
257
258
259
260       val rev_map : f:('a -> 'b) -> 'a list -> 'b list
261
262
263       rev_map ~f l gives the same result as ListLabels.rev ( ListLabels.map f
264       l) , but is tail-recursive and more efficient.
265
266
267
268       val filter_map : f:('a -> 'b option) -> 'a list -> 'b list
269
270
271       filter_map ~f l applies f to every element of l , filters out the  None
272       elements and returns the list of the arguments of the Some elements.
273
274
275       Since 4.08.0
276
277
278
279       val concat_map : f:('a -> 'b list) -> 'a list -> 'b list
280
281
282       concat_map  ~f  l  gives the same result as ListLabels.concat ( ListLa‐
283       bels.map f l) . Tail-recursive.
284
285
286       Since 4.10.0
287
288
289
290       val fold_left_map : f:('a -> 'b -> 'a * 'c) -> init:'a -> 'b list -> 'a
291       * 'c list
292
293
294       fold_left_map  is   a  combination of fold_left and map that threads an
295       accumulator through calls to f .
296
297
298       Since 4.11.0
299
300
301
302       val fold_left : f:('a -> 'b -> 'a) -> init:'a -> 'b list -> 'a
303
304
305       fold_left ~f ~init [b1; ...; bn] is f (... (f (f init b1) b2) ...) bn .
306
307
308
309       val fold_right : f:('a -> 'b -> 'b) -> 'a list -> init:'b -> 'b
310
311
312       fold_right ~f [a1; ...; an] ~init is f a1 (f a2 (... (f an init)  ...))
313       . Not tail-recursive.
314
315
316
317
318   Iterators on two lists
319       val iter2 : f:('a -> 'b -> unit) -> 'a list -> 'b list -> unit
320
321
322       iter2  ~f  [a1; ...; an] [b1; ...; bn] calls in turn f a1 b1; ...; f an
323       bn .
324
325
326       Raises Invalid_argument if the two lists are determined to have differ‐
327       ent lengths.
328
329
330
331       val map2 : f:('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
332
333
334       map2 ~f [a1; ...; an] [b1; ...; bn] is [f a1 b1; ...; f an bn] .
335
336
337       Raises Invalid_argument if the two lists are determined to have differ‐
338       ent lengths. Not tail-recursive.
339
340
341
342       val rev_map2 : f:('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
343
344
345       rev_map2 ~f l1 l2 gives the same result  as  ListLabels.rev  (  ListLa‐
346       bels.map2 f l1 l2) , but is tail-recursive and more efficient.
347
348
349
350       val  fold_left2  : f:('a -> 'b -> 'c -> 'a) -> init:'a -> 'b list -> 'c
351       list -> 'a
352
353
354       fold_left2 ~f ~init [a1; ...; an] [b1; ...; bn] is f (... (f (f init a1
355       b1) a2 b2) ...) an bn .
356
357
358       Raises Invalid_argument if the two lists are determined to have differ‐
359       ent lengths.
360
361
362
363       val fold_right2 : f:('a -> 'b -> 'c -> 'c) -> 'a list  ->  'b  list  ->
364       init:'c -> 'c
365
366
367       fold_right2  ~f  [a1;  ...; an] [b1; ...; bn] ~init is f a1 b1 (f a2 b2
368       (... (f an bn init) ...))  .
369
370
371       Raises Invalid_argument if the two lists are determined to have differ‐
372       ent lengths. Not tail-recursive.
373
374
375
376
377   List scanning
378       val for_all : f:('a -> bool) -> 'a list -> bool
379
380
381       for_all ~f [a1; ...; an] checks if all elements of the list satisfy the
382       predicate f . That is, it returns (f a1) && (f a2) && ... && (f an) for
383       a non-empty list and true if the list is empty.
384
385
386
387       val exists : f:('a -> bool) -> 'a list -> bool
388
389
390       exists ~f [a1; ...; an] checks if at least one element of the list sat‐
391       isfies the predicate f . That is, it returns (f a1) || (f a2) || ... ||
392       (f an) for a non-empty list and false if the list is empty.
393
394
395
396       val for_all2 : f:('a -> 'b -> bool) -> 'a list -> 'b list -> bool
397
398       Same as ListLabels.for_all , but for a two-argument predicate.
399
400
401       Raises Invalid_argument if the two lists are determined to have differ‐
402       ent lengths.
403
404
405
406       val exists2 : f:('a -> 'b -> bool) -> 'a list -> 'b list -> bool
407
408       Same as ListLabels.exists , but for a two-argument predicate.
409
410
411       Raises Invalid_argument if the two lists are determined to have differ‐
412       ent lengths.
413
414
415
416       val mem : 'a -> set:'a list -> bool
417
418
419       mem a ~set is true if and only if a is equal to an element of set .
420
421
422
423       val memq : 'a -> set:'a list -> bool
424
425       Same  as  ListLabels.mem , but uses physical equality instead of struc‐
426       tural equality to compare list elements.
427
428
429
430
431   List searching
432       val find : f:('a -> bool) -> 'a list -> 'a
433
434
435       find ~f l returns the first element of the list l  that  satisfies  the
436       predicate f .
437
438
439       Raises Not_found if there is no value that satisfies f in the list l .
440
441
442
443       val find_opt : f:('a -> bool) -> 'a list -> 'a option
444
445
446       find  ~f  l  returns the first element of the list l that satisfies the
447       predicate f .  Returns None if there is no value that  satisfies  f  in
448       the list l .
449
450
451       Since 4.05
452
453
454
455       val find_map : f:('a -> 'b option) -> 'a list -> 'b option
456
457
458       find_map  ~f l applies f to the elements of l in order, and returns the
459       first result of the form Some v , or None if none exist.
460
461
462       Since 4.10.0
463
464
465
466       val filter : f:('a -> bool) -> 'a list -> 'a list
467
468
469       filter ~f l returns all the elements of the list  l  that  satisfy  the
470       predicate f . The order of the elements in the input list is preserved.
471
472
473
474       val find_all : f:('a -> bool) -> 'a list -> 'a list
475
476
477       find_all is another name for ListLabels.filter .
478
479
480
481       val filteri : f:(int -> 'a -> bool) -> 'a list -> 'a list
482
483       Same  as  ListLabels.filter , but the predicate is applied to the index
484       of the element as first argument (counting from 0), and the element it‐
485       self as second argument.
486
487
488       Since 4.11.0
489
490
491
492       val partition : f:('a -> bool) -> 'a list -> 'a list * 'a list
493
494
495       partition  ~f l returns a pair of lists (l1, l2) , where l1 is the list
496       of all the elements of l that satisfy the predicate f , and l2  is  the
497       list of all the elements of l that do not satisfy f .  The order of the
498       elements in the input list is preserved.
499
500
501
502       val partition_map : f:('a -> ('b, 'c) Either.t) -> 'a list -> 'b list *
503       'c list
504
505
506       partition_map  f l returns a pair of lists (l1, l2) such that, for each
507       element x of the input list l :
508
509       -if f x is Left y1 , then y1 is in l1 , and
510
511       -if f x is Right y2 , then y2 is in l2 .
512
513       The output elements are included in l1 and l2 in the same relative  or‐
514       der as the corresponding input elements in l .
515
516       In particular, partition_map (fun x -> if f x then Left x else Right x)
517       l is equivalent to partition f l .
518
519
520       Since 4.12.0
521
522
523
524
525   Association lists
526       val assoc : 'a -> ('a * 'b) list -> 'b
527
528
529       assoc a l returns the value associated with key a in the list of  pairs
530       l  .  That  is, assoc a [ ...; (a,b); ...] = b if (a,b) is the leftmost
531       binding of a in list l .
532
533
534       Raises Not_found if there is no value associated with a in the list l .
535
536
537
538       val assoc_opt : 'a -> ('a * 'b) list -> 'b option
539
540
541       assoc_opt a l returns the value associated with key a in  the  list  of
542       pairs  l . That is, assoc_opt a [ ...; (a,b); ...] = Some b if (a,b) is
543       the leftmost binding of a in list l .  Returns  None  if  there  is  no
544       value associated with a in the list l .
545
546
547       Since 4.05
548
549
550
551       val assq : 'a -> ('a * 'b) list -> 'b
552
553       Same as ListLabels.assoc , but uses physical equality instead of struc‐
554       tural equality to compare keys.
555
556
557
558       val assq_opt : 'a -> ('a * 'b) list -> 'b option
559
560       Same as ListLabels.assoc_opt , but uses physical  equality  instead  of
561       structural equality to compare keys.
562
563
564       Since 4.05.0
565
566
567
568       val mem_assoc : 'a -> map:('a * 'b) list -> bool
569
570       Same  as ListLabels.assoc , but simply return true if a binding exists,
571       and false if no bindings exist for the given key.
572
573
574
575       val mem_assq : 'a -> map:('a * 'b) list -> bool
576
577       Same as ListLabels.mem_assoc , but uses physical  equality  instead  of
578       structural equality to compare keys.
579
580
581
582       val remove_assoc : 'a -> ('a * 'b) list -> ('a * 'b) list
583
584
585       remove_assoc  a  l  returns  the list of pairs l without the first pair
586       with key a , if any.  Not tail-recursive.
587
588
589
590       val remove_assq : 'a -> ('a * 'b) list -> ('a * 'b) list
591
592       Same as ListLabels.remove_assoc , but uses physical equality instead of
593       structural equality to compare keys. Not tail-recursive.
594
595
596
597
598   Lists of pairs
599       val split : ('a * 'b) list -> 'a list * 'b list
600
601       Transform  a  list  of pairs into a pair of lists: split [(a1,b1); ...;
602       (an,bn)] is ([a1; ...; an], [b1; ...; bn]) .  Not tail-recursive.
603
604
605
606       val combine : 'a list -> 'b list -> ('a * 'b) list
607
608       Transform a pair of lists into a list of pairs: combine [a1;  ...;  an]
609       [b1; ...; bn] is [(a1,b1); ...; (an,bn)] .
610
611
612       Raises  Invalid_argument  if  the two lists have different lengths. Not
613       tail-recursive.
614
615
616
617
618   Sorting
619       val sort : cmp:('a -> 'a -> int) -> 'a list -> 'a list
620
621       Sort a list in increasing order according to a comparison function. The
622       comparison  function must return 0 if its arguments compare as equal, a
623       positive integer if the first is greater, and a negative integer if the
624       first is smaller (see Array.sort for a complete specification). For ex‐
625       ample, compare is a suitable comparison function.  The  resulting  list
626       is sorted in increasing order.  ListLabels.sort is guaranteed to run in
627       constant heap space (in addition to the size of the  result  list)  and
628       logarithmic stack space.
629
630       The  current  implementation  uses Merge Sort. It runs in constant heap
631       space and logarithmic stack space.
632
633
634
635       val stable_sort : cmp:('a -> 'a -> int) -> 'a list -> 'a list
636
637       Same as ListLabels.sort , but the sorting algorithm is guaranteed to be
638       stable (i.e. elements that compare equal are kept in their original or‐
639       der).
640
641       The current implementation uses Merge Sort. It runs  in  constant  heap
642       space and logarithmic stack space.
643
644
645
646       val fast_sort : cmp:('a -> 'a -> int) -> 'a list -> 'a list
647
648       Same as ListLabels.sort or ListLabels.stable_sort , whichever is faster
649       on typical input.
650
651
652
653       val sort_uniq : cmp:('a -> 'a -> int) -> 'a list -> 'a list
654
655       Same as ListLabels.sort , but also remove duplicates.
656
657
658       Since 4.03.0
659
660
661
662       val merge : cmp:('a -> 'a -> int) -> 'a list -> 'a list -> 'a list
663
664       Merge two lists: Assuming that l1 and l2 are sorted  according  to  the
665       comparison  function  cmp  , merge ~cmp l1 l2 will return a sorted list
666       containing all the elements of l1 and l2 .  If several elements compare
667       equal,  the  elements  of  l1  will be before the elements of l2 .  Not
668       tail-recursive (sum of the lengths of the arguments).
669
670
671
672
673   Lists and Sequences
674       val to_seq : 'a list -> 'a Seq.t
675
676       Iterate on the list.
677
678
679       Since 4.07
680
681
682
683       val of_seq : 'a Seq.t -> 'a list
684
685       Create a list from a sequence.
686
687
688       Since 4.07
689
690
691
692
693
694OCamldoc                          2023-01-23                     ListLabels(3)