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 fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
225
226
227       List.fold_left f a [b1; ...; bn] is f (... (f (f a b1) b2) ...) bn .
228
229
230
231       val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b
232
233
234       List.fold_right  f [a1; ...; an] b is f a1 (f a2 (... (f an b) ...))  .
235       Not tail-recursive.
236
237
238
239
240   Iterators on two lists
241       val iter2 : ('a -> 'b -> unit) -> 'a list -> 'b list -> unit
242
243
244       List.iter2 f [a1; ...; an] [b1; ...; bn] calls in turn f a1 b1; ...;  f
245       an bn .  Raise Invalid_argument if the two lists are determined to have
246       different lengths.
247
248
249
250       val map2 : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
251
252
253       List.map2 f [a1; ...; an] [b1; ...; bn] is [f a1 b1; ...; f  an  bn]  .
254       Raise  Invalid_argument if the two lists are determined to have differ‐
255       ent lengths.  Not tail-recursive.
256
257
258
259       val rev_map2 : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
260
261
262       List.rev_map2 f l1 l2 gives the same result as List.rev (  List.map2  f
263       l1 l2) , but is tail-recursive and more efficient.
264
265
266
267       val  fold_left2 : ('a -> 'b -> 'c -> 'a) -> 'a -> 'b list -> 'c list ->
268       'a
269
270
271       List.fold_left2 f a [b1; ...; bn] [c1; ...; cn] is f (... (f  (f  a  b1
272       c1)  b2  c2)  ...) bn cn .  Raise Invalid_argument if the two lists are
273       determined to have different lengths.
274
275
276
277       val fold_right2 : ('a -> 'b -> 'c -> 'c) -> 'a list -> 'b list -> 'c ->
278       'c
279
280
281       List.fold_right2  f  [a1;  ...; an] [b1; ...; bn] c is f a1 b1 (f a2 b2
282       (... (f an bn c) ...))  .  Raise Invalid_argument if the two lists  are
283       determined to have different lengths.  Not tail-recursive.
284
285
286
287
288   List scanning
289       val for_all : ('a -> bool) -> 'a list -> bool
290
291
292       for_all  p [a1; ...; an] checks if all elements of the list satisfy the
293       predicate p . That is, it returns (p a1) && (p a2) && ... && (p an) .
294
295
296
297       val exists : ('a -> bool) -> 'a list -> bool
298
299
300       exists p [a1; ...; an] checks if at least one element of the list  sat‐
301       isfies the predicate p . That is, it returns (p a1) || (p a2) || ... ||
302       (p an) .
303
304
305
306       val for_all2 : ('a -> 'b -> bool) -> 'a list -> 'b list -> bool
307
308       Same as  List.for_all  ,  but  for  a  two-argument  predicate.   Raise
309       Invalid_argument  if  the  two  lists  are determined to have different
310       lengths.
311
312
313
314       val exists2 : ('a -> 'b -> bool) -> 'a list -> 'b list -> bool
315
316       Same  as  List.exists  ,  but  for  a  two-argument  predicate.   Raise
317       Invalid_argument  if  the  two  lists  are determined to have different
318       lengths.
319
320
321
322       val mem : 'a -> 'a list -> bool
323
324
325       mem a l is true if and only if a is equal to an element of l .
326
327
328
329       val memq : 'a -> 'a list -> bool
330
331       Same as List.mem , but uses physical  equality  instead  of  structural
332       equality to compare list elements.
333
334
335
336
337   List searching
338       val find : ('a -> bool) -> 'a list -> 'a
339
340
341       find  p  l  returns  the first element of the list l that satisfies the
342       predicate p .  Raise Not_found if there is no value that satisfies p in
343       the list l .
344
345
346
347       val find_opt : ('a -> bool) -> 'a list -> 'a option
348
349
350       find_opt p l returns the first element of the list l that satisfies the
351       predicate p , or None if there is no value that satisfies p in the list
352       l .
353
354
355       Since 4.05
356
357
358
359       val filter : ('a -> bool) -> 'a list -> 'a list
360
361
362       filter  p  l  returns  all  the elements of the list l that satisfy the
363       predicate p .  The order of the elements in  the  input  list  is  pre‐
364       served.
365
366
367
368       val find_all : ('a -> bool) -> 'a list -> 'a list
369
370
371       find_all is another name for List.filter .
372
373
374
375       val partition : ('a -> bool) -> 'a list -> 'a list * 'a list
376
377
378       partition  p  l returns a pair of lists (l1, l2) , where l1 is the list
379       of all the elements of l that satisfy the predicate p , and l2  is  the
380       list of all the elements of l that do not satisfy p .  The order of the
381       elements in the input list is preserved.
382
383
384
385
386   Association lists
387       val assoc : 'a -> ('a * 'b) list -> 'b
388
389
390       assoc a l returns the value associated with key a in the list of  pairs
391       l  .  That  is, assoc a [ ...; (a,b); ...] = b if (a,b) is the leftmost
392       binding of a in list l .  Raise Not_found if there is no value  associ‐
393       ated with a in the list l .
394
395
396
397       val assoc_opt : 'a -> ('a * 'b) list -> 'b option
398
399
400       assoc_opt  a  l  returns the value associated with key a in the list of
401       pairs l . That is, assoc_opt a [ ...; (a,b); ...] = b if (a,b)  is  the
402       leftmost  binding  of  a in list l .  Returns None if there is no value
403       associated with a in the list l .
404
405
406       Since 4.05
407
408
409
410       val assq : 'a -> ('a * 'b) list -> 'b
411
412       Same as List.assoc , but uses physical equality instead  of  structural
413       equality to compare keys.
414
415
416
417       val assq_opt : 'a -> ('a * 'b) list -> 'b option
418
419       Same  as  List.assoc_opt , but uses physical equality instead of struc‐
420       tural equality to compare keys.
421
422
423       Since 4.05
424
425
426
427       val mem_assoc : 'a -> ('a * 'b) list -> bool
428
429       Same as List.assoc , but simply return true if a  binding  exists,  and
430       false if no bindings exist for the given key.
431
432
433
434       val mem_assq : 'a -> ('a * 'b) list -> bool
435
436       Same  as  List.mem_assoc , but uses physical equality instead of struc‐
437       tural equality to compare keys.
438
439
440
441       val remove_assoc : 'a -> ('a * 'b) list -> ('a * 'b) list
442
443
444       remove_assoc a l returns the list of pairs l  without  the  first  pair
445       with key a , if any.  Not tail-recursive.
446
447
448
449       val remove_assq : 'a -> ('a * 'b) list -> ('a * 'b) list
450
451       Same  as  List.remove_assoc  ,  but  uses  physical equality instead of
452       structural equality to compare keys.  Not tail-recursive.
453
454
455
456
457   Lists of pairs
458       val split : ('a * 'b) list -> 'a list * 'b list
459
460       Transform a list of pairs into a pair of lists:  split  [(a1,b1);  ...;
461       (an,bn)] is ([a1; ...; an], [b1; ...; bn]) .  Not tail-recursive.
462
463
464
465       val combine : 'a list -> 'b list -> ('a * 'b) list
466
467       Transform  a  pair of lists into a list of pairs: combine [a1; ...; an]
468       [b1; ...; bn] is [(a1,b1); ...; (an,bn)] .  Raise  Invalid_argument  if
469       the two lists have different lengths.  Not tail-recursive.
470
471
472
473
474   Sorting
475       val sort : ('a -> 'a -> int) -> 'a list -> 'a list
476
477       Sort  a  list  in  increasing order according to a comparison function.
478       The comparison function must return  0  if  its  arguments  compare  as
479       equal, a positive integer if the first is greater, and a negative inte‐
480       ger if the first is smaller (see Array.sort for a  complete  specifica‐
481       tion).   For  example,  compare is a suitable comparison function.  The
482       resulting list is sorted in increasing order.  List.sort is  guaranteed
483       to  run  in  constant heap space (in addition to the size of the result
484       list) and logarithmic stack space.
485
486       The current implementation uses Merge Sort. It runs  in  constant  heap
487       space and logarithmic stack space.
488
489
490
491       val stable_sort : ('a -> 'a -> int) -> 'a list -> 'a list
492
493       Same  as List.sort , but the sorting algorithm is guaranteed to be sta‐
494       ble (i.e. elements that compare equal are kept in their original order)
495       .
496
497       The  current  implementation  uses Merge Sort. It runs in constant heap
498       space and logarithmic stack space.
499
500
501
502       val fast_sort : ('a -> 'a -> int) -> 'a list -> 'a list
503
504       Same as List.sort or List.stable_sort , whichever is faster on  typical
505       input.
506
507
508
509       val sort_uniq : ('a -> 'a -> int) -> 'a list -> 'a list
510
511       Same as List.sort , but also remove duplicates.
512
513
514       Since 4.02.0
515
516
517
518       val merge : ('a -> 'a -> int) -> 'a list -> 'a list -> 'a list
519
520       Merge  two  lists:  Assuming that l1 and l2 are sorted according to the
521       comparison function cmp , merge cmp l1 l2 will  return  a  sorted  list
522       containing all the elements of l1 and l2 .  If several elements compare
523       equal, the elements of l1 will be before the  elements  of  l2  .   Not
524       tail-recursive (sum of the lengths of the arguments).
525
526
527
528
529   Iterators
530       val to_seq : 'a list -> 'a Seq.t
531
532       Iterate on the list
533
534
535       Since 4.07
536
537
538
539       val of_seq : 'a Seq.t -> 'a list
540
541       Create a list from the iterator
542
543
544       Since 4.07
545
546
547
548
549
550OCamldoc                          2019-07-30                           List(3)