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