1Stdlib.ListLabels(3) OCaml library Stdlib.ListLabels(3)
2
6 Stdlib.ListLabels - no description
7
9 Module Stdlib.ListLabels
10
12 Module ListLabels
13 : (module Stdlib__listLabels)
14 type 'a t = 'a list =
22 | []
23 | (::) of 'a * 'a list
24 An alias for the type of lists.
27 val length : 'a list -> int
31 Return the length (number of elements) of the given list.
33 val compare_lengths : 'a list -> 'b list -> int
37 Compare the lengths of two lists. compare_lengths l1 l2 is equivalent
39 to compare (length l1) (length l2) , except that the computation stops
40 after reaching the end of the shortest list.
41 Since 4.05.0
44 val compare_length_with : 'a list -> len:int -> int
48 Compare the length of a list to an integer. compare_length_with l len
50 is equivalent to compare (length l) len , except that the computation
51 stops after at most len iterations on the list.
52 Since 4.05.0
55 val cons : 'a -> 'a list -> 'a list
59 cons x xs is x :: xs
62 Since 4.05.0
66 val hd : 'a list -> 'a
70 Return the first element of the given list.
72 Raises Failure if the list is empty.
75 val tl : 'a list -> 'a list
79 Return the given list without its first element.
81 Raises Failure if the list is empty.
84 val nth : 'a list -> int -> 'a
88 Return the n -th element of the given list. The first element (head of
90 the list) is at position 0.
91 Raises Failure if the list is too short.
94 Raises Invalid_argument if n is negative.
97 val nth_opt : 'a list -> int -> 'a option
101 Return the n -th element of the given list. The first element (head of
103 the list) is at position 0. Return None if the list is too short.
104 Since 4.05
107 Raises Invalid_argument if n is negative.
110 val rev : 'a list -> 'a list
114 List reversal.
116 val init : len:int -> f:(int -> 'a) -> 'a list
120 init ~len ~f is f 0; f 1; ...; f (len-1) , evaluated left to right.
123 Since 4.06.0
126 Raises Invalid_argument if len < 0 .
129 val append : 'a list -> 'a list -> 'a list
133 Concatenate two lists. Same function as the infix operator @ . Not
135 tail-recursive (length of the first argument). The @ operator is not
136 tail-recursive either.
137 val rev_append : 'a list -> 'a list -> 'a list
141 rev_append l1 l2 reverses l1 and concatenates it with l2 . This is
144 equivalent to ( ListLabels.rev l1) @ l2 , but rev_append is tail-recur‐
145 sive and more efficient.
146 val concat : 'a list list -> 'a list
150 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 val flatten : 'a list list -> 'a list
159 Same as ListLabels.concat . Not tail-recursive (length of the argument
161 + length of the longest sub-list).
162 Comparison
167 val equal : eq:('a -> 'a -> bool) -> 'a list -> 'a list -> bool
168 equal eq [a1; ...; an] [b1; ..; bm] holds when the two input lists have
171 the same length, and for each pair of elements ai , bi at the same po‐
172 sition we have eq ai bi .
173 Note: the eq function may be called even if the lists have different
175 length. If you know your equality function is costly, you may want to
176 check ListLabels.compare_lengths first.
177 Since 4.12.0
180 val compare : cmp:('a -> 'a -> int) -> 'a list -> 'a list -> int
184 compare cmp [a1; ...; an] [b1; ...; bm] performs a lexicographic com‐
187 parison of the two input lists, using the same 'a -> 'a -> int inter‐
188 face as compare :
189 - a1 :: l1 is smaller than a2 :: l2 (negative result) if a1 is smaller
192 than a2 , or if they are equal (0 result) and l1 is smaller than l2
193 -the empty list [] is strictly smaller than non-empty lists
196 Note: the cmp function will be called even if the lists have different
198 lengths.
199 Since 4.12.0
202 Iterators
207 val iter : f:('a -> unit) -> 'a list -> unit
208 iter ~f [a1; ...; an] applies function f in turn to a1; ...; an . It is
211 equivalent to begin f a1; f a2; ...; f an; () end .
212 val iteri : f:(int -> 'a -> unit) -> 'a list -> unit
216 Same as ListLabels.iter , but the function is applied to the index of
218 the element as first argument (counting from 0), and the element itself
219 as second argument.
220 Since 4.00.0
223 val map : f:('a -> 'b) -> 'a list -> 'b list
227 map ~f [a1; ...; an] applies function f to a1, ..., an , and builds the
230 list [f a1; ...; f an] with the results returned by f . Not tail-recur‐
231 sive.
232 val mapi : f:(int -> 'a -> 'b) -> 'a list -> 'b list
236 Same as ListLabels.map , but the function is applied to the index of
238 the element as first argument (counting from 0), and the element itself
239 as second argument. Not tail-recursive.
240 Since 4.00.0
243 val rev_map : f:('a -> 'b) -> 'a list -> 'b list
247 rev_map ~f l gives the same result as ListLabels.rev ( ListLabels.map f
250 l) , but is tail-recursive and more efficient.
251 val filter_map : f:('a -> 'b option) -> 'a list -> 'b list
255 filter_map ~f l applies f to every element of l , filters out the None
258 elements and returns the list of the arguments of the Some elements.
259 Since 4.08.0
262 val concat_map : f:('a -> 'b list) -> 'a list -> 'b list
266 concat_map ~f l gives the same result as ListLabels.concat ( ListLa‐
269 bels.map f l) . Tail-recursive.
270 Since 4.10.0
273 val fold_left_map : f:('a -> 'b -> 'a * 'c) -> init:'a -> 'b list -> 'a
277 * 'c list
278 fold_left_map is a combination of fold_left and map that threads an
281 accumulator through calls to f .
282 Since 4.11.0
285 val fold_left : f:('a -> 'b -> 'a) -> init:'a -> 'b list -> 'a
289 fold_left ~f ~init [b1; ...; bn] is f (... (f (f init b1) b2) ...) bn .
292 val fold_right : f:('a -> 'b -> 'b) -> 'a list -> init:'b -> 'b
296 fold_right ~f [a1; ...; an] ~init is f a1 (f a2 (... (f an init) ...))
299 . Not tail-recursive.
300 Iterators on two lists
305 val iter2 : f:('a -> 'b -> unit) -> 'a list -> 'b list -> unit
306 iter2 ~f [a1; ...; an] [b1; ...; bn] calls in turn f a1 b1; ...; f an
309 bn .
310 Raises Invalid_argument if the two lists are determined to have differ‐
313 ent lengths.
314 val map2 : f:('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
318 map2 ~f [a1; ...; an] [b1; ...; bn] is [f a1 b1; ...; f an bn] .
321 Raises Invalid_argument if the two lists are determined to have differ‐
324 ent lengths. Not tail-recursive.
325 val rev_map2 : f:('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
329 rev_map2 ~f l1 l2 gives the same result as ListLabels.rev ( ListLa‐
332 bels.map2 f l1 l2) , but is tail-recursive and more efficient.
333 val fold_left2 : f:('a -> 'b -> 'c -> 'a) -> init:'a -> 'b list -> 'c
337 list -> 'a
338 fold_left2 ~f ~init [a1; ...; an] [b1; ...; bn] is f (... (f (f init a1
341 b1) a2 b2) ...) an bn .
342 Raises Invalid_argument if the two lists are determined to have differ‐
345 ent lengths.
346 val fold_right2 : f:('a -> 'b -> 'c -> 'c) -> 'a list -> 'b list ->
350 init:'c -> 'c
351 fold_right2 ~f [a1; ...; an] [b1; ...; bn] ~init is f a1 b1 (f a2 b2
354 (... (f an bn init) ...)) .
355 Raises Invalid_argument if the two lists are determined to have differ‐
358 ent lengths. Not tail-recursive.
359 List scanning
364 val for_all : f:('a -> bool) -> 'a list -> bool
365 for_all ~f [a1; ...; an] checks if all elements of the list satisfy the
368 predicate f . That is, it returns (f a1) && (f a2) && ... && (f an) for
369 a non-empty list and true if the list is empty.
370 val exists : f:('a -> bool) -> 'a list -> bool
374 exists ~f [a1; ...; an] checks if at least one element of the list sat‐
377 isfies the predicate f . That is, it returns (f a1) || (f a2) || ... ||
378 (f an) for a non-empty list and false if the list is empty.
379 val for_all2 : f:('a -> 'b -> bool) -> 'a list -> 'b list -> bool
383 Same as ListLabels.for_all , but for a two-argument predicate.
385 Raises Invalid_argument if the two lists are determined to have differ‐
388 ent lengths.
389 val exists2 : f:('a -> 'b -> bool) -> 'a list -> 'b list -> bool
393 Same as ListLabels.exists , but for a two-argument predicate.
395 Raises Invalid_argument if the two lists are determined to have differ‐
398 ent lengths.
399 val mem : 'a -> set:'a list -> bool
403 mem a ~set is true if and only if a is equal to an element of set .
406 val memq : 'a -> set:'a list -> bool
410 Same as ListLabels.mem , but uses physical equality instead of struc‐
412 tural equality to compare list elements.
413 List searching
418 val find : f:('a -> bool) -> 'a list -> 'a
419 find ~f l returns the first element of the list l that satisfies the
422 predicate f .
423 Raises Not_found if there is no value that satisfies f in the list l .
426 val find_opt : f:('a -> bool) -> 'a list -> 'a option
430 find ~f l returns the first element of the list l that satisfies the
433 predicate f . Returns None if there is no value that satisfies f in
434 the list l .
435 Since 4.05
438 val find_map : f:('a -> 'b option) -> 'a list -> 'b option
442 find_map ~f l applies f to the elements of l in order, and returns the
445 first result of the form Some v , or None if none exist.
446 Since 4.10.0
449 val filter : f:('a -> bool) -> 'a list -> 'a list
453 filter ~f l returns all the elements of the list l that satisfy the
456 predicate f . The order of the elements in the input list is preserved.
457 val find_all : f:('a -> bool) -> 'a list -> 'a list
461 find_all is another name for ListLabels.filter .
464 val filteri : f:(int -> 'a -> bool) -> 'a list -> 'a list
468 Same as ListLabels.filter , but the predicate is applied to the index
470 of the element as first argument (counting from 0), and the element it‐
471 self as second argument.
472 Since 4.11.0
475 val partition : f:('a -> bool) -> 'a list -> 'a list * 'a list
479 partition ~f l returns a pair of lists (l1, l2) , where l1 is the list
482 of all the elements of l that satisfy the predicate f , and l2 is the
483 list of all the elements of l that do not satisfy f . The order of the
484 elements in the input list is preserved.
485 val partition_map : f:('a -> ('b, 'c) Either.t) -> 'a list -> 'b list *
489 'c list
490 partition_map f l returns a pair of lists (l1, l2) such that, for each
493 element x of the input list l :
494 -if f x is Left y1 , then y1 is in l1 , and
496 -if f x is Right y2 , then y2 is in l2 .
498 The output elements are included in l1 and l2 in the same relative or‐
500 der as the corresponding input elements in l .
501 In particular, partition_map (fun x -> if f x then Left x else Right x)
503 l is equivalent to partition f l .
504 Since 4.12.0
507 Association lists
512 val assoc : 'a -> ('a * 'b) list -> 'b
513 assoc a l returns the value associated with key a in the list of pairs
516 l . That is, assoc a [ ...; (a,b); ...] = b if (a,b) is the leftmost
517 binding of a in list l .
518 Raises Not_found if there is no value associated with a in the list l .
521 val assoc_opt : 'a -> ('a * 'b) list -> 'b option
525 assoc_opt a l returns the value associated with key a in the list of
528 pairs l . That is, assoc_opt a [ ...; (a,b); ...] = Some b if (a,b) is
529 the leftmost binding of a in list l . Returns None if there is no
530 value associated with a in the list l .
531 Since 4.05
534 val assq : 'a -> ('a * 'b) list -> 'b
538 Same as ListLabels.assoc , but uses physical equality instead of struc‐
540 tural equality to compare keys.
541 val assq_opt : 'a -> ('a * 'b) list -> 'b option
545 Same as ListLabels.assoc_opt , but uses physical equality instead of
547 structural equality to compare keys.
548 Since 4.05.0
551 val mem_assoc : 'a -> map:('a * 'b) list -> bool
555 Same as ListLabels.assoc , but simply return true if a binding exists,
557 and false if no bindings exist for the given key.
558 val mem_assq : 'a -> map:('a * 'b) list -> bool
562 Same as ListLabels.mem_assoc , but uses physical equality instead of
564 structural equality to compare keys.
565 val remove_assoc : 'a -> ('a * 'b) list -> ('a * 'b) list
569 remove_assoc a l returns the list of pairs l without the first pair
572 with key a , if any. Not tail-recursive.
573 val remove_assq : 'a -> ('a * 'b) list -> ('a * 'b) list
577 Same as ListLabels.remove_assoc , but uses physical equality instead of
579 structural equality to compare keys. Not tail-recursive.
580 Lists of pairs
585 val split : ('a * 'b) list -> 'a list * 'b list
586 Transform a list of pairs into a pair of lists: split [(a1,b1); ...;
588 (an,bn)] is ([a1; ...; an], [b1; ...; bn]) . Not tail-recursive.
589 val combine : 'a list -> 'b list -> ('a * 'b) list
593 Transform a pair of lists into a list of pairs: combine [a1; ...; an]
595 [b1; ...; bn] is [(a1,b1); ...; (an,bn)] .
596 Raises Invalid_argument if the two lists have different lengths. Not
599 tail-recursive.
600 Sorting
605 val sort : cmp:('a -> 'a -> int) -> 'a list -> 'a list
606 Sort a list in increasing order according to a comparison function. The
608 comparison function must return 0 if its arguments compare as equal, a
609 positive integer if the first is greater, and a negative integer if the
610 first is smaller (see Array.sort for a complete specification). For ex‐
611 ample, compare is a suitable comparison function. The resulting list
612 is sorted in increasing order. ListLabels.sort is guaranteed to run in
613 constant heap space (in addition to the size of the result list) and
614 logarithmic stack space.
615 The current implementation uses Merge Sort. It runs in constant heap
617 space and logarithmic stack space.
618 val stable_sort : cmp:('a -> 'a -> int) -> 'a list -> 'a list
622 Same as ListLabels.sort , but the sorting algorithm is guaranteed to be
624 stable (i.e. elements that compare equal are kept in their original or‐
625 der).
626 The current implementation uses Merge Sort. It runs in constant heap
628 space and logarithmic stack space.
629 val fast_sort : cmp:('a -> 'a -> int) -> 'a list -> 'a list
633 Same as ListLabels.sort or ListLabels.stable_sort , whichever is faster
635 on typical input.
636 val sort_uniq : cmp:('a -> 'a -> int) -> 'a list -> 'a list
640 Same as ListLabels.sort , but also remove duplicates.
642 Since 4.03.0
645 val merge : cmp:('a -> 'a -> int) -> 'a list -> 'a list -> 'a list
649 Merge two lists: Assuming that l1 and l2 are sorted according to the
651 comparison function cmp , merge ~cmp l1 l2 will return a sorted list
652 containing all the elements of l1 and l2 . If several elements compare
653 equal, the elements of l1 will be before the elements of l2 . Not
654 tail-recursive (sum of the lengths of the arguments).
655 Iterators
660 val to_seq : 'a list -> 'a Seq.t
661 Iterate on the list.
663 Since 4.07
666 val of_seq : 'a Seq.t -> 'a list
670 Create a list from the iterator.
672 Since 4.07
675OCamldoc 2021-07-22 Stdlib.ListLabels(3)