1List(3)                          OCaml library                         List(3)
2
3
4

NAME

6       List - List operations.
7

Module

9       Module   List
10

Documentation

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