.TH "Stdlib.ListLabels" 3o 2020-01-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\&.
.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\&. Raise
.B Failure "hd"
if the list is empty\&.

.sp

.I val compare_lengths 
: 
.B 'a list -> 'b list -> int
.sp
Compare the lengths of two lists\&. 
.B compare_lengths l1 l2
is
equivalent to 
.B compare (length l1) (length l2)
, 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\&. 
.B compare_length_with l n
is
equivalent to 
.B compare (length l) n
, except that
the computation stops after at most 
.B n
iterations on the list\&.

.sp
.B "Since"
4.05.0

.sp

.I val cons 
: 
.B 'a -> 'a list -> 'a list
.sp

.B cons x xs
is 
.B x :: xs


.sp
.B "Since"
4.05.0

.sp

.I val tl 
: 
.B 'a list -> 'a list
.sp
Return the given list without its first element\&. Raise
.B Failure "tl"
if the list is empty\&.

.sp

.I val nth 
: 
.B 'a list -> int -> 'a
.sp
Return the 
.B n
\-th element of the given list\&.
The first element (head of the list) is at position 0\&.
Raise 
.B Failure "nth"
if the list is too short\&.
Raise 
.B Invalid_argument "List\&.nth"
if 
.B n
is negative\&.

.sp

.I val nth_opt 
: 
.B 'a list -> int -> 'a option
.sp
Return the 
.B n
\-th element of the given list\&.
The first element (head of the list) is at position 0\&.
Return 
.B None
if the list is too short\&.
Raise 
.B Invalid_argument "List\&.nth"
if 
.B n
is negative\&.

.sp
.B "Since"
4.05

.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

.B List\&.init len f
is 
.B f 0; f 1; \&.\&.\&.; f (len\-1)
, evaluated left to right\&.

.sp
.B "Since"
4.06.0

.sp
.B "Raises Invalid_argument"
if 
.B len < 0
\&.

.sp

.I val append 
: 
.B 'a list -> 'a list -> 'a list
.sp
Catenate two lists\&.  Same function as the infix operator 
.B @
\&.
Not tail\-recursive (length of the first argument)\&.  The 
.B @
operator is not tail\-recursive either\&.

.sp

.I val rev_append 
: 
.B 'a list -> 'a list -> 'a list
.sp

.B List\&.rev_append l1 l2
reverses 
.B l1
and concatenates it with 
.B l2
\&.
This is equivalent to 
.B (
.B List\&.rev
.B  l1) @ l2
, but 
.B rev_append
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 
.B concat
\&.  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

.B List\&.iter f [a1; \&.\&.\&.; an]
applies function 
.B f
in turn to
.B a1; \&.\&.\&.; an
\&. It is equivalent to
.B begin f a1; f a2; \&.\&.\&.; f an; () end
\&.

.sp

.I val iteri 
: 
.B f:(int -> 'a -> unit) -> 'a list -> unit
.sp
Same as 
.B List\&.iter
, 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

.B List\&.map f [a1; \&.\&.\&.; an]
applies function 
.B f
to 
.B a1, \&.\&.\&., an
,
and builds the list 
.B [f a1; \&.\&.\&.; f an]
with the results returned by 
.B f
\&.  Not tail\-recursive\&.

.sp

.I val mapi 
: 
.B f:(int -> 'a -> 'b) -> 'a list -> 'b list
.sp
Same as 
.B List\&.map
, 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

.B List\&.rev_map f l
gives the same result as
.B List\&.rev
.B  (
.B List\&.map
.B  f l)
, but is tail\-recursive and
more efficient\&.

.sp

.I val filter_map 
: 
.B f:('a -> 'b option) -> 'a list -> 'b list
.sp

.B filter_map f l
applies 
.B f
to every element of 
.B l
, filters
out the 
.B None
elements and returns the list of the arguments of
the 
.B Some
elements\&.

.sp
.B "Since"
4.08.0

.sp

.I val fold_left 
: 
.B f:('a -> 'b -> 'a) -> init:'a -> 'b list -> 'a
.sp

.B List\&.fold_left f a [b1; \&.\&.\&.; bn]
is
.B f (\&.\&.\&. (f (f a b1) b2) \&.\&.\&.) bn
\&.

.sp

.I val fold_right 
: 
.B f:('a -> 'b -> 'b) -> 'a list -> init:'b -> 'b
.sp

.B List\&.fold_right f [a1; \&.\&.\&.; an] b
is
.B f a1 (f a2 (\&.\&.\&. (f an b) \&.\&.\&.))
\&.  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

.B List\&.iter2 f [a1; \&.\&.\&.; an] [b1; \&.\&.\&.; bn]
calls in turn
.B f a1 b1; \&.\&.\&.; f an bn
\&.
Raise 
.B 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

.B List\&.map2 f [a1; \&.\&.\&.; an] [b1; \&.\&.\&.; bn]
is
.B [f a1 b1; \&.\&.\&.; f an bn]
\&.
Raise 
.B 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

.B List\&.rev_map2 f l1 l2
gives the same result as
.B List\&.rev
.B  (
.B List\&.map2
.B  f l1 l2)
, 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

.B List\&.fold_left2 f a [b1; \&.\&.\&.; bn] [c1; \&.\&.\&.; cn]
is
.B f (\&.\&.\&. (f (f a b1 c1) b2 c2) \&.\&.\&.) bn cn
\&.
Raise 
.B 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

.B List\&.fold_right2 f [a1; \&.\&.\&.; an] [b1; \&.\&.\&.; bn] c
is
.B f a1 b1 (f a2 b2 (\&.\&.\&. (f an bn c) \&.\&.\&.))
\&.
Raise 
.B 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

.B for_all p [a1; \&.\&.\&.; an]
checks if all elements of the list
satisfy the predicate 
.B p
\&. That is, it returns
.B (p a1) && (p a2) && \&.\&.\&. && (p an)
\&.

.sp

.I val exists 
: 
.B f:('a -> bool) -> 'a list -> bool
.sp

.B exists p [a1; \&.\&.\&.; an]
checks if at least one element of
the list satisfies the predicate 
.B p
\&. That is, it returns
.B (p a1) || (p a2) || \&.\&.\&. || (p an)
\&.

.sp

.I val for_all2 
: 
.B f:('a -> 'b -> bool) -> 'a list -> 'b list -> bool
.sp
Same as 
.B List\&.for_all
, but for a two\-argument predicate\&.
Raise 
.B 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 
.B List\&.exists
, but for a two\-argument predicate\&.
Raise 
.B Invalid_argument
if the two lists are determined
to have different lengths\&.

.sp

.I val mem 
: 
.B 'a -> set:'a list -> bool
.sp

.B mem a l
is true if and only if 
.B a
is equal
to an element of 
.B l
\&.

.sp

.I val memq 
: 
.B 'a -> set:'a list -> bool
.sp
Same as 
.B List\&.mem
, 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

.B find p l
returns the first element of the list 
.B l
that satisfies the predicate 
.B p
\&.
Raise 
.B Not_found
if there is no value that satisfies 
.B p
in the
list 
.B l
\&.

.sp

.I val find_opt 
: 
.B f:('a -> bool) -> 'a list -> 'a option
.sp

.B find p l
returns the first element of the list 
.B l
that satisfies the predicate 
.B p
\&.
Returns 
.B None
if there is no value that satisfies 
.B p
in the
list 
.B l
\&.

.sp
.B "Since"
4.05

.sp

.I val filter 
: 
.B f:('a -> bool) -> 'a list -> 'a list
.sp

.B filter p l
returns all the elements of the list 
.B l
that satisfy the predicate 
.B p
\&.  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

.B find_all
is another name for 
.B List\&.filter
\&.

.sp

.I val partition 
: 
.B f:('a -> bool) -> 'a list -> 'a list * 'a list
.sp

.B partition p l
returns a pair of lists 
.B (l1, l2)
, where
.B l1
is the list of all the elements of 
.B l
that
satisfy the predicate 
.B p
, and 
.B l2
is the list of all the
elements of 
.B l
that do not satisfy 
.B p
\&.
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

.B assoc a l
returns the value associated with key 
.B a
in the list of
pairs 
.B l
\&. That is,
.B assoc a [ \&.\&.\&.; (a,b); \&.\&.\&.] = b
if 
.B (a,b)
is the leftmost binding of 
.B a
in list 
.B l
\&.
Raise 
.B Not_found
if there is no value associated with 
.B a
in the
list 
.B l
\&.

.sp

.I val assoc_opt 
: 
.B 'a -> ('a * 'b) list -> 'b option
.sp

.B assoc_opt a l
returns the value associated with key 
.B a
in the list of
pairs 
.B l
\&. That is,
.B assoc a [ \&.\&.\&.; (a,b); \&.\&.\&.] = b
if 
.B (a,b)
is the leftmost binding of 
.B a
in list 
.B l
\&.
Returns 
.B None
if there is no value associated with 
.B a
in the
list 
.B l
\&.

.sp
.B "Since"
4.05

.sp

.I val assq 
: 
.B 'a -> ('a * 'b) list -> 'b
.sp
Same as 
.B List\&.assoc
, 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 
.B List\&.assoc_opt
, 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 
.B List\&.assoc
, 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 
.B List\&.mem_assoc
, 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

.B remove_assoc a l
returns the list of
pairs 
.B l
without the first pair with key 
.B a
, if any\&.
Not tail\-recursive\&.

.sp

.I val remove_assq 
: 
.B 'a -> ('a * 'b) list -> ('a * 'b) list
.sp
Same as 
.B List\&.remove_assoc
, 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:
.B split [(a1,b1); \&.\&.\&.; (an,bn)]
is 
.B ([a1; \&.\&.\&.; an], [b1; \&.\&.\&.; bn])
\&.
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:
.B combine [a1; \&.\&.\&.; an] [b1; \&.\&.\&.; bn]
is
.B [(a1,b1); \&.\&.\&.; (an,bn)]
\&.
Raise 
.B 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,
.B compare
is a suitable comparison function\&.
The resulting list is sorted in increasing order\&.
.B List\&.sort
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 
.B List\&.sort
, 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 
.B List\&.sort
or 
.B List\&.stable_sort
, whichever is
faster on typical input\&.

.sp

.I val sort_uniq 
: 
.B cmp:('a -> 'a -> int) -> 'a list -> 'a list
.sp
Same as 
.B List\&.sort
, 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 
.B l1
and 
.B l2
are sorted according to the
comparison function 
.B cmp
, 
.B merge cmp l1 l2
will return a
sorted list containing all the elements of 
.B l1
and 
.B l2
\&.
If several elements compare equal, the elements of 
.B l1
will be
before the elements of 
.B l2
\&.
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
