1334 lines
17 KiB
HTML
1334 lines
17 KiB
HTML
|
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
|
|
<HTML><HEAD><TITLE>Man page of List</TITLE>
|
|
</HEAD><BODY>
|
|
<H1>List</H1>
|
|
Section: OCaml library (3o)<BR>Updated: 2020-01-30<BR><A HREF="#index">Index</A>
|
|
<A HREF="/cgi-bin/man/man2html">Return to Main Contents</A><HR>
|
|
|
|
<A NAME="lbAB"> </A>
|
|
<H2>NAME</H2>
|
|
|
|
List - List operations.
|
|
<A NAME="lbAC"> </A>
|
|
<H2>Module</H2>
|
|
|
|
Module List
|
|
<A NAME="lbAD"> </A>
|
|
<H2>Documentation</H2>
|
|
|
|
<P>
|
|
Module
|
|
<B>List</B>
|
|
|
|
<BR> :
|
|
<B>sig end</B>
|
|
|
|
<P>
|
|
<P>
|
|
List operations.
|
|
<P>
|
|
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.
|
|
<P>
|
|
The above considerations can usually be ignored if your lists are not
|
|
longer than about 10000 elements.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>type </I>
|
|
|
|
<B>'a</B>
|
|
|
|
<I>t </I>
|
|
|
|
=
|
|
<B>'a list</B>
|
|
|
|
=
|
|
<BR> | []
|
|
<BR> | ::
|
|
<B>of </B>
|
|
|
|
<B>'a * 'a list</B>
|
|
|
|
<BR>
|
|
<P>
|
|
An alias for the type of lists.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val length </I>
|
|
|
|
:
|
|
<B>'a list -> int</B>
|
|
|
|
<P>
|
|
Return the length (number of elements) of the given list.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val compare_lengths </I>
|
|
|
|
:
|
|
<B>'a list -> 'b list -> int</B>
|
|
|
|
<P>
|
|
Compare the lengths of two lists.
|
|
<B>compare_lengths l1 l2</B>
|
|
|
|
is
|
|
equivalent to
|
|
<B>compare (length l1) (length l2)</B>
|
|
|
|
, except that
|
|
the computation stops after itering on the shortest list.
|
|
<P>
|
|
<P>
|
|
<B>Since</B>
|
|
|
|
4.05.0
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val compare_length_with </I>
|
|
|
|
:
|
|
<B>'a list -> int -> int</B>
|
|
|
|
<P>
|
|
Compare the length of a list to an integer.
|
|
<B>compare_length_with l n</B>
|
|
|
|
is
|
|
equivalent to
|
|
<B>compare (length l) n</B>
|
|
|
|
, except that
|
|
the computation stops after at most
|
|
<B>n</B>
|
|
|
|
iterations on the list.
|
|
<P>
|
|
<P>
|
|
<B>Since</B>
|
|
|
|
4.05.0
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val cons </I>
|
|
|
|
:
|
|
<B>'a -> 'a list -> 'a list</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>cons x xs</B>
|
|
|
|
is
|
|
<B>x :: xs</B>
|
|
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<B>Since</B>
|
|
|
|
4.03.0
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val hd </I>
|
|
|
|
:
|
|
<B>'a list -> 'a</B>
|
|
|
|
<P>
|
|
Return the first element of the given list. Raise
|
|
<B>Failure hd</B>
|
|
|
|
if the list is empty.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val tl </I>
|
|
|
|
:
|
|
<B>'a list -> 'a list</B>
|
|
|
|
<P>
|
|
Return the given list without its first element. Raise
|
|
<B>Failure tl</B>
|
|
|
|
if the list is empty.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val nth </I>
|
|
|
|
:
|
|
<B>'a list -> int -> 'a</B>
|
|
|
|
<P>
|
|
Return the
|
|
<B>n</B>
|
|
|
|
-th element of the given list.
|
|
The first element (head of the list) is at position 0.
|
|
Raise
|
|
<B>Failure nth</B>
|
|
|
|
if the list is too short.
|
|
Raise
|
|
<B>Invalid_argument List.nth</B>
|
|
|
|
if
|
|
<B>n</B>
|
|
|
|
is negative.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val nth_opt </I>
|
|
|
|
:
|
|
<B>'a list -> int -> 'a option</B>
|
|
|
|
<P>
|
|
Return the
|
|
<B>n</B>
|
|
|
|
-th element of the given list.
|
|
The first element (head of the list) is at position 0.
|
|
Return
|
|
<B>None</B>
|
|
|
|
if the list is too short.
|
|
Raise
|
|
<B>Invalid_argument List.nth</B>
|
|
|
|
if
|
|
<B>n</B>
|
|
|
|
is negative.
|
|
<P>
|
|
<P>
|
|
<B>Since</B>
|
|
|
|
4.05
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val rev </I>
|
|
|
|
:
|
|
<B>'a list -> 'a list</B>
|
|
|
|
<P>
|
|
List reversal.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val init </I>
|
|
|
|
:
|
|
<B>int -> (int -> 'a) -> 'a list</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>List.init len f</B>
|
|
|
|
is
|
|
<B>[f 0; f 1; ...; f (len-1)]</B>
|
|
|
|
, evaluated left to right.
|
|
<P>
|
|
<P>
|
|
<B>Since</B>
|
|
|
|
4.06.0
|
|
<P>
|
|
<P>
|
|
<B>Raises Invalid_argument</B>
|
|
|
|
if len < 0.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val append </I>
|
|
|
|
:
|
|
<B>'a list -> 'a list -> 'a list</B>
|
|
|
|
<P>
|
|
Concatenate two lists. Same as the infix operator
|
|
<B>@</B>
|
|
|
|
.
|
|
Not tail-recursive (length of the first argument).
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val rev_append </I>
|
|
|
|
:
|
|
<B>'a list -> 'a list -> 'a list</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>List.rev_append l1 l2</B>
|
|
|
|
reverses
|
|
<B>l1</B>
|
|
|
|
and concatenates it to
|
|
<B>l2</B>
|
|
|
|
.
|
|
This is equivalent to
|
|
<B>List.rev</B>
|
|
|
|
<B>l1 @ l2</B>
|
|
|
|
, but
|
|
<B>rev_append</B>
|
|
|
|
is
|
|
tail-recursive and more efficient.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val concat </I>
|
|
|
|
:
|
|
<B>'a list list -> 'a list</B>
|
|
|
|
<P>
|
|
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).
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val flatten </I>
|
|
|
|
:
|
|
<B>'a list list -> 'a list</B>
|
|
|
|
<P>
|
|
An alias for
|
|
<B>concat</B>
|
|
|
|
.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<P>
|
|
|
|
<A NAME="lbAE"> </A>
|
|
<H3>Iterators</H3>
|
|
|
|
<P>
|
|
<P>
|
|
|
|
<P>
|
|
<I>val iter </I>
|
|
|
|
:
|
|
<B>('a -> unit) -> 'a list -> unit</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>List.iter f [a1; ...; an]</B>
|
|
|
|
applies function
|
|
<B>f</B>
|
|
|
|
in turn to
|
|
<B>a1; ...; an</B>
|
|
|
|
. It is equivalent to
|
|
<B>begin f a1; f a2; ...; f an; () end</B>
|
|
|
|
.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val iteri </I>
|
|
|
|
:
|
|
<B>(int -> 'a -> unit) -> 'a list -> unit</B>
|
|
|
|
<P>
|
|
Same as
|
|
<B>List.iter</B>
|
|
|
|
, but the function is applied to the index of
|
|
the element as first argument (counting from 0), and the element
|
|
itself as second argument.
|
|
<P>
|
|
<P>
|
|
<B>Since</B>
|
|
|
|
4.00.0
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val map </I>
|
|
|
|
:
|
|
<B>('a -> 'b) -> 'a list -> 'b list</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>List.map f [a1; ...; an]</B>
|
|
|
|
applies function
|
|
<B>f</B>
|
|
|
|
to
|
|
<B>a1, ..., an</B>
|
|
|
|
,
|
|
and builds the list
|
|
<B>[f a1; ...; f an]</B>
|
|
|
|
with the results returned by
|
|
<B>f</B>
|
|
|
|
. Not tail-recursive.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val mapi </I>
|
|
|
|
:
|
|
<B>(int -> 'a -> 'b) -> 'a list -> 'b list</B>
|
|
|
|
<P>
|
|
Same as
|
|
<B>List.map</B>
|
|
|
|
, but the function is applied to the index of
|
|
the element as first argument (counting from 0), and the element
|
|
itself as second argument. Not tail-recursive.
|
|
<P>
|
|
<P>
|
|
<B>Since</B>
|
|
|
|
4.00.0
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val rev_map </I>
|
|
|
|
:
|
|
<B>('a -> 'b) -> 'a list -> 'b list</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>List.rev_map f l</B>
|
|
|
|
gives the same result as
|
|
<B>List.rev</B>
|
|
|
|
<B>(</B>
|
|
|
|
<B>List.map</B>
|
|
|
|
<B>f l)</B>
|
|
|
|
, but is tail-recursive and
|
|
more efficient.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val filter_map </I>
|
|
|
|
:
|
|
<B>('a -> 'b option) -> 'a list -> 'b list</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>filter_map f l</B>
|
|
|
|
applies
|
|
<B>f</B>
|
|
|
|
to every element of
|
|
<B>l</B>
|
|
|
|
, filters
|
|
out the
|
|
<B>None</B>
|
|
|
|
elements and returns the list of the arguments of
|
|
the
|
|
<B>Some</B>
|
|
|
|
elements.
|
|
<P>
|
|
<P>
|
|
<B>Since</B>
|
|
|
|
4.08.0
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val fold_left </I>
|
|
|
|
:
|
|
<B>('a -> 'b -> 'a) -> 'a -> 'b list -> 'a</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>List.fold_left f a [b1; ...; bn]</B>
|
|
|
|
is
|
|
<B>f (... (f (f a b1) b2) ...) bn</B>
|
|
|
|
.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val fold_right </I>
|
|
|
|
:
|
|
<B>('a -> 'b -> 'b) -> 'a list -> 'b -> 'b</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>List.fold_right f [a1; ...; an] b</B>
|
|
|
|
is
|
|
<B>f a1 (f a2 (... (f an b) ...))</B>
|
|
|
|
. Not tail-recursive.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<P>
|
|
|
|
<A NAME="lbAF"> </A>
|
|
<H3>Iterators on two lists</H3>
|
|
|
|
<P>
|
|
<P>
|
|
|
|
<P>
|
|
<I>val iter2 </I>
|
|
|
|
:
|
|
<B>('a -> 'b -> unit) -> 'a list -> 'b list -> unit</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>List.iter2 f [a1; ...; an] [b1; ...; bn]</B>
|
|
|
|
calls in turn
|
|
<B>f a1 b1; ...; f an bn</B>
|
|
|
|
.
|
|
Raise
|
|
<B>Invalid_argument</B>
|
|
|
|
if the two lists are determined
|
|
to have different lengths.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val map2 </I>
|
|
|
|
:
|
|
<B>('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>List.map2 f [a1; ...; an] [b1; ...; bn]</B>
|
|
|
|
is
|
|
<B>[f a1 b1; ...; f an bn]</B>
|
|
|
|
.
|
|
Raise
|
|
<B>Invalid_argument</B>
|
|
|
|
if the two lists are determined
|
|
to have different lengths. Not tail-recursive.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val rev_map2 </I>
|
|
|
|
:
|
|
<B>('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>List.rev_map2 f l1 l2</B>
|
|
|
|
gives the same result as
|
|
<B>List.rev</B>
|
|
|
|
<B>(</B>
|
|
|
|
<B>List.map2</B>
|
|
|
|
<B>f l1 l2)</B>
|
|
|
|
, but is tail-recursive and
|
|
more efficient.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val fold_left2 </I>
|
|
|
|
:
|
|
<B>('a -> 'b -> 'c -> 'a) -> 'a -> 'b list -> 'c list -> 'a</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>List.fold_left2 f a [b1; ...; bn] [c1; ...; cn]</B>
|
|
|
|
is
|
|
<B>f (... (f (f a b1 c1) b2 c2) ...) bn cn</B>
|
|
|
|
.
|
|
Raise
|
|
<B>Invalid_argument</B>
|
|
|
|
if the two lists are determined
|
|
to have different lengths.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val fold_right2 </I>
|
|
|
|
:
|
|
<B>('a -> 'b -> 'c -> 'c) -> 'a list -> 'b list -> 'c -> 'c</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>List.fold_right2 f [a1; ...; an] [b1; ...; bn] c</B>
|
|
|
|
is
|
|
<B>f a1 b1 (f a2 b2 (... (f an bn c) ...))</B>
|
|
|
|
.
|
|
Raise
|
|
<B>Invalid_argument</B>
|
|
|
|
if the two lists are determined
|
|
to have different lengths. Not tail-recursive.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<P>
|
|
|
|
<A NAME="lbAG"> </A>
|
|
<H3>List scanning</H3>
|
|
|
|
<P>
|
|
<P>
|
|
|
|
<P>
|
|
<I>val for_all </I>
|
|
|
|
:
|
|
<B>('a -> bool) -> 'a list -> bool</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>for_all p [a1; ...; an]</B>
|
|
|
|
checks if all elements of the list
|
|
satisfy the predicate
|
|
<B>p</B>
|
|
|
|
. That is, it returns
|
|
<B>(p a1) && (p a2) && ... && (p an)</B>
|
|
|
|
.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val exists </I>
|
|
|
|
:
|
|
<B>('a -> bool) -> 'a list -> bool</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>exists p [a1; ...; an]</B>
|
|
|
|
checks if at least one element of
|
|
the list satisfies the predicate
|
|
<B>p</B>
|
|
|
|
. That is, it returns
|
|
<B>(p a1) || (p a2) || ... || (p an)</B>
|
|
|
|
.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val for_all2 </I>
|
|
|
|
:
|
|
<B>('a -> 'b -> bool) -> 'a list -> 'b list -> bool</B>
|
|
|
|
<P>
|
|
Same as
|
|
<B>List.for_all</B>
|
|
|
|
, but for a two-argument predicate.
|
|
Raise
|
|
<B>Invalid_argument</B>
|
|
|
|
if the two lists are determined
|
|
to have different lengths.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val exists2 </I>
|
|
|
|
:
|
|
<B>('a -> 'b -> bool) -> 'a list -> 'b list -> bool</B>
|
|
|
|
<P>
|
|
Same as
|
|
<B>List.exists</B>
|
|
|
|
, but for a two-argument predicate.
|
|
Raise
|
|
<B>Invalid_argument</B>
|
|
|
|
if the two lists are determined
|
|
to have different lengths.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val mem </I>
|
|
|
|
:
|
|
<B>'a -> 'a list -> bool</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>mem a l</B>
|
|
|
|
is true if and only if
|
|
<B>a</B>
|
|
|
|
is equal
|
|
to an element of
|
|
<B>l</B>
|
|
|
|
.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val memq </I>
|
|
|
|
:
|
|
<B>'a -> 'a list -> bool</B>
|
|
|
|
<P>
|
|
Same as
|
|
<B>List.mem</B>
|
|
|
|
, but uses physical equality instead of structural
|
|
equality to compare list elements.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<P>
|
|
|
|
<A NAME="lbAH"> </A>
|
|
<H3>List searching</H3>
|
|
|
|
<P>
|
|
<P>
|
|
|
|
<P>
|
|
<I>val find </I>
|
|
|
|
:
|
|
<B>('a -> bool) -> 'a list -> 'a</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>find p l</B>
|
|
|
|
returns the first element of the list
|
|
<B>l</B>
|
|
|
|
that satisfies the predicate
|
|
<B>p</B>
|
|
|
|
.
|
|
Raise
|
|
<B>Not_found</B>
|
|
|
|
if there is no value that satisfies
|
|
<B>p</B>
|
|
|
|
in the
|
|
list
|
|
<B>l</B>
|
|
|
|
.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val find_opt </I>
|
|
|
|
:
|
|
<B>('a -> bool) -> 'a list -> 'a option</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>find_opt p l</B>
|
|
|
|
returns the first element of the list
|
|
<B>l</B>
|
|
|
|
that
|
|
satisfies the predicate
|
|
<B>p</B>
|
|
|
|
, or
|
|
<B>None</B>
|
|
|
|
if there is no value that
|
|
satisfies
|
|
<B>p</B>
|
|
|
|
in the list
|
|
<B>l</B>
|
|
|
|
.
|
|
<P>
|
|
<P>
|
|
<B>Since</B>
|
|
|
|
4.05
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val filter </I>
|
|
|
|
:
|
|
<B>('a -> bool) -> 'a list -> 'a list</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>filter p l</B>
|
|
|
|
returns all the elements of the list
|
|
<B>l</B>
|
|
|
|
that satisfy the predicate
|
|
<B>p</B>
|
|
|
|
. The order of the elements
|
|
in the input list is preserved.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val find_all </I>
|
|
|
|
:
|
|
<B>('a -> bool) -> 'a list -> 'a list</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>find_all</B>
|
|
|
|
is another name for
|
|
<B>List.filter</B>
|
|
|
|
.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val partition </I>
|
|
|
|
:
|
|
<B>('a -> bool) -> 'a list -> 'a list * 'a list</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>partition p l</B>
|
|
|
|
returns a pair of lists
|
|
<B>(l1, l2)</B>
|
|
|
|
, where
|
|
<B>l1</B>
|
|
|
|
is the list of all the elements of
|
|
<B>l</B>
|
|
|
|
that
|
|
satisfy the predicate
|
|
<B>p</B>
|
|
|
|
, and
|
|
<B>l2</B>
|
|
|
|
is the list of all the
|
|
elements of
|
|
<B>l</B>
|
|
|
|
that do not satisfy
|
|
<B>p</B>
|
|
|
|
.
|
|
The order of the elements in the input list is preserved.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<P>
|
|
|
|
<A NAME="lbAI"> </A>
|
|
<H3>Association lists</H3>
|
|
|
|
<P>
|
|
<P>
|
|
|
|
<P>
|
|
<I>val assoc </I>
|
|
|
|
:
|
|
<B>'a -> ('a * 'b) list -> 'b</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>assoc a l</B>
|
|
|
|
returns the value associated with key
|
|
<B>a</B>
|
|
|
|
in the list of
|
|
pairs
|
|
<B>l</B>
|
|
|
|
. That is,
|
|
<B>assoc a [ ...; (a,b); ...] = b</B>
|
|
|
|
if
|
|
<B>(a,b)</B>
|
|
|
|
is the leftmost binding of
|
|
<B>a</B>
|
|
|
|
in list
|
|
<B>l</B>
|
|
|
|
.
|
|
Raise
|
|
<B>Not_found</B>
|
|
|
|
if there is no value associated with
|
|
<B>a</B>
|
|
|
|
in the
|
|
list
|
|
<B>l</B>
|
|
|
|
.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val assoc_opt </I>
|
|
|
|
:
|
|
<B>'a -> ('a * 'b) list -> 'b option</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>assoc_opt a l</B>
|
|
|
|
returns the value associated with key
|
|
<B>a</B>
|
|
|
|
in the list of
|
|
pairs
|
|
<B>l</B>
|
|
|
|
. That is,
|
|
<B>assoc_opt a [ ...; (a,b); ...] = b</B>
|
|
|
|
if
|
|
<B>(a,b)</B>
|
|
|
|
is the leftmost binding of
|
|
<B>a</B>
|
|
|
|
in list
|
|
<B>l</B>
|
|
|
|
.
|
|
Returns
|
|
<B>None</B>
|
|
|
|
if there is no value associated with
|
|
<B>a</B>
|
|
|
|
in the
|
|
list
|
|
<B>l</B>
|
|
|
|
.
|
|
<P>
|
|
<P>
|
|
<B>Since</B>
|
|
|
|
4.05
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val assq </I>
|
|
|
|
:
|
|
<B>'a -> ('a * 'b) list -> 'b</B>
|
|
|
|
<P>
|
|
Same as
|
|
<B>List.assoc</B>
|
|
|
|
, but uses physical equality instead of structural
|
|
equality to compare keys.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val assq_opt </I>
|
|
|
|
:
|
|
<B>'a -> ('a * 'b) list -> 'b option</B>
|
|
|
|
<P>
|
|
Same as
|
|
<B>List.assoc_opt</B>
|
|
|
|
, but uses physical equality instead of structural
|
|
equality to compare keys.
|
|
<P>
|
|
<P>
|
|
<B>Since</B>
|
|
|
|
4.05
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val mem_assoc </I>
|
|
|
|
:
|
|
<B>'a -> ('a * 'b) list -> bool</B>
|
|
|
|
<P>
|
|
Same as
|
|
<B>List.assoc</B>
|
|
|
|
, but simply return true if a binding exists,
|
|
and false if no bindings exist for the given key.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val mem_assq </I>
|
|
|
|
:
|
|
<B>'a -> ('a * 'b) list -> bool</B>
|
|
|
|
<P>
|
|
Same as
|
|
<B>List.mem_assoc</B>
|
|
|
|
, but uses physical equality instead of
|
|
structural equality to compare keys.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val remove_assoc </I>
|
|
|
|
:
|
|
<B>'a -> ('a * 'b) list -> ('a * 'b) list</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>remove_assoc a l</B>
|
|
|
|
returns the list of
|
|
pairs
|
|
<B>l</B>
|
|
|
|
without the first pair with key
|
|
<B>a</B>
|
|
|
|
, if any.
|
|
Not tail-recursive.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val remove_assq </I>
|
|
|
|
:
|
|
<B>'a -> ('a * 'b) list -> ('a * 'b) list</B>
|
|
|
|
<P>
|
|
Same as
|
|
<B>List.remove_assoc</B>
|
|
|
|
, but uses physical equality instead
|
|
of structural equality to compare keys. Not tail-recursive.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<P>
|
|
|
|
<A NAME="lbAJ"> </A>
|
|
<H3>Lists of pairs</H3>
|
|
|
|
<P>
|
|
<P>
|
|
|
|
<P>
|
|
<I>val split </I>
|
|
|
|
:
|
|
<B>('a * 'b) list -> 'a list * 'b list</B>
|
|
|
|
<P>
|
|
Transform a list of pairs into a pair of lists:
|
|
<B>split [(a1,b1); ...; (an,bn)]</B>
|
|
|
|
is
|
|
<B>([a1; ...; an], [b1; ...; bn])</B>
|
|
|
|
.
|
|
Not tail-recursive.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val combine </I>
|
|
|
|
:
|
|
<B>'a list -> 'b list -> ('a * 'b) list</B>
|
|
|
|
<P>
|
|
Transform a pair of lists into a list of pairs:
|
|
<B>combine [a1; ...; an] [b1; ...; bn]</B>
|
|
|
|
is
|
|
<B>[(a1,b1); ...; (an,bn)]</B>
|
|
|
|
.
|
|
Raise
|
|
<B>Invalid_argument</B>
|
|
|
|
if the two lists
|
|
have different lengths. Not tail-recursive.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<P>
|
|
|
|
<A NAME="lbAK"> </A>
|
|
<H3>Sorting</H3>
|
|
|
|
<P>
|
|
<P>
|
|
|
|
<P>
|
|
<I>val sort </I>
|
|
|
|
:
|
|
<B>('a -> 'a -> int) -> 'a list -> 'a list</B>
|
|
|
|
<P>
|
|
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</B>
|
|
|
|
is a suitable comparison function.
|
|
The resulting list is sorted in increasing order.
|
|
<B>List.sort</B>
|
|
|
|
is guaranteed to run in constant heap space
|
|
(in addition to the size of the result list) and logarithmic
|
|
stack space.
|
|
<P>
|
|
The current implementation uses Merge Sort. It runs in constant
|
|
heap space and logarithmic stack space.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val stable_sort </I>
|
|
|
|
:
|
|
<B>('a -> 'a -> int) -> 'a list -> 'a list</B>
|
|
|
|
<P>
|
|
Same as
|
|
<B>List.sort</B>
|
|
|
|
, but the sorting algorithm is guaranteed to
|
|
be stable (i.e. elements that compare equal are kept in their
|
|
original order) .
|
|
<P>
|
|
The current implementation uses Merge Sort. It runs in constant
|
|
heap space and logarithmic stack space.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val fast_sort </I>
|
|
|
|
:
|
|
<B>('a -> 'a -> int) -> 'a list -> 'a list</B>
|
|
|
|
<P>
|
|
Same as
|
|
<B>List.sort</B>
|
|
|
|
or
|
|
<B>List.stable_sort</B>
|
|
|
|
, whichever is faster
|
|
on typical input.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val sort_uniq </I>
|
|
|
|
:
|
|
<B>('a -> 'a -> int) -> 'a list -> 'a list</B>
|
|
|
|
<P>
|
|
Same as
|
|
<B>List.sort</B>
|
|
|
|
, but also remove duplicates.
|
|
<P>
|
|
<P>
|
|
<B>Since</B>
|
|
|
|
4.02.0
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val merge </I>
|
|
|
|
:
|
|
<B>('a -> 'a -> int) -> 'a list -> 'a list -> 'a list</B>
|
|
|
|
<P>
|
|
Merge two lists:
|
|
Assuming that
|
|
<B>l1</B>
|
|
|
|
and
|
|
<B>l2</B>
|
|
|
|
are sorted according to the
|
|
comparison function
|
|
<B>cmp</B>
|
|
|
|
,
|
|
<B>merge cmp l1 l2</B>
|
|
|
|
will return a
|
|
sorted list containing all the elements of
|
|
<B>l1</B>
|
|
|
|
and
|
|
<B>l2</B>
|
|
|
|
.
|
|
If several elements compare equal, the elements of
|
|
<B>l1</B>
|
|
|
|
will be
|
|
before the elements of
|
|
<B>l2</B>
|
|
|
|
.
|
|
Not tail-recursive (sum of the lengths of the arguments).
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<P>
|
|
|
|
<A NAME="lbAL"> </A>
|
|
<H3>Iterators</H3>
|
|
|
|
<P>
|
|
<P>
|
|
|
|
<P>
|
|
<I>val to_seq </I>
|
|
|
|
:
|
|
<B>'a list -> 'a Seq.t</B>
|
|
|
|
<P>
|
|
Iterate on the list
|
|
<P>
|
|
<P>
|
|
<B>Since</B>
|
|
|
|
4.07
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val of_seq </I>
|
|
|
|
:
|
|
<B>'a Seq.t -> 'a list</B>
|
|
|
|
<P>
|
|
Create a list from the iterator
|
|
<P>
|
|
<P>
|
|
<B>Since</B>
|
|
|
|
4.07
|
|
<P>
|
|
<P>
|
|
<P>
|
|
|
|
<HR>
|
|
<A NAME="index"> </A><H2>Index</H2>
|
|
<DL>
|
|
<DT id="1"><A HREF="#lbAB">NAME</A><DD>
|
|
<DT id="2"><A HREF="#lbAC">Module</A><DD>
|
|
<DT id="3"><A HREF="#lbAD">Documentation</A><DD>
|
|
<DL>
|
|
<DT id="4"><A HREF="#lbAE">Iterators</A><DD>
|
|
<DT id="5"><A HREF="#lbAF">Iterators on two lists</A><DD>
|
|
<DT id="6"><A HREF="#lbAG">List scanning</A><DD>
|
|
<DT id="7"><A HREF="#lbAH">List searching</A><DD>
|
|
<DT id="8"><A HREF="#lbAI">Association lists</A><DD>
|
|
<DT id="9"><A HREF="#lbAJ">Lists of pairs</A><DD>
|
|
<DT id="10"><A HREF="#lbAK">Sorting</A><DD>
|
|
<DT id="11"><A HREF="#lbAL">Iterators</A><DD>
|
|
</DL>
|
|
</DL>
|
|
<HR>
|
|
This document was created by
|
|
<A HREF="/cgi-bin/man/man2html">man2html</A>,
|
|
using the manual pages.<BR>
|
|
Time: 00:05:47 GMT, March 31, 2021
|
|
</BODY>
|
|
</HTML>
|