.TH "Stdlib.ListLabels" 3o 2020-10-30 OCamldoc "OCaml library" .SH NAME Stdlib.ListLabels \- no description .SH Module Module Stdlib.ListLabels .SH Documentation .sp Module .BI "ListLabels" : .B (module Stdlib__listLabels) .sp .sp .sp .sp .I type .B 'a .I t = .B 'a list = | [] | :: .B of .B 'a * 'a list .sp An alias for the type of lists\&. .sp .PP List operations\&. .sp Some functions are flagged as not tail\-recursive\&. A tail\-recursive function uses constant stack space, while a non\-tail\-recursive function uses stack space proportional to the length of its list argument, which can be a problem with very long lists\&. When the function takes several list arguments, an approximate formula giving stack usage (in some unspecified constant unit) is shown in parentheses\&. .sp The above considerations can usually be ignored if your lists are not longer than about 10000 elements\&. .sp This module is intended to be used through .ft B StdLabels .ft R which replaces .ft B Array .ft R , .ft B Bytes .ft R , .ft B List .ft R and .ft B String .ft R with their labeled counterparts\&. .sp For example: .EX .ft B .br \& open StdLabels .br \& .br \& let seq len = List\&.init ~f:(function i \-> i) ~len .br \& .ft R .EE .PP .I val length : .B 'a list -> int .sp Return the length (number of elements) of the given list\&. .sp .I val hd : .B 'a list -> 'a .sp Return the first element of the given list\&. .sp .B "Raises Failure" if the list is empty\&. .sp .I val compare_lengths : .B 'a list -> 'b list -> int .sp Compare the lengths of two lists\&. .ft B compare_lengths l1 l2 .ft R is equivalent to .ft B compare (length l1) (length l2) .ft R , except that the computation stops after itering on the shortest list\&. .sp .B "Since" 4.05.0 .sp .I val compare_length_with : .B 'a list -> len:int -> int .sp Compare the length of a list to an integer\&. .ft B compare_length_with l n .ft R is equivalent to .ft B compare (length l) n .ft R , except that the computation stops after at most .ft B n .ft R iterations on the list\&. .sp .B "Since" 4.05.0 .sp .I val cons : .B 'a -> 'a list -> 'a list .sp .ft B cons x xs .ft R is .ft B x :: xs .ft R .sp .B "Since" 4.05.0 .sp .I val tl : .B 'a list -> 'a list .sp Return the given list without its first element\&. .sp .B "Raises Failure" if the list is empty\&. .sp .I val nth : .B 'a list -> int -> 'a .sp Return the .ft B n .ft R \-th element of the given list\&. The first element (head of the list) is at position 0\&. .sp .B "Raises Failure" if the list is too short\&. .sp .B "Raises Invalid_argument" if .ft B n .ft R is negative\&. .sp .I val nth_opt : .B 'a list -> int -> 'a option .sp Return the .ft B n .ft R \-th element of the given list\&. The first element (head of the list) is at position 0\&. Return .ft B None .ft R if the list is too short\&. .sp .B "Since" 4.05 .sp .B "Raises Invalid_argument" if .ft B n .ft R is negative\&. .sp .I val rev : .B 'a list -> 'a list .sp List reversal\&. .sp .I val init : .B len:int -> f:(int -> 'a) -> 'a list .sp .ft B List\&.init len f .ft R is .ft B f 0; f 1; \&.\&.\&.; f (len\-1) .ft R , evaluated left to right\&. .sp .B "Since" 4.06.0 .sp .B "Raises Invalid_argument" if .ft B len < 0 .ft R \&. .sp .I val append : .B 'a list -> 'a list -> 'a list .sp Catenate two lists\&. Same function as the infix operator .ft B @ .ft R \&. Not tail\-recursive (length of the first argument)\&. The .ft B @ .ft R operator is not tail\-recursive either\&. .sp .I val rev_append : .B 'a list -> 'a list -> 'a list .sp .ft B List\&.rev_append l1 l2 .ft R reverses .ft B l1 .ft R and concatenates it with .ft B l2 .ft R \&. This is equivalent to .ft B ( .ft R .ft B List\&.rev .ft R .ft B l1) @ l2 .ft R , but .ft B rev_append .ft R is tail\-recursive and more efficient\&. .sp .I val concat : .B 'a list list -> 'a list .sp Concatenate a list of lists\&. The elements of the argument are all concatenated together (in the same order) to give the result\&. Not tail\-recursive (length of the argument + length of the longest sub\-list)\&. .sp .I val flatten : .B 'a list list -> 'a list .sp Same as .ft B concat .ft R \&. Not tail\-recursive (length of the argument + length of the longest sub\-list)\&. .sp .PP .SS Iterators .PP .I val iter : .B f:('a -> unit) -> 'a list -> unit .sp .ft B List\&.iter f [a1; \&.\&.\&.; an] .ft R applies function .ft B f .ft R in turn to .ft B a1; \&.\&.\&.; an .ft R \&. It is equivalent to .ft B begin f a1; f a2; \&.\&.\&.; f an; () end .ft R \&. .sp .I val iteri : .B f:(int -> 'a -> unit) -> 'a list -> unit .sp Same as .ft B List\&.iter .ft R , but the function is applied to the index of the element as first argument (counting from 0), and the element itself as second argument\&. .sp .B "Since" 4.00.0 .sp .I val map : .B f:('a -> 'b) -> 'a list -> 'b list .sp .ft B List\&.map f [a1; \&.\&.\&.; an] .ft R applies function .ft B f .ft R to .ft B a1, \&.\&.\&., an .ft R , and builds the list .ft B [f a1; \&.\&.\&.; f an] .ft R with the results returned by .ft B f .ft R \&. Not tail\-recursive\&. .sp .I val mapi : .B f:(int -> 'a -> 'b) -> 'a list -> 'b list .sp Same as .ft B List\&.map .ft R , but the function is applied to the index of the element as first argument (counting from 0), and the element itself as second argument\&. .sp .B "Since" 4.00.0 .sp .I val rev_map : .B f:('a -> 'b) -> 'a list -> 'b list .sp .ft B List\&.rev_map f l .ft R gives the same result as .ft B List\&.rev .ft R .ft B ( .ft R .ft B List\&.map .ft R .ft B f l) .ft R , but is tail\-recursive and more efficient\&. .sp .I val filter_map : .B f:('a -> 'b option) -> 'a list -> 'b list .sp .ft B filter_map f l .ft R applies .ft B f .ft R to every element of .ft B l .ft R , filters out the .ft B None .ft R elements and returns the list of the arguments of the .ft B Some .ft R elements\&. .sp .B "Since" 4.08.0 .sp .I val concat_map : .B f:('a -> 'b list) -> 'a list -> 'b list .sp .ft B List\&.concat_map f l .ft R gives the same result as .ft B List\&.concat .ft R .ft B ( .ft R .ft B List\&.map .ft R .ft B f l) .ft R \&. Tail\-recursive\&. .sp .B "Since" 4.10.0 .sp .I val fold_left_map : .B f:('a -> 'b -> 'a * 'c) -> init:'a -> 'b list -> 'a * 'c list .sp .ft B fold_left_map .ft R is a combination of .ft B fold_left .ft R and .ft B map .ft R hat threads an accumulator through calls to .ft B f .ft R .sp .B "Since" 4.11.0 .sp .I val fold_left : .B f:('a -> 'b -> 'a) -> init:'a -> 'b list -> 'a .sp .ft B List\&.fold_left f a [b1; \&.\&.\&.; bn] .ft R is .ft B f (\&.\&.\&. (f (f a b1) b2) \&.\&.\&.) bn .ft R \&. .sp .I val fold_right : .B f:('a -> 'b -> 'b) -> 'a list -> init:'b -> 'b .sp .ft B List\&.fold_right f [a1; \&.\&.\&.; an] b .ft R is .ft B f a1 (f a2 (\&.\&.\&. (f an b) \&.\&.\&.)) .ft R \&. Not tail\-recursive\&. .sp .PP .SS Iterators on two lists .PP .I val iter2 : .B f:('a -> 'b -> unit) -> 'a list -> 'b list -> unit .sp .ft B List\&.iter2 f [a1; \&.\&.\&.; an] [b1; \&.\&.\&.; bn] .ft R calls in turn .ft B f a1 b1; \&.\&.\&.; f an bn .ft R \&. .sp .B "Raises Invalid_argument" if the two lists are determined to have different lengths\&. .sp .I val map2 : .B f:('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list .sp .ft B List\&.map2 f [a1; \&.\&.\&.; an] [b1; \&.\&.\&.; bn] .ft R is .ft B [f a1 b1; \&.\&.\&.; f an bn] .ft R \&. .sp .B "Raises Invalid_argument" if the two lists are determined to have different lengths\&. Not tail\-recursive\&. .sp .I val rev_map2 : .B f:('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list .sp .ft B List\&.rev_map2 f l1 l2 .ft R gives the same result as .ft B List\&.rev .ft R .ft B ( .ft R .ft B List\&.map2 .ft R .ft B f l1 l2) .ft R , but is tail\-recursive and more efficient\&. .sp .I val fold_left2 : .B f:('a -> 'b -> 'c -> 'a) -> init:'a -> 'b list -> 'c list -> 'a .sp .ft B List\&.fold_left2 f a [b1; \&.\&.\&.; bn] [c1; \&.\&.\&.; cn] .ft R is .ft B f (\&.\&.\&. (f (f a b1 c1) b2 c2) \&.\&.\&.) bn cn .ft R \&. .sp .B "Raises Invalid_argument" if the two lists are determined to have different lengths\&. .sp .I val fold_right2 : .B f:('a -> 'b -> 'c -> 'c) -> 'a list -> 'b list -> init:'c -> 'c .sp .ft B List\&.fold_right2 f [a1; \&.\&.\&.; an] [b1; \&.\&.\&.; bn] c .ft R is .ft B f a1 b1 (f a2 b2 (\&.\&.\&. (f an bn c) \&.\&.\&.)) .ft R \&. .sp .B "Raises Invalid_argument" if the two lists are determined to have different lengths\&. Not tail\-recursive\&. .sp .PP .SS List scanning .PP .I val for_all : .B f:('a -> bool) -> 'a list -> bool .sp .ft B for_all p [a1; \&.\&.\&.; an] .ft R checks if all elements of the list satisfy the predicate .ft B p .ft R \&. That is, it returns .ft B (p a1) && (p a2) && \&.\&.\&. && (p an) .ft R \&. .sp .I val exists : .B f:('a -> bool) -> 'a list -> bool .sp .ft B exists p [a1; \&.\&.\&.; an] .ft R checks if at least one element of the list satisfies the predicate .ft B p .ft R \&. That is, it returns .ft B (p a1) || (p a2) || \&.\&.\&. || (p an) .ft R \&. .sp .I val for_all2 : .B f:('a -> 'b -> bool) -> 'a list -> 'b list -> bool .sp Same as .ft B List\&.for_all .ft R , but for a two\-argument predicate\&. .sp .B "Raises Invalid_argument" if the two lists are determined to have different lengths\&. .sp .I val exists2 : .B f:('a -> 'b -> bool) -> 'a list -> 'b list -> bool .sp Same as .ft B List\&.exists .ft R , but for a two\-argument predicate\&. .sp .B "Raises Invalid_argument" if the two lists are determined to have different lengths\&. .sp .I val mem : .B 'a -> set:'a list -> bool .sp .ft B mem a l .ft R is true if and only if .ft B a .ft R is equal to an element of .ft B l .ft R \&. .sp .I val memq : .B 'a -> set:'a list -> bool .sp Same as .ft B List\&.mem .ft R , but uses physical equality instead of structural equality to compare list elements\&. .sp .PP .SS List searching .PP .I val find : .B f:('a -> bool) -> 'a list -> 'a .sp .ft B find p l .ft R returns the first element of the list .ft B l .ft R that satisfies the predicate .ft B p .ft R \&. .sp .B "Raises Not_found" if there is no value that satisfies .ft B p .ft R in the list .ft B l .ft R \&. .sp .I val find_opt : .B f:('a -> bool) -> 'a list -> 'a option .sp .ft B find p l .ft R returns the first element of the list .ft B l .ft R that satisfies the predicate .ft B p .ft R \&. Returns .ft B None .ft R if there is no value that satisfies .ft B p .ft R in the list .ft B l .ft R \&. .sp .B "Since" 4.05 .sp .I val find_map : .B f:('a -> 'b option) -> 'a list -> 'b option .sp .ft B find_map f l .ft R applies .ft B f .ft R to the elements of .ft B l .ft R in order, and returns the first result of the form .ft B Some v .ft R , or .ft B None .ft R if none exist\&. .sp .B "Since" 4.10.0 .sp .I val filter : .B f:('a -> bool) -> 'a list -> 'a list .sp .ft B filter p l .ft R returns all the elements of the list .ft B l .ft R that satisfy the predicate .ft B p .ft R \&. The order of the elements in the input list is preserved\&. .sp .I val find_all : .B f:('a -> bool) -> 'a list -> 'a list .sp .ft B find_all .ft R is another name for .ft B List\&.filter .ft R \&. .sp .I val filteri : .B f:(int -> 'a -> bool) -> 'a list -> 'a list .sp Same as .ft B List\&.filter .ft R , but the predicate is applied to the index of the element as first argument (counting from 0), and the element itself as second argument\&. .sp .B "Since" 4.11.0 .sp .I val partition : .B f:('a -> bool) -> 'a list -> 'a list * 'a list .sp .ft B partition p l .ft R returns a pair of lists .ft B (l1, l2) .ft R , where .ft B l1 .ft R is the list of all the elements of .ft B l .ft R that satisfy the predicate .ft B p .ft R , and .ft B l2 .ft R is the list of all the elements of .ft B l .ft R that do not satisfy .ft B p .ft R \&. The order of the elements in the input list is preserved\&. .sp .PP .SS Association lists .PP .I val assoc : .B 'a -> ('a * 'b) list -> 'b .sp .ft B assoc a l .ft R returns the value associated with key .ft B a .ft R in the list of pairs .ft B l .ft R \&. That is, .ft B assoc a [ \&.\&.\&.; (a,b); \&.\&.\&.] = b .ft R if .ft B (a,b) .ft R is the leftmost binding of .ft B a .ft R in list .ft B l .ft R \&. .sp .B "Raises Not_found" if there is no value associated with .ft B a .ft R in the list .ft B l .ft R \&. .sp .I val assoc_opt : .B 'a -> ('a * 'b) list -> 'b option .sp .ft B assoc_opt a l .ft R returns the value associated with key .ft B a .ft R in the list of pairs .ft B l .ft R \&. That is, .ft B assoc a [ \&.\&.\&.; (a,b); \&.\&.\&.] = b .ft R if .ft B (a,b) .ft R is the leftmost binding of .ft B a .ft R in list .ft B l .ft R \&. Returns .ft B None .ft R if there is no value associated with .ft B a .ft R in the list .ft B l .ft R \&. .sp .B "Since" 4.05 .sp .I val assq : .B 'a -> ('a * 'b) list -> 'b .sp Same as .ft B List\&.assoc .ft R , but uses physical equality instead of structural equality to compare keys\&. .sp .I val assq_opt : .B 'a -> ('a * 'b) list -> 'b option .sp Same as .ft B List\&.assoc_opt .ft R , but uses physical equality instead of structural equality to compare keys\&. .sp .B "Since" 4.05.0 .sp .I val mem_assoc : .B 'a -> map:('a * 'b) list -> bool .sp Same as .ft B List\&.assoc .ft R , but simply return true if a binding exists, and false if no bindings exist for the given key\&. .sp .I val mem_assq : .B 'a -> map:('a * 'b) list -> bool .sp Same as .ft B List\&.mem_assoc .ft R , but uses physical equality instead of structural equality to compare keys\&. .sp .I val remove_assoc : .B 'a -> ('a * 'b) list -> ('a * 'b) list .sp .ft B remove_assoc a l .ft R returns the list of pairs .ft B l .ft R without the first pair with key .ft B a .ft R , if any\&. Not tail\-recursive\&. .sp .I val remove_assq : .B 'a -> ('a * 'b) list -> ('a * 'b) list .sp Same as .ft B List\&.remove_assoc .ft R , but uses physical equality instead of structural equality to compare keys\&. Not tail\-recursive\&. .sp .PP .SS Lists of pairs .PP .I val split : .B ('a * 'b) list -> 'a list * 'b list .sp Transform a list of pairs into a pair of lists: .ft B split [(a1,b1); \&.\&.\&.; (an,bn)] .ft R is .ft B ([a1; \&.\&.\&.; an], [b1; \&.\&.\&.; bn]) .ft R \&. Not tail\-recursive\&. .sp .I val combine : .B 'a list -> 'b list -> ('a * 'b) list .sp Transform a pair of lists into a list of pairs: .ft B combine [a1; \&.\&.\&.; an] [b1; \&.\&.\&.; bn] .ft R is .ft B [(a1,b1); \&.\&.\&.; (an,bn)] .ft R \&. .sp .B "Raises Invalid_argument" if the two lists have different lengths\&. Not tail\-recursive\&. .sp .PP .SS Sorting .PP .I val sort : .B cmp:('a -> 'a -> int) -> 'a list -> 'a list .sp Sort a list in increasing order according to a comparison function\&. The comparison function must return 0 if its arguments compare as equal, a positive integer if the first is greater, and a negative integer if the first is smaller (see Array\&.sort for a complete specification)\&. For example, .ft B compare .ft R is a suitable comparison function\&. The resulting list is sorted in increasing order\&. .ft B List\&.sort .ft R is guaranteed to run in constant heap space (in addition to the size of the result list) and logarithmic stack space\&. .sp The current implementation uses Merge Sort\&. It runs in constant heap space and logarithmic stack space\&. .sp .I val stable_sort : .B cmp:('a -> 'a -> int) -> 'a list -> 'a list .sp Same as .ft B List\&.sort .ft R , but the sorting algorithm is guaranteed to be stable (i\&.e\&. elements that compare equal are kept in their original order) \&. .sp The current implementation uses Merge Sort\&. It runs in constant heap space and logarithmic stack space\&. .sp .I val fast_sort : .B cmp:('a -> 'a -> int) -> 'a list -> 'a list .sp Same as .ft B List\&.sort .ft R or .ft B List\&.stable_sort .ft R , whichever is faster on typical input\&. .sp .I val sort_uniq : .B cmp:('a -> 'a -> int) -> 'a list -> 'a list .sp Same as .ft B List\&.sort .ft R , but also remove duplicates\&. .sp .B "Since" 4.03.0 .sp .I val merge : .B cmp:('a -> 'a -> int) -> 'a list -> 'a list -> 'a list .sp Merge two lists: Assuming that .ft B l1 .ft R and .ft B l2 .ft R are sorted according to the comparison function .ft B cmp .ft R , .ft B merge cmp l1 l2 .ft R will return a sorted list containing all the elements of .ft B l1 .ft R and .ft B l2 .ft R \&. If several elements compare equal, the elements of .ft B l1 .ft R will be before the elements of .ft B l2 .ft R \&. Not tail\-recursive (sum of the lengths of the arguments)\&. .sp .PP .SS Iterators .PP .I val to_seq : .B 'a list -> 'a Seq.t .sp Iterate on the list .sp .B "Since" 4.07 .sp .I val of_seq : .B 'a Seq.t -> 'a list .sp Create a list from the iterator .sp .B "Since" 4.07 .sp