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