Immutable, singly-linked lists, giving fast access to the front of the list, and slow (i.e., O(n)) access to the back of the list. The comparison functions on lists are lexicographic.
include sig ... end
val hash_fold_t : (Base.Hash.state ‑> 'a ‑> Base.Hash.state) ‑> Base.Hash.state ‑> 'a t ‑> Base.Hash.state
val t_of_sexp : (Base.Sexp.t ‑> 'a) ‑> Base.Sexp.t ‑> 'a t
val sexp_of_t : ('a ‑> Base.Sexp.t) ‑> 'a t ‑> Base.Sexp.t
include Base.Container.S1 with type a t := a t
val mem : 'a t ‑> 'a ‑> equal:('a ‑> 'a ‑> bool) ‑> bool
Checks whether the provided element is there, using equal
.
val length : 'a t ‑> int
val is_empty : 'a t ‑> bool
val iter : 'a t ‑> f:('a ‑> unit) ‑> unit
val fold : 'a t ‑> init:'accum ‑> f:('accum ‑> 'a ‑> 'accum) ‑> 'accum
fold t ~init ~f
returns f (... f (f (f init e1) e2) e3 ...) en
, where e1..en
are the elements of t
val fold_result : 'a t ‑> init:'accum ‑> f:('accum ‑> 'a ‑> ('accum, 'e) Base.Result.t) ‑> ('accum, 'e) Base.Result.t
fold_result t ~init ~f
is a short-circuiting version of fold
that runs in the
Result
monad. If f
returns an Error _
, that value is returned without any
additional invocations of f
.
val fold_until : 'a t ‑> init:'accum ‑> f:('accum ‑> 'a ‑> ('accum, 'final) Base__.Container_intf.Continue_or_stop.t) ‑> finish:('accum ‑> 'final) ‑> 'final
fold_until t ~init ~f ~finish
is a short-circuiting version of fold
. If f
returns Stop _
the computation ceases and results in that value. If f
returns
Continue _
, the fold will proceed. If f
never returns Stop _
, the final result
is computed by finish
.
val exists : 'a t ‑> f:('a ‑> bool) ‑> bool
Returns true
if and only if there exists an element for which the provided
function evaluates to true
. This is a short-circuiting operation.
val for_all : 'a t ‑> f:('a ‑> bool) ‑> bool
Returns true
if and only if the provided function evaluates to true
for all
elements. This is a short-circuiting operation.
val count : 'a t ‑> f:('a ‑> bool) ‑> int
Returns the number of elements for which the provided function evaluates to true.
val sum : (module Base.Commutative_group.S with type t = 'sum) ‑> 'a t ‑> f:('a ‑> 'sum) ‑> 'sum
Returns the sum of f i
for all i
in the container.
val find : 'a t ‑> f:('a ‑> bool) ‑> 'a option
Returns as an option
the first element for which f
evaluates to true.
val find_map : 'a t ‑> f:('a ‑> 'b option) ‑> 'b option
Returns the first evaluation of f
that returns Some
, and returns None
if there
is no such element.
val to_list : 'a t ‑> 'a list
val to_array : 'a t ‑> 'a array
val min_elt : 'a t ‑> compare:('a ‑> 'a ‑> int) ‑> 'a option
Returns a minimum (resp maximum) element from the collection using the provided
compare
function, or None
if the collection is empty. In case of a tie, the first
element encountered while traversing the collection is returned. The implementation
uses fold
so it has the same complexity as fold
.
val max_elt : 'a t ‑> compare:('a ‑> 'a ‑> int) ‑> 'a option
include Base.Monad.S with type a t := a t
include Base__.Monad_intf.S_without_syntax with type a t := a t
include Base__.Monad_intf.Infix with type a t := a t
module Monad_infix : Base__.Monad_intf.Infix with type a t := a t
module Or_unequal_lengths : sig ... end
Or_unequal_lengths
is used for functions that take multiple lists and that only make
sense if all the lists have the same length, e.g., iter2
, map3
. Such functions
check the list lengths prior to doing anything else, and return Unequal_lengths
if
not all the lists have the same length.
of_list
is the identity function. It is useful so that the List
module matches
the same signature that other container modules do, namely:
val of_list : 'a List.t -> 'a t
val nth : 'a t ‑> int ‑> 'a option
val nth_exn : 'a t ‑> int ‑> 'a
Return the n
-th element of the given list. The first element (head of the list) is
at position 0. Raise if the list is too short or n
is negative.
List.rev_append l1 l2
reverses l1
and concatenates it to l2
. This is equivalent
to (
List.rev l1) @ l2
, but rev_append
is more efficient.
List.unordered_append l1 l2
has the same elements as l1 @ l2
, but in some
unspecified order. Generally takes time proportional to length of first list, but is
O(1) if either list is empty.
List.rev_map l ~f
gives the same result as List.rev (
ListLabels.map f l)
,
but is more efficient.
val fold_left : 'a t ‑> init:'b ‑> f:('b ‑> 'a ‑> 'b) ‑> 'b
fold_left
is the same as fold
, and one should always use fold
rather than
fold_left
, except in functors that are parameterized over a more general signature
where this equivalence does not hold.
List.iter2 [a1; ...; an] [b1; ...; bn] ~f
calls in turn f a1 b1; ...; f an bn
.
The exn version will raise if the two lists have different lengths.
val iter2 : 'a t ‑> 'b t ‑> f:('a ‑> 'b ‑> unit) ‑> unit Or_unequal_lengths.t
List.rev_map2_exn l1 l2 ~f
gives the same result as List.rev (List.map2_exn l1 l2
~f)
, but is more efficient.
val rev_map2 : 'a t ‑> 'b t ‑> f:('a ‑> 'b ‑> 'c) ‑> 'c t Or_unequal_lengths.t
List.fold2 ~f ~init:a [b1; ...; bn] [c1; ...; cn]
is f (... (f (f a b1 c1) b2 c2)
...) bn cn
. The exn version will raise if the two lists have different lengths.
val fold2 : 'a t ‑> 'b t ‑> init:'c ‑> f:('c ‑> 'a ‑> 'b ‑> 'c) ‑> 'c Or_unequal_lengths.t
val for_alli : 'a t ‑> f:(int ‑> 'a ‑> bool) ‑> bool
Like List.for_all, but passes the index as an argument.
Like List.for_all, but for a two-argument predicate. The exn version will raise if the two lists have different lengths.
val for_all2 : 'a t ‑> 'b t ‑> f:('a ‑> 'b ‑> bool) ‑> bool Or_unequal_lengths.t
val existsi : 'a t ‑> f:(int ‑> 'a ‑> bool) ‑> bool
Like List.exists, but passes the index as an argument.
Like List.exists, but for a two-argument predicate. The exn version will raise if the two lists have different lengths.
val exists2 : 'a t ‑> 'b t ‑> f:('a ‑> 'b ‑> bool) ‑> bool Or_unequal_lengths.t
filter l ~f
returns all the elements of the list l
that satisfy the predicate p
.
The order of the elements in the input list is preserved.
partition_tf l ~f
returns a pair of lists (l1, l2)
, where l1
is the list of all
the elements of l
that satisfy the predicate p
, and l2
is the list of all the
elements of l
that do not satisfy p
. The order of the elements in the input list
is preserved. The "tf" suffix is mnemonic to remind readers at a call that the result
is (trues, falses).
split_n [e1; ...; em] n
is ([e1; ...; en], [en+1; ...; em])
.
n > m
, ([e1; ...; em], [])
is returned.n < 0
, ([], [e1; ...; em])
is returned.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, Pervasives.compare is a suitable
comparison function.
The current implementation uses Merge Sort. It runs in linear heap space and logarithmic stack space.
Presently, the sort is stable, meaning that two equal elements in the input will be in the same order in the output.
Merges two lists: assuming that l1
and l2
are sorted according to the comparison
function compare
, merge compare l1 l2
will return a sorted list containing all the
elements of l1
and l2
. If several elements compare equal, the elements of l1
will be before the elements of l2
.
val hd : 'a t ‑> 'a option
val findi : 'a t ‑> f:(int ‑> 'a ‑> bool) ‑> (int * 'a) option
val find_exn : 'a t ‑> f:('a ‑> bool) ‑> 'a
find_exn t ~f
returns the first element of t
that satisfies f
. It raises
Caml.Not_found
or Not_found_s
if there is no such element.
val find_map_exn : 'a t ‑> f:('a ‑> 'b option) ‑> 'b
Returns the first evaluation of f
that returns Some
. Raises Caml.Not_found
or
Not_found_s
if f
always returns None
.
Like find_map
and find_map_exn
, but passes the index as an argument.
val find_mapi : 'a t ‑> f:(int ‑> 'a ‑> 'b option) ‑> 'b option
val find_mapi_exn : 'a t ‑> f:(int ‑> 'a ‑> 'b option) ‑> 'b
List.map f [a1; ...; an]
applies function f
to a1
, a2
, ..., an
, in order,
and builds the list [f a1; ...; f an]
with the results returned by f
.
folding_map
is a version of map
that threads an accumulator through calls to
f
.
fold_map
is a combination of fold
and map
that threads an accumulator through
calls to f
.
concat_map t ~f
is concat (map t ~f)
, except that there is no guarantee about the
order in which f
is applied to the elements of t
.
List.map2 [a1; ...; an] [b1; ...; bn] ~f
is [f a1 b1; ...; f an bn]
. The exn
version will raise if the two lists have different lengths.
val map2 : 'a t ‑> 'b t ‑> f:('a ‑> 'b ‑> 'c) ‑> 'c t Or_unequal_lengths.t
Analogous to rev_map2
.
val rev_map3 : 'a t ‑> 'b t ‑> 'c t ‑> f:('a ‑> 'b ‑> 'c ‑> 'd) ‑> 'd t Or_unequal_lengths.t
Analogous to map2
.
val map3 : 'a t ‑> 'b t ‑> 'c t ‑> f:('a ‑> 'b ‑> 'c ‑> 'd) ‑> 'd t Or_unequal_lengths.t
rev_map_append l1 l2 ~f
reverses l1
mapping f
over each element, and appends the
result to the front of l2
.
val fold_right : 'a t ‑> f:('a ‑> 'b ‑> 'b) ‑> init:'b ‑> 'b
List.fold_right [a1; ...; an] ~f ~init:b
is f a1 (f a2 (... (f an b) ...))
.
Transform a list of pairs into a pair of lists: unzip [(a1,b1); ...; (an,bn)]
is
([a1; ...; an], [b1; ...; bn])
.
Transform a pair of lists into an (optional) list of pairs: zip [a1; ...; an] [b1;
...; bn]
is [(a1,b1); ...; (an,bn)]
. Returns None
if the two lists have
different lengths.
mapi
is just like map, but it also passes in the index of each element as the first
argument to the mapped function. Tail-recursive.
val iteri : 'a t ‑> f:(int ‑> 'a ‑> unit) ‑> unit
iteri
is just like iter
, but it also passes in the index of each element as the
first argument to the iter'd function. Tail-recursive.
val foldi : 'a t ‑> init:'b ‑> f:(int ‑> 'b ‑> 'a ‑> 'b) ‑> 'b
foldi
is just like fold
, but it also passes in the index of each element as the
first argument to the folded function. Tail-recursive.
val reduce_exn : 'a t ‑> f:('a ‑> 'a ‑> 'a) ‑> 'a
reduce_exn [a1; ...; an] ~f
is f (... (f (f a1 a2) a3) ...) an
. It fails on the
empty list. Tail recursive.
val reduce : 'a t ‑> f:('a ‑> 'a ‑> 'a) ‑> 'a option
val reduce_balanced : 'a t ‑> f:('a ‑> 'a ‑> 'a) ‑> 'a option
reduce_balanced
returns the same value as reduce
when f
is associative, but
differs in that the tree of nested applications of f
has logarithmic depth.
This is useful when your 'a
grows in size as you reduce it and f
becomes more
expensive with bigger inputs. For example, reduce_balanced ~f:(^)
takes n*log(n)
time, while reduce ~f:(^)
takes quadratic time.
val reduce_balanced_exn : 'a t ‑> f:('a ‑> 'a ‑> 'a) ‑> 'a
group l ~break
returns a list of lists (i.e., groups) whose concatenation is equal
to the original list. Each group is broken where break
returns true on a pair of
successive elements.
Example:
group ~break:(<>) ['M';'i';'s';'s';'i';'s';'s';'i';'p';'p';'i'] ->
[['M'];['i'];['s';'s'];['i'];['s';'s'];['i'];['p';'p'];['i']]
This is just like group
, except that you get the index in the original list of the
current element along with the two elements.
Example, group the chars of "Mississippi"
into triples:
groupi ~break:(fun i _ _ -> i mod 3 = 0)
['M';'i';'s';'s';'i';'s';'s';'i';'p';'p';'i'] ->
[['M'; 'i'; 's']; ['s'; 'i'; 's']; ['s'; 'i'; 'p']; ['p'; 'i']]
chunks_of l ~length
returns a list of lists whose concatenation is equal to the
original list. Every list has length
elements, except for possibly the last list,
which may have fewer. chunks_of
raises if length <= 0
.
val last_exn : 'a t ‑> 'a
val find_consecutive_duplicate : 'a t ‑> equal:('a ‑> 'a ‑> bool) ‑> ('a * 'a) option
find_consecutive_duplicate t ~equal
returns the first pair of consecutive elements
(a1, a2)
in t
such that equal a1 a2
. They are returned in the same order as
they appear in t
. equal
need not be an equivalence relation; it is simply used as
a predicate on consecutive elements.
val remove_consecutive_duplicates : ?which_to_keep:[ `First | `Last ] ‑> 'a t ‑> equal:('a ‑> 'a ‑> bool) ‑> 'a t
Returns the given list with consecutive duplicates removed. The relative order of the
other elements is unaffected. The element kept from a run of duplicates is determined
by which_to_keep
.
val find_a_dup : compare:('a ‑> 'a ‑> int) ‑> 'a t ‑> 'a option
find_a_dup
returns a duplicate from the list (with no guarantees about which
duplicate you get), or None
if there are no dups.
val contains_dup : compare:('a ‑> 'a ‑> int) ‑> 'a t ‑> bool
Returns true if there are any two elements in the list which are the same. O(n log n) time complexity.
val find_all_dups : compare:('a ‑> 'a ‑> int) ‑> 'a t ‑> 'a list
find_all_dups
returns a list of all elements that occur more than once, with
no guarantees about order. O(n log n) time complexity.
val count : 'a t ‑> f:('a ‑> bool) ‑> int
count l ~f
is the number of elements in l
that satisfy the predicate f
.
val counti : 'a t ‑> f:(int ‑> 'a ‑> bool) ‑> int
val range : ?stride:int ‑> ?start:[ `inclusive | `exclusive ] ‑> ?stop:[ `inclusive | `exclusive ] ‑> int ‑> int ‑> int t
range ?stride ?start ?stop start_i stop_i
is the list of integers from start_i
to
stop_i
, stepping by stride
. If stride
< 0 then we need start_i
> stop_i
for
the result to be nonempty (or start_i
= stop_i
in the case where both bounds are
inclusive).
val range' : compare:('a ‑> 'a ‑> int) ‑> stride:('a ‑> 'a) ‑> ?start:[ `inclusive | `exclusive ] ‑> ?stop:[ `inclusive | `exclusive ] ‑> 'a ‑> 'a ‑> 'a t
range'
is analogous to range
for general start/stop/stride types. range'
raises
if stride x
returns x
or if the direction that stride x
moves x
changes from
one call to the next.
val init : int ‑> f:(int ‑> 'a) ‑> 'a t
init n ~f
is [(f 0); (f 1); ...; (f (n-1))]
. It is an error if n < 0
.
List.init
applies f
to values in decreasing order; starting with n - 1
, and
ending with 0
. This is the opposite order to Array.init
.
rev_filter_map l ~f
is the reversed sublist of l
containing only elements for
which f
returns Some e
.
rev_filter_mapi is just like rev_filter_map
, but it also passes in the index of each
element as the first argument to the mapped function. Tail-recursive.
filter_mapi is just like filter_map
, but it also passes in the index of each element
as the first argument to the mapped function. Tail-recursive.
filter_opt l
is the sublist of l
containing only elements which are Some e
. In
other words, filter_opt l
= filter_map ~f:ident l
.
module Assoc : sig ... end
Interpret a list of (key, value) pairs as a map in which only the first occurrence of a key affects the semantics, i.e.:
Note that sub
, unlike slice
, doesn't use Python-style indices!
take l n
returns the first n
elements of l
, or all of l
if n > length l
.
take l n = fst (split_n l n)
.
drop l n
returns l
without the first n
elements, or the empty list if n >
length l
. drop l n = snd (split_n l n)
.
Concatenates a list of lists. The elements of the argument are all concatenated together (in the same order) to give the result. Tail recursive over outer and inner lists.
Like concat
, but faster and without preserving any ordering (i.e., for lists that
are essentially viewed as multi-sets).
Returns a list with all possible pairs -- if the input lists have length len1
and
len2
, the resulting list will have length len1 * len2
.
val permute : ?random_state:Base.Random.State.t ‑> 'a t ‑> 'a t
permute ?random_state t
returns a permutation of t
.
permute
side-effects random_state
by repeated calls to Random.State.int
. If
random_state
is not supplied, permute
uses Random.State.default
.
val random_element : ?random_state:Base.Random.State.t ‑> 'a t ‑> 'a option
random_element ?random_state t
is None
if t
is empty, else it is Some x
for
some x
chosen uniformly at random from t
.
random_element
side-effects random_state
by calling Random.State.int
. If
random_state
is not supplied, random_element
uses Random.State.default
.
val random_element_exn : ?random_state:Base.Random.State.t ‑> 'a t ‑> 'a
val is_sorted : 'a t ‑> compare:('a ‑> 'a ‑> int) ‑> bool
is_sorted t ~compare
returns true
iff for all adjacent a1; a2
in t
, compare
a1 a2 <= 0
.
is_sorted_strictly
is similar, except it uses <
instead of <=
.
val is_sorted_strictly : 'a t ‑> compare:('a ‑> 'a ‑> int) ‑> bool
module Infix : sig ... end
transpose m
transposes the rows and columns of the matrix m
,
considered as either a row of column lists or (dually) a column of row lists.
Example:
transpose [[1;2;3];[4;5;6]] = [[1;4];[2;5];[3;6]]
On non-empty rectangular matrices, transpose
is an involution (i.e., transpose
(transpose m) = m
). Transpose returns None
when called on lists of lists with
non-uniform lengths.