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

NAME

6       StdLabels.List - no description
7

Module

9       Module   StdLabels.List
10

Documentation

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