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