1ListLabels(3) OCaml library ListLabels(3)
2
6 ListLabels - no description
7
9 Module ListLabels
10
12 Module ListLabels
13 : sig end
14 type 'a t = 'a list =
22 | []
23 | :: of 'a * 'a list
24 An alias for the type of lists.
27 List operations.
32 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 un‐
38 specified constant unit) is shown in parentheses.
39 The above considerations can usually be ignored if your lists are not
41 longer than about 10000 elements.
42 This module is intended to be used through StdLabels which replaces Ar‐
44 ray , Bytes , List and String with their labeled counterparts.
45 For example:
47 open StdLabels
48 let seq len = List.init ~f:(function i -> i) ~len
50 val length : 'a list -> int
53 Return the length (number of elements) of the given list.
55 val hd : 'a list -> 'a
59 Return the first element of the given list.
61 Raises Failure if the list is empty.
64 val compare_lengths : 'a list -> 'b list -> int
68 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 Since 4.05.0
75 val compare_length_with : 'a list -> len:int -> int
79 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 Since 4.05.0
86 val cons : 'a -> 'a list -> 'a list
90 cons x xs is x :: xs
93 Since 4.05.0
97 val tl : 'a list -> 'a list
101 Return the given list without its first element.
103 Raises Failure if the list is empty.
106 val nth : 'a list -> int -> 'a
110 Return the n -th element of the given list. The first element (head of
112 the list) is at position 0.
113 Raises Failure if the list is too short.
116 Raises Invalid_argument if n is negative.
119 val nth_opt : 'a list -> int -> 'a option
123 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 Since 4.05
129 Raises Invalid_argument if n is negative.
132 val rev : 'a list -> 'a list
136 List reversal.
138 val init : len:int -> f:(int -> 'a) -> 'a list
142 List.init len f is f 0; f 1; ...; f (len-1) , evaluated left to right.
145 Since 4.06.0
148 Raises Invalid_argument if len < 0 .
151 val append : 'a list -> 'a list -> 'a list
155 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 val rev_append : 'a list -> 'a list -> 'a list
163 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 val concat : 'a list list -> 'a list
172 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 val flatten : 'a list list -> 'a list
181 Same as concat . Not tail-recursive (length of the argument + length of
183 the longest sub-list).
184 Iterators
189 val iter : f:('a -> unit) -> 'a list -> unit
190 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 val iteri : f:(int -> 'a -> unit) -> 'a list -> unit
198 Same as List.iter , but the function is applied to the index of the el‐
200 ement as first argument (counting from 0), and the element itself as
201 second argument.
202 Since 4.00.0
205 val map : f:('a -> 'b) -> 'a list -> 'b list
209 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 val mapi : f:(int -> 'a -> 'b) -> 'a list -> 'b list
218 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 Since 4.00.0
225 val rev_map : f:('a -> 'b) -> 'a list -> 'b list
229 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 val filter_map : f:('a -> 'b option) -> 'a list -> 'b list
237 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 Since 4.08.0
244 val concat_map : f:('a -> 'b list) -> 'a list -> 'b list
248 List.concat_map f l gives the same result as List.concat ( List.map f
251 l) . Tail-recursive.
252 Since 4.10.0
255 val fold_left_map : f:('a -> 'b -> 'a * 'c) -> init:'a -> 'b list -> 'a
259 * 'c list
260 fold_left_map is a combination of fold_left and map hat threads an ac‐
263 cumulator through calls to f
264 Since 4.11.0
268 val fold_left : f:('a -> 'b -> 'a) -> init:'a -> 'b list -> 'a
272 List.fold_left f a [b1; ...; bn] is f (... (f (f a b1) b2) ...) bn .
275 val fold_right : f:('a -> 'b -> 'b) -> 'a list -> init:'b -> 'b
279 List.fold_right f [a1; ...; an] b is f a1 (f a2 (... (f an b) ...)) .
282 Not tail-recursive.
283 Iterators on two lists
288 val iter2 : f:('a -> 'b -> unit) -> 'a list -> 'b list -> unit
289 List.iter2 f [a1; ...; an] [b1; ...; bn] calls in turn f a1 b1; ...; f
292 an bn .
293 Raises Invalid_argument if the two lists are determined to have differ‐
296 ent lengths.
297 val map2 : f:('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
301 List.map2 f [a1; ...; an] [b1; ...; bn] is [f a1 b1; ...; f an bn] .
304 Raises Invalid_argument if the two lists are determined to have differ‐
307 ent lengths. Not tail-recursive.
308 val rev_map2 : f:('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
312 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 val fold_left2 : f:('a -> 'b -> 'c -> 'a) -> init:'a -> 'b list -> 'c
320 list -> 'a
321 List.fold_left2 f a [b1; ...; bn] [c1; ...; cn] is f (... (f (f a b1
324 c1) b2 c2) ...) bn cn .
325 Raises Invalid_argument if the two lists are determined to have differ‐
328 ent lengths.
329 val fold_right2 : f:('a -> 'b -> 'c -> 'c) -> 'a list -> 'b list ->
333 init:'c -> 'c
334 List.fold_right2 f [a1; ...; an] [b1; ...; bn] c is f a1 b1 (f a2 b2
337 (... (f an bn c) ...)) .
338 Raises Invalid_argument if the two lists are determined to have differ‐
341 ent lengths. Not tail-recursive.
342 List scanning
347 val for_all : f:('a -> bool) -> 'a list -> bool
348 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 val exists : f:('a -> bool) -> 'a list -> bool
356 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 val for_all2 : f:('a -> 'b -> bool) -> 'a list -> 'b list -> bool
365 Same as List.for_all , but for a two-argument predicate.
367 Raises Invalid_argument if the two lists are determined to have differ‐
370 ent lengths.
371 val exists2 : f:('a -> 'b -> bool) -> 'a list -> 'b list -> bool
375 Same as List.exists , but for a two-argument predicate.
377 Raises Invalid_argument if the two lists are determined to have differ‐
380 ent lengths.
381 val mem : 'a -> set:'a list -> bool
385 mem a l is true if and only if a is equal to an element of l .
388 val memq : 'a -> set:'a list -> bool
392 Same as List.mem , but uses physical equality instead of structural
394 equality to compare list elements.
395 List searching
400 val find : f:('a -> bool) -> 'a list -> 'a
401 find p l returns the first element of the list l that satisfies the
404 predicate p .
405 Raises Not_found if there is no value that satisfies p in the list l .
408 val find_opt : f:('a -> bool) -> 'a list -> 'a option
412 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 Since 4.05
420 val find_map : f:('a -> 'b option) -> 'a list -> 'b option
424 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 Since 4.10.0
431 val filter : f:('a -> bool) -> 'a list -> 'a list
435 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 val find_all : f:('a -> bool) -> 'a list -> 'a list
443 find_all is another name for List.filter .
446 val filteri : f:(int -> 'a -> bool) -> 'a list -> 'a list
450 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 Since 4.11.0
457 val partition : f:('a -> bool) -> 'a list -> 'a list * 'a list
461 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 Association lists
472 val assoc : 'a -> ('a * 'b) list -> 'b
473 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 Raises Not_found if there is no value associated with a in the list l .
481 val assoc_opt : 'a -> ('a * 'b) list -> 'b option
485 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 Since 4.05
494 val assq : 'a -> ('a * 'b) list -> 'b
498 Same as List.assoc , but uses physical equality instead of structural
500 equality to compare keys.
501 val assq_opt : 'a -> ('a * 'b) list -> 'b option
505 Same as List.assoc_opt , but uses physical equality instead of struc‐
507 tural equality to compare keys.
508 Since 4.05.0
511 val mem_assoc : 'a -> map:('a * 'b) list -> bool
515 Same as List.assoc , but simply return true if a binding exists, and
517 false if no bindings exist for the given key.
518 val mem_assq : 'a -> map:('a * 'b) list -> bool
522 Same as List.mem_assoc , but uses physical equality instead of struc‐
524 tural equality to compare keys.
525 val remove_assoc : 'a -> ('a * 'b) list -> ('a * 'b) list
529 remove_assoc a l returns the list of pairs l without the first pair
532 with key a , if any. Not tail-recursive.
533 val remove_assq : 'a -> ('a * 'b) list -> ('a * 'b) list
537 Same as List.remove_assoc , but uses physical equality instead of
539 structural equality to compare keys. Not tail-recursive.
540 Lists of pairs
545 val split : ('a * 'b) list -> 'a list * 'b list
546 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 val combine : 'a list -> 'b list -> ('a * 'b) list
553 Transform a pair of lists into a list of pairs: combine [a1; ...; an]
555 [b1; ...; bn] is [(a1,b1); ...; (an,bn)] .
556 Raises Invalid_argument if the two lists have different lengths. Not
559 tail-recursive.
560 Sorting
565 val sort : cmp:('a -> 'a -> int) -> 'a list -> 'a list
566 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 ex‐
571 ample, 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 The current implementation uses Merge Sort. It runs in constant heap
577 space and logarithmic stack space.
578 val stable_sort : cmp:('a -> 'a -> int) -> 'a list -> 'a list
582 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 The current implementation uses Merge Sort. It runs in constant heap
588 space and logarithmic stack space.
589 val fast_sort : cmp:('a -> 'a -> int) -> 'a list -> 'a list
593 Same as List.sort or List.stable_sort , whichever is faster on typical
595 input.
596 val sort_uniq : cmp:('a -> 'a -> int) -> 'a list -> 'a list
600 Same as List.sort , but also remove duplicates.
602 Since 4.03.0
605 val merge : cmp:('a -> 'a -> int) -> 'a list -> 'a list -> 'a list
609 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 Iterators
620 val to_seq : 'a list -> 'a Seq.t
621 Iterate on the list
623 Since 4.07
626 val of_seq : 'a Seq.t -> 'a list
630 Create a list from the iterator
632 Since 4.07
635OCamldoc 2021-01-26 ListLabels(3)