include Bare_sigs.List.S
Boilerplate
Include the legacy list. Functions that raise exceptions are shadowed below.
include module type of List with type 'a t = 'a List.t
type 'a t = 'a List.t =
| []
| :: of 'a * 'a list
An alias for the type of lists.
val length : 'a list -> int
Return the length (number of elements) of the given list.
val compare_lengths : 'a list -> 'b list -> int
Compare the lengths of two lists. compare_lengths l1 l2
is equivalent to compare (length l1) (length l2)
, except that the computation stops after itering on the shortest list.
val compare_length_with : 'a list -> int -> int
Compare the length of a list to an integer. compare_length_with l n
is equivalent to compare (length l) n
, except that the computation stops after at most n
iterations on the list.
val cons : 'a -> 'a list -> 'a list
val nth_opt : 'a list -> int -> 'a option
Return the n
-th element of the given list. The first element (head of the list) is at position 0. Return None
if the list is too short. Raise Invalid_argument "List.nth"
if n
is negative.
val rev : 'a list -> 'a list
val append : 'a list -> 'a list -> 'a list
Concatenate two lists. Same as the infix operator @
. Not tail-recursive (length of the first argument).
val rev_append : 'a list -> 'a list -> 'a list
List.rev_append l1 l2
reverses l1
and concatenates it to l2
. This is equivalent to List.rev
l1 @ l2
, but rev_append
is tail-recursive and more efficient.
val concat : 'a list list -> 'a list
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).
val flatten : 'a list list -> 'a list
Iterators
val iter : ('a -> unit) -> 'a list -> unit
List.iter f [a1; ...; an]
applies function f
in turn to a1; ...; an
. It is equivalent to begin f a1; f a2; ...; f an; () end
.
val iteri : (int -> 'a -> unit) -> 'a list -> unit
Same as 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.
val map : ('a -> 'b) -> 'a list -> 'b list
List.map f [a1; ...; an]
applies function f
to a1, ..., an
, and builds the list [f a1; ...; f an]
with the results returned by f
. Not tail-recursive.
val mapi : (int -> 'a -> 'b) -> 'a list -> 'b list
Same as 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. Not tail-recursive.
val rev_map : ('a -> 'b) -> 'a list -> 'b list
List.rev_map f l
gives the same result as List.rev
(
List.map
f l)
, but is tail-recursive and more efficient.
val filter_map : ('a -> 'b option) -> 'a list -> 'b list
filter_map f l
applies f
to every element of l
, filters out the None
elements and returns the list of the arguments of the Some
elements.
val concat_map : ('a -> 'b list) -> 'a list -> 'b list
List.concat_map f l
gives the same result as List.concat
(
List.map
f l)
. Tail-recursive.
val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
List.fold_left f a [b1; ...; bn]
is f (... (f (f a b1) b2) ...) bn
.
val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b
List.fold_right f [a1; ...; an] b
is f a1 (f a2 (... (f an b) ...))
. Not tail-recursive.
Iterators on two lists
List scanning
val for_all : ('a -> bool) -> 'a list -> bool
for_all p [a1; ...; an]
checks if all elements of the list satisfy the predicate p
. That is, it returns (p a1) && (p a2) && ... && (p an)
.
val exists : ('a -> bool) -> 'a list -> bool
exists p [a1; ...; an]
checks if at least one element of the list satisfies the predicate p
. That is, it returns (p a1) || (p a2) || ... || (p an)
.
val mem : 'a -> 'a list -> bool
mem a l
is true if and only if a
is equal to an element of l
.
val memq : 'a -> 'a list -> bool
Same as List.mem
, but uses physical equality instead of structural equality to compare list elements.
List searching
val find_opt : ('a -> bool) -> 'a list -> 'a option
find_opt p l
returns the first element of the list l
that satisfies the predicate p
, or None
if there is no value that satisfies p
in the list l
.
val find_map : ('a -> 'b option) -> 'a list -> 'b option
find_map f l
applies f
to the elements of l
in order, and returns the first result of the form Some v
, or None
if none exist.
val filter : ('a -> bool) -> 'a list -> 'a list
filter p l
returns all the elements of the list l
that satisfy the predicate p
. The order of the elements in the input list is preserved.
val find_all : ('a -> bool) -> 'a list -> 'a list
find_all
is another name for List.filter
.
val partition : ('a -> bool) -> 'a list -> 'a list * 'a list
partition p l
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.
Association lists
val assoc_opt : 'a -> ('a * 'b) list -> 'b option
assoc_opt a l
returns the value associated with key a
in the list of pairs l
. That is, assoc_opt a [ ...; (a,b); ...] = b
if (a,b)
is the leftmost binding of a
in list l
. Returns None
if there is no value associated with a
in the list l
.
val assq_opt : 'a -> ('a * 'b) list -> 'b option
Same as List.assoc_opt
, but uses physical equality instead of structural equality to compare keys.
val mem_assoc : 'a -> ('a * 'b) list -> bool
Same as List.assoc
, but simply return true if a binding exists, and false if no bindings exist for the given key.
val mem_assq : 'a -> ('a * 'b) list -> bool
Same as List.mem_assoc
, but uses physical equality instead of structural equality to compare keys.
val remove_assoc : 'a -> ('a * 'b) list -> ('a * 'b) list
remove_assoc a l
returns the list of pairs l
without the first pair with key a
, if any. Not tail-recursive.
val remove_assq : 'a -> ('a * 'b) list -> ('a * 'b) list
Same as List.remove_assoc
, but uses physical equality instead of structural equality to compare keys. Not tail-recursive.
Lists of pairs
val split : ('a * 'b) list -> 'a list * 'b list
Transform a list of pairs into a pair of lists: split [(a1,b1); ...; (an,bn)]
is ([a1; ...; an], [b1; ...; bn])
. Not tail-recursive.
Sorting
val sort : ('a -> 'a -> int) -> 'a list -> 'a list
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, Stdlib.compare
is a suitable comparison function. The resulting list is sorted in increasing order. List.sort
is guaranteed to run in constant heap space (in addition to the size of the result list) and logarithmic stack space.
The current implementation uses Merge Sort. It runs in constant heap space and logarithmic stack space.
val stable_sort : ('a -> 'a -> int) -> 'a list -> 'a list
Same as List.sort
, but the sorting algorithm is guaranteed to be stable (i.e. elements that compare equal are kept in their original order) .
The current implementation uses Merge Sort. It runs in constant heap space and logarithmic stack space.
val fast_sort : ('a -> 'a -> int) -> 'a list -> 'a list
Same as List.sort
or List.stable_sort
, whichever is faster on typical input.
val sort_uniq : ('a -> 'a -> int) -> 'a list -> 'a list
Same as List.sort
, but also remove duplicates.
val merge : ('a -> 'a -> int) -> 'a list -> 'a list -> 'a list
Merge two lists: Assuming that l1
and l2
are sorted according to the comparison function cmp
, merge cmp 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
. Not tail-recursive (sum of the lengths of the arguments).
Iterators
val to_seq : 'a list -> 'a Seq.t
val of_seq : 'a Seq.t -> 'a list
Create a list from the iterator
Trivial values
in-monad, preallocated nil
val nil_e : ('a list, 'trace) result
val nil_s : 'a list Lwt.t
nil
is Lwt.return (Ok [])
Safe wrappers
Shadowing unsafe functions to avoid all exceptions.
Safe lookups, scans, retrievals
Return option rather than raise Not_found
, Failure _
, or Invalid_argument _
val hd : 'a list -> 'a option
hd xs
is the head (first element) of the list or None
if the list is empty.
val tl : 'a list -> 'a list option
tl xs
is the tail of the list (the whole list except the first element) or None
if the list is empty.
val nth : 'a list -> int -> 'a option
nth xs n
is the n
th element of the list or None
if the list has fewer than n
elements.
nth xs 0 = tl xs
val last : 'a -> 'a list -> 'a
last x xs
is the last element of the list xs
or x
if xs
is empty.
The primary intended use for last
is after destructing a list: match l with | None -> … | Some x :: xs -> last x xs
but it can also be used for a default value: last default_value_if_empty xs
.
val last_opt : 'a list -> 'a option
last_opt xs
is the last element of the list xs
or None
if the list xs
is empty.
val find : ('a -> bool) -> 'a list -> 'a option
find predicate xs
is the first element x
of the list xs
such that predicate x
is true
or None
if the list xs
has no such element.
val assoc : 'a -> ('a * 'b) list -> 'b option
assoc k kvs
is v
such that (k', v)
is the first pair in the list such that k' = k
(uses the polymorphic equality) or None
if the list contains no such pair.
val assq : 'a -> ('a * 'b) list -> 'b option
assq k kvs
is the same as assoc k kvs
but it uses the physical equality.
Initialisation
val init :
when_negative_length:'trace ->
int ->
(int -> 'a) ->
('a list, 'trace) result
init ~when_negative_length n f
is Error when_negative_length
if n
is strictly negative and Ok (Stdlib.List.init n f)
otherwise.
Double-list traversals
These safe-wrappers take an explicit value to handle the case of lists of unequal length.
val combine :
when_different_lengths:'trace ->
'a list ->
'b list ->
(('a * 'b) list, 'trace) result
combine ~when_different_lengths l1 l2
is either
Error when_different_lengths
if List.length l1 <> List.length l2
- a list of pairs of elements from
l1
and l2
E.g., combine ~when_different_lengths [] [] = Ok []
E.g., combine ~when_different_lengths [1; 2] ['a'; 'b'] = Ok [(1,'a'); (2, 'b')]
E.g., combine ~when_different_lengths:() [1] [] = Error ()
Note: combine ~when_different_lengths l1 l2
is equivalent to try Ok (Stdlib.List.combine l1 l2)
with Invalid_argument _ -> when_different_lengths
The same equivalence almost holds for the other double traversors below. The notable difference is if the functions passed as argument to the traversors raise the Invalid_argument _
exception.
val rev_combine :
when_different_lengths:'trace ->
'a list ->
'b list ->
(('a * 'b) list, 'trace) result
rev_combine ~when_different_lengths xs ys
is rev (combine ~when_different_lengths xs ys)
but more efficient.
val iter2 :
when_different_lengths:'trace ->
('a -> 'b -> unit) ->
'a list ->
'b list ->
(unit, 'trace) result
val map2 :
when_different_lengths:'trace ->
('a -> 'b -> 'c) ->
'a list ->
'b list ->
('c list, 'trace) result
val rev_map2 :
when_different_lengths:'trace ->
('a -> 'b -> 'c) ->
'a list ->
'b list ->
('c list, 'trace) result
val fold_left2 :
when_different_lengths:'trace ->
('a -> 'b -> 'c -> 'a) ->
'a ->
'b list ->
'c list ->
('a, 'trace) result
val fold_right2 :
when_different_lengths:'trace ->
('a -> 'b -> 'c -> 'c) ->
'a list ->
'b list ->
'c ->
('c, 'trace) result
This function is not tail-recursive
val for_all2 :
when_different_lengths:'trace ->
('a -> 'b -> bool) ->
'a list ->
'b list ->
(bool, 'trace) result
val exists2 :
when_different_lengths:'trace ->
('a -> 'b -> bool) ->
'a list ->
'b list ->
(bool, 'trace) result
Monad-aware variants
The functions below are strict extensions of the standard Stdlib.List
module. It is for result-, lwt- and lwt-result-aware variants. The meaning of the suffix is as described above, in Lwtreslib
, and in Sigs.Seq
.
Initialisation variants
Note that for asynchronous variants (_s
, _es
, _p
, and _ep
), if the length parameter is negative, then the promise is returned already fulfilled with Error when_different_lengths
.
val init_e :
when_negative_length:'trace ->
int ->
(int -> ('a, 'trace) result) ->
('a list, 'trace) result
val init_s :
when_negative_length:'trace ->
int ->
(int -> 'a Lwt.t) ->
('a list, 'trace) result Lwt.t
val init_es :
when_negative_length:'trace ->
int ->
(int -> ('a, 'trace) result Lwt.t) ->
('a list, 'trace) result Lwt.t
val init_p :
when_negative_length:'trace ->
int ->
(int -> 'a Lwt.t) ->
('a list, 'trace) result Lwt.t
Query variants
val find_e :
('a -> (bool, 'trace) result) ->
'a list ->
('a option, 'trace) result
val find_s : ('a -> bool Lwt.t) -> 'a list -> 'a option Lwt.t
val rev_filter : ('a -> bool) -> 'a list -> 'a list
rev_filter f l
is rev (filter f l)
but more efficient.
val rev_filter_some : 'a option list -> 'a list
val filter_some : 'a option list -> 'a list
val rev_filter_ok : ('a, 'b) result list -> 'a list
val filter_ok : ('a, 'b) result list -> 'a list
val rev_filter_error : ('a, 'b) result list -> 'b list
val filter_error : ('a, 'b) result list -> 'b list
val rev_filter_e :
('a -> (bool, 'trace) result) ->
'a list ->
('a list, 'trace) result
val filter_e :
('a -> (bool, 'trace) result) ->
'a list ->
('a list, 'trace) result
val rev_filter_s : ('a -> bool Lwt.t) -> 'a list -> 'a list Lwt.t
val filter_s : ('a -> bool Lwt.t) -> 'a list -> 'a list Lwt.t
val filter_p : ('a -> bool Lwt.t) -> 'a list -> 'a list Lwt.t
val rev_partition_result : ('a, 'b) result list -> 'a list * 'b list
val partition_result : ('a, 'b) result list -> 'a list * 'b list
val rev_partition_e :
('a -> (bool, 'trace) result) ->
'a list ->
('a list * 'a list, 'trace) result
val partition_e :
('a -> (bool, 'trace) result) ->
'a list ->
('a list * 'a list, 'trace) result
val rev_partition_s :
('a -> bool Lwt.t) ->
'a list ->
('a list * 'a list) Lwt.t
val partition_s : ('a -> bool Lwt.t) -> 'a list -> ('a list * 'a list) Lwt.t
val rev_partition_es :
('a -> (bool, 'trace) result Lwt.t) ->
'a list ->
('a list * 'a list, 'trace) result Lwt.t
val partition_p : ('a -> bool Lwt.t) -> 'a list -> ('a list * 'a list) Lwt.t
Traversal variants
val iter_e : ('a -> (unit, 'trace) result) -> 'a list -> (unit, 'trace) result
val iter_s : ('a -> unit Lwt.t) -> 'a list -> unit Lwt.t
val iter_p : ('a -> unit Lwt.t) -> 'a list -> unit Lwt.t
val iteri_e :
(int -> 'a -> (unit, 'trace) result) ->
'a list ->
(unit, 'trace) result
val iteri_s : (int -> 'a -> unit Lwt.t) -> 'a list -> unit Lwt.t
val iteri_p : (int -> 'a -> unit Lwt.t) -> 'a list -> unit Lwt.t
val map_e : ('a -> ('b, 'trace) result) -> 'a list -> ('b list, 'trace) result
val map_s : ('a -> 'b Lwt.t) -> 'a list -> 'b list Lwt.t
val map_p : ('a -> 'b Lwt.t) -> 'a list -> 'b list Lwt.t
val mapi_e :
(int -> 'a -> ('b, 'trace) result) ->
'a list ->
('b list, 'trace) result
val mapi_s : (int -> 'a -> 'b Lwt.t) -> 'a list -> 'b list Lwt.t
val mapi_p : (int -> 'a -> 'b Lwt.t) -> 'a list -> 'b list Lwt.t
val rev_mapi : (int -> 'a -> 'b) -> 'a list -> 'b list
val rev_map_e :
('a -> ('b, 'trace) result) ->
'a list ->
('b list, 'trace) result
val rev_map_s : ('a -> 'b Lwt.t) -> 'a list -> 'b list Lwt.t
val rev_map_p : ('a -> 'b Lwt.t) -> 'a list -> 'b list Lwt.t
val rev_mapi_e :
(int -> 'a -> ('b, 'trace) result) ->
'a list ->
('b list, 'trace) result
val rev_mapi_s : (int -> 'a -> 'b Lwt.t) -> 'a list -> 'b list Lwt.t
val rev_mapi_p : (int -> 'a -> 'b Lwt.t) -> 'a list -> 'b list Lwt.t
val rev_filter_map : ('a -> 'b option) -> 'a list -> 'b list
val rev_filter_map_e :
('a -> ('b option, 'trace) result) ->
'a list ->
('b list, 'trace) result
val filter_map_e :
('a -> ('b option, 'trace) result) ->
'a list ->
('b list, 'trace) result
val rev_filter_map_s : ('a -> 'b option Lwt.t) -> 'a list -> 'b list Lwt.t
val filter_map_s : ('a -> 'b option Lwt.t) -> 'a list -> 'b list Lwt.t
val filter_map_p : ('a -> 'b option Lwt.t) -> 'a list -> 'b list Lwt.t
val fold_left_e :
('a -> 'b -> ('a, 'trace) result) ->
'a ->
'b list ->
('a, 'trace) result
val fold_left_s : ('a -> 'b -> 'a Lwt.t) -> 'a -> 'b list -> 'a Lwt.t
val fold_right_e :
('a -> 'b -> ('b, 'trace) result) ->
'a list ->
'b ->
('b, 'trace) result
This function is not tail-recursive
val fold_right_s : ('a -> 'b -> 'b Lwt.t) -> 'a list -> 'b -> 'b Lwt.t
This function is not tail-recursive
This function is not tail-recursive
Double-traversal variants
As mentioned above, there are no _p
and _ep
double-traversors. Use combine
(and variants) to circumvent this.
val iter2_e :
when_different_lengths:'trace ->
('a -> 'b -> (unit, 'trace) result) ->
'a list ->
'b list ->
(unit, 'trace) result
val iter2_s :
when_different_lengths:'trace ->
('a -> 'b -> unit Lwt.t) ->
'a list ->
'b list ->
(unit, 'trace) result Lwt.t
val iter2_es :
when_different_lengths:'trace ->
('a -> 'b -> (unit, 'trace) result Lwt.t) ->
'a list ->
'b list ->
(unit, 'trace) result Lwt.t
val map2_e :
when_different_lengths:'trace ->
('a -> 'b -> ('c, 'trace) result) ->
'a list ->
'b list ->
('c list, 'trace) result
val map2_s :
when_different_lengths:'trace ->
('a -> 'b -> 'c Lwt.t) ->
'a list ->
'b list ->
('c list, 'trace) result Lwt.t
val map2_es :
when_different_lengths:'trace ->
('a -> 'b -> ('c, 'trace) result Lwt.t) ->
'a list ->
'b list ->
('c list, 'trace) result Lwt.t
val rev_map2_e :
when_different_lengths:'trace ->
('a -> 'b -> ('c, 'trace) result) ->
'a list ->
'b list ->
('c list, 'trace) result
val rev_map2_s :
when_different_lengths:'trace ->
('a -> 'b -> 'c Lwt.t) ->
'a list ->
'b list ->
('c list, 'trace) result Lwt.t
val rev_map2_es :
when_different_lengths:'trace ->
('a -> 'b -> ('c, 'trace) result Lwt.t) ->
'a list ->
'b list ->
('c list, 'trace) result Lwt.t
val fold_left2_e :
when_different_lengths:'trace ->
('a -> 'b -> 'c -> ('a, 'trace) result) ->
'a ->
'b list ->
'c list ->
('a, 'trace) result
val fold_left2_s :
when_different_lengths:'trace ->
('a -> 'b -> 'c -> 'a Lwt.t) ->
'a ->
'b list ->
'c list ->
('a, 'trace) result Lwt.t
val fold_left2_es :
when_different_lengths:'trace ->
('a -> 'b -> 'c -> ('a, 'trace) result Lwt.t) ->
'a ->
'b list ->
'c list ->
('a, 'trace) result Lwt.t
val fold_right2_e :
when_different_lengths:'trace ->
('a -> 'b -> 'c -> ('c, 'trace) result) ->
'a list ->
'b list ->
'c ->
('c, 'trace) result
This function is not tail-recursive
val fold_right2_s :
when_different_lengths:'trace ->
('a -> 'b -> 'c -> 'c Lwt.t) ->
'a list ->
'b list ->
'c ->
('c, 'trace) result Lwt.t
This function is not tail-recursive
val fold_right2_es :
when_different_lengths:'trace ->
('a -> 'b -> 'c -> ('c, 'trace) result Lwt.t) ->
'a list ->
'b list ->
'c ->
('c, 'trace) result Lwt.t
This function is not tail-recursive
Scanning variants
val for_all_e :
('a -> (bool, 'trace) result) ->
'a list ->
(bool, 'trace) result
val for_all_s : ('a -> bool Lwt.t) -> 'a list -> bool Lwt.t
val for_all_p : ('a -> bool Lwt.t) -> 'a list -> bool Lwt.t
val exists_e :
('a -> (bool, 'trace) result) ->
'a list ->
(bool, 'trace) result
val exists_s : ('a -> bool Lwt.t) -> 'a list -> bool Lwt.t
val exists_p : ('a -> bool Lwt.t) -> 'a list -> bool Lwt.t
Double-scanning variants
As mentioned above, there are no _p
and _ep
double-scanners. Use combine
(and variants) to circumvent this.
val for_all2_e :
when_different_lengths:'trace ->
('a -> 'b -> (bool, 'trace) result) ->
'a list ->
'b list ->
(bool, 'trace) result
val for_all2_s :
when_different_lengths:'trace ->
('a -> 'b -> bool Lwt.t) ->
'a list ->
'b list ->
(bool, 'trace) result Lwt.t
val for_all2_es :
when_different_lengths:'trace ->
('a -> 'b -> (bool, 'trace) result Lwt.t) ->
'a list ->
'b list ->
(bool, 'trace) result Lwt.t
val exists2_e :
when_different_lengths:'trace ->
('a -> 'b -> (bool, 'trace) result) ->
'a list ->
'b list ->
(bool, 'trace) result
val exists2_s :
when_different_lengths:'trace ->
('a -> 'b -> bool Lwt.t) ->
'a list ->
'b list ->
(bool, 'trace) result Lwt.t
val exists2_es :
when_different_lengths:'trace ->
('a -> 'b -> (bool, 'trace) result Lwt.t) ->
'a list ->
'b list ->
(bool, 'trace) result Lwt.t
Combine variants
These are primarily intended to be used for preprocessing before applying a traversor to the resulting list of pairs. They give alternatives to the when_different_lengths
mechanism of the immediate double-traversors above.
In case the semantic of, say, map2_es
was unsatisfying, one can use map_es
on a combine
-preprocessed pair of lists. The different variants of combine
give different approaches to different-length handling.
val combine_drop : 'a list -> 'b list -> ('a * 'b) list
combine_drop ll lr
is a list l
of pairs of elements taken from the common-length prefix of ll
and lr
. The suffix of whichever list is longer (if any) is dropped.
More formally nth l n
is:
None
if n >= min (length ll) (length lr)
Some (Option.get @@ nth ll n, Option.get @@ nth lr n)
otherwise
val combine_with_leftovers :
'a list ->
'b list ->
('a * 'b) list * [ `Left of 'a list | `Right of 'b list ] option
combine_with_leftovers ll lr
is a tuple (combined, leftover)
where combined
is combine_drop ll lr
and leftover
is either `Left lsuffix
or `Right rsuffix
depending on which of ll
or lr
is longer. leftover
is None
if the two lists have the same length.