List
A replacement for Stdlib.List which:
- replaces the exception-raising functions by exception-safe variants,
- provides Lwt-, result- and Lwt-result-aware traversors.
List is intended to shadow both Stdlib.List and Lwt_list.
Basics
Checkout Lwtreslib for an introduction to the naming and semantic convention of Lwtreslib. In a nutshell:
- Stdlib functions that raise exceptions are replaced by safe variants (typically returning
option). - The
_e suffix is for result-aware traversors ("e" stands for "error"), _s and _p are for Lwt-aware, and _es and _ep are for Lwt-result-aware. _e, _s, and _es traversors are fail-early: they stop traversal as soon as a failure (Error or Fail) occurs; _p and _ep traversors are best-effort: they only resolve once all of the intermediate promises have, even if a failure occurs.
Double-traversal and combine
Note that double-list traversors (iter2, map2, etc., and also combine) take an additional when_different_lengths parameter. This is to control the error that is returned when the two lists passed as arguments have different lengths.
This mechanism is a replacement for Stdlib.List.iter2 (etc.) raising Invalid_argument.
Note that, as per the fail-early behaviour mentioned above, _e, _s, and _es traversors will have already processed the common-prefix before the error is returned.
Because the best-effort behaviour of _p and _ep is unsatisfying for this failure case, double parallel traversors are omitted from this library. (Specifically, it is not obvious whether nor how the when_different_lengths error should be composed with the other errors.)
To obtain a different behaviour for sequential traversors, or to process two lists in parallel, you can use combine or any of the alternatives that handles the error differently: combine_drop, combine_with_leftovers. Finally, the rev_combine is provided to allow to avoid multiple-reversing.
Special considerations
Because they traverse the list from right-to-left, the fold_right2 function and all its variants fail with when_different_lengths before any of the processing starts. Whilst this is still within the fail-early behaviour, it may be surprising enough that it requires mentioning here.
Because they may return early, for_all2 and exists2 and all their variants may return Ok _ even though the arguments have different lengths.
Trivial values
type 'a t = 'a list = | []| :: of 'a * 'a list
in-monad, preallocated nil
val nil_s : 'a list Lwt.tnil_es 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 optionhd xs is the head (first element) of the list or None if the list is empty.
val tl : 'a list -> 'a list optiontl 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 optionnth xs n is the nth element of the list or None if the list has fewer than n elements.
nth xs 0 = hd xs
val nth_opt : 'a list -> int -> 'a optionnth_opt is an alias for nth provided for backwards compatibility.
val last : 'a -> 'a list -> 'alast 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 optionlast_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 optionfind 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 find_opt : ('a -> bool) -> 'a list -> 'a optionfind_opt is an alias for find provided for backwards compatibility.
val mem : equal:('a -> 'a -> bool) -> 'a -> 'a list -> boolmem ~equal a l is true iff there is an element e of l such that equal a e.
val assoc : equal:('a -> 'a -> bool) -> 'a -> ('a * 'b) list -> 'b optionassoc ~equal k kvs is Some v such that (k', v) is the first pair in the list such that equal k' k or None if the list contains no such pair.
val assoc_opt : equal:('a -> 'a -> bool) -> 'a -> ('a * 'b) list -> 'b optionassoc_opt is an alias for assoc provided for backwards compatibility.
val assq : 'a -> ('a * 'b) list -> 'b optionassq k kvs is the same as assoc ~equal:Stdlib.( == ) k kvs: it uses the physical equality.
val assq_opt : 'a -> ('a * 'b) list -> 'b optionassq_opt is an alias for assq provided for backwards compatibility.
val mem_assoc : equal:('a -> 'a -> bool) -> 'a -> ('a * 'b) list -> boolmem_assoc ~equal k l is equivalent to Option.is_some @@ assoc ~equal k l.
val mem_assq : 'a -> ('a * 'b) list -> boolmem_assq k l is mem_assoc ~equal:Stdlib.( == ) k l.
val remove_assoc :
equal:('a -> 'a -> bool) ->
'a ->
('a * 'b) list ->
('a * 'b) listremove_assoc ~equal k l is l without the first element (k', _) such that equal k k'.
val remove_assq : 'a -> ('a * 'b) list -> ('a * 'b) listremove_assoq k l is remove_assoc ~equal:Stdlib.( == ) k l.
Initialisation
val init :
when_negative_length:'trace ->
int ->
(int -> 'a) ->
('a list, 'trace) Pervasives.resultinit ~when_negative_length n f is Error when_negative_length if n is strictly negative and Ok (Stdlib.List.init n f) otherwise.
Basic traversal
val length : 'a list -> intval rev : 'a list -> 'a listval concat : 'a list list -> 'a listval append : 'a list -> 'a list -> 'a listval rev_append : 'a list -> 'a list -> 'a listval flatten : 'a list list -> 'a listDouble-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) Pervasives.resultcombine ~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) Pervasives.resultrev_combine ~when_different_lengths xs ys is rev (combine ~when_different_lengths xs ys) but more efficient.
val split : ('a * 'b) list -> 'a list * 'b listval iter2 :
when_different_lengths:'trace ->
('a -> 'b -> unit) ->
'a list ->
'b list ->
(unit, 'trace) Pervasives.resultval map2 :
when_different_lengths:'trace ->
('a -> 'b -> 'c) ->
'a list ->
'b list ->
('c list, 'trace) Pervasives.resultval rev_map2 :
when_different_lengths:'trace ->
('a -> 'b -> 'c) ->
'a list ->
'b list ->
('c list, 'trace) Pervasives.resultval fold_left2 :
when_different_lengths:'trace ->
('a -> 'b -> 'c -> 'a) ->
'a ->
'b list ->
'c list ->
('a, 'trace) Pervasives.resultval fold_right2 :
when_different_lengths:'trace ->
('a -> 'b -> 'c -> 'c) ->
'a list ->
'b list ->
'c ->
('c, 'trace) Pervasives.resultThis function is not tail-recursive
val fold_left_map : ('a -> 'b -> 'a * 'c) -> 'a -> 'b list -> 'a * 'c listfold_left_map f a xs is a combination of fold_left and map that maps over all elements of xs and threads an accumulator with initial value a through calls to f.
val for_all2 :
when_different_lengths:'trace ->
('a -> 'b -> bool) ->
'a list ->
'b list ->
(bool, 'trace) Pervasives.resultval exists2 :
when_different_lengths:'trace ->
('a -> 'b -> bool) ->
'a list ->
'b list ->
(bool, 'trace) Pervasives.resultMonad-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.
Query variants
val find_s : ('a -> bool Lwt.t) -> 'a list -> 'a option Lwt.tval filter : ('a -> bool) -> 'a list -> 'a listval rev_filter : ('a -> bool) -> 'a list -> 'a listrev_filter f l is rev (filter f l) but more efficient.
val rev_filter_some : 'a option list -> 'a listval filter_some : 'a option list -> 'a listval rev_filter_s : ('a -> bool Lwt.t) -> 'a list -> 'a list Lwt.tval filter_s : ('a -> bool Lwt.t) -> 'a list -> 'a list Lwt.tval filter_p : ('a -> bool Lwt.t) -> 'a list -> 'a list Lwt.tval rev_partition : ('a -> bool) -> 'a list -> 'a list * 'a listval partition : ('a -> bool) -> 'a list -> 'a list * 'a listval rev_partition_s :
('a -> bool Lwt.t) ->
'a list ->
('a list * 'a list) Lwt.tval partition_s : ('a -> bool Lwt.t) -> 'a list -> ('a list * 'a list) Lwt.tval partition_p : ('a -> bool Lwt.t) -> 'a list -> ('a list * 'a list) Lwt.tval iter : ('a -> unit) -> 'a list -> unitval iter_s : ('a -> unit Lwt.t) -> 'a list -> unit Lwt.tval iter_p : ('a -> unit Lwt.t) -> 'a list -> unit Lwt.tval iteri : (int -> 'a -> unit) -> 'a list -> unitval iteri_s : (int -> 'a -> unit Lwt.t) -> 'a list -> unit Lwt.tval iteri_p : (int -> 'a -> unit Lwt.t) -> 'a list -> unit Lwt.tval map : ('a -> 'b) -> 'a list -> 'b listval map_s : ('a -> 'b Lwt.t) -> 'a list -> 'b list Lwt.tval map_p : ('a -> 'b Lwt.t) -> 'a list -> 'b list Lwt.tval mapi : (int -> 'a -> 'b) -> 'a list -> 'b listval mapi_s : (int -> 'a -> 'b Lwt.t) -> 'a list -> 'b list Lwt.tval mapi_p : (int -> 'a -> 'b Lwt.t) -> 'a list -> 'b list Lwt.tval rev_map : ('a -> 'b) -> 'a list -> 'b listval rev_mapi : (int -> 'a -> 'b) -> 'a list -> 'b listval rev_map_s : ('a -> 'b Lwt.t) -> 'a list -> 'b list Lwt.tval rev_map_p : ('a -> 'b Lwt.t) -> 'a list -> 'b list Lwt.tval rev_mapi_s : (int -> 'a -> 'b Lwt.t) -> 'a list -> 'b list Lwt.tval rev_mapi_p : (int -> 'a -> 'b Lwt.t) -> 'a list -> 'b list Lwt.tval rev_filter_map : ('a -> 'b option) -> 'a list -> 'b listval rev_filter_map_s : ('a -> 'b option Lwt.t) -> 'a list -> 'b list Lwt.tval filter_map : ('a -> 'b option) -> 'a list -> 'b listval filter_map_s : ('a -> 'b option Lwt.t) -> 'a list -> 'b list Lwt.tval filter_map_p : ('a -> 'b option Lwt.t) -> 'a list -> 'b list Lwt.tval concat_map : ('a -> 'b list) -> 'a list -> 'b listval concat_map_s : ('a -> 'b list Lwt.t) -> 'a list -> 'b list Lwt.tval concat_map_p : ('a -> 'b list Lwt.t) -> 'a list -> 'b list Lwt.tval fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'aval fold_left_s : ('a -> 'b -> 'a Lwt.t) -> 'a -> 'b list -> 'a Lwt.tfold_left_map_e f a xs is a combination of fold_left_e and map_e that maps over all elements of xs and threads an accumulator with initial value a through calls to f. The list is traversed from left to right and the first encountered error is returned.
val fold_left_map_s :
('a -> 'b -> ('a * 'c) Lwt.t) ->
'a ->
'b list ->
('a * 'c list) Lwt.tfold_left_map_s f a xs is a combination of fold_left_s and map_s that maps over all elements of xs and threads an accumulator with initial value a through calls to f.
fold_left_map_es f a xs is a combination of fold_left_es and map_es that maps over all elements of xs and threads an accumulator with initial value a through calls to f. The list is traversed from left to right and the first encountered error is returned.
val fold_left_i : (int -> 'a -> 'b -> 'a) -> 'a -> 'b list -> 'aval fold_left_i_s : (int -> 'a -> 'b -> 'a Lwt.t) -> 'a -> 'b list -> 'a Lwt.tval fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'bThis function is not tail-recursive
This function is not tail-recursive
val fold_right_s : ('a -> 'b -> 'b Lwt.t) -> 'a list -> 'b -> 'b Lwt.tThis 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_s :
when_different_lengths:'trace ->
('a -> 'b -> unit Lwt.t) ->
'a list ->
'b list ->
(unit, 'trace) Pervasives.result Lwt.tval map2_s :
when_different_lengths:'trace ->
('a -> 'b -> 'c Lwt.t) ->
'a list ->
'b list ->
('c list, 'trace) Pervasives.result Lwt.tval rev_map2_s :
when_different_lengths:'trace ->
('a -> 'b -> 'c Lwt.t) ->
'a list ->
'b list ->
('c list, 'trace) Pervasives.result Lwt.tval fold_left2_s :
when_different_lengths:'trace ->
('a -> 'b -> 'c -> 'a Lwt.t) ->
'a ->
'b list ->
'c list ->
('a, 'trace) Pervasives.result Lwt.tThis 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) Pervasives.result Lwt.tThis function is not tail-recursive
This function is not tail-recursive
Scanning variants
val for_all : ('a -> bool) -> 'a list -> boolval for_all_s : ('a -> bool Lwt.t) -> 'a list -> bool Lwt.tval for_all_p : ('a -> bool Lwt.t) -> 'a list -> bool Lwt.tval exists : ('a -> bool) -> 'a list -> boolval exists_s : ('a -> bool Lwt.t) -> 'a list -> bool Lwt.tval exists_p : ('a -> bool Lwt.t) -> 'a list -> bool Lwt.tDouble-scanning variants
As mentioned above, there are no _p and _ep double-scanners. Use combine (and variants) to circumvent this.
val for_all2_s :
when_different_lengths:'trace ->
('a -> 'b -> bool Lwt.t) ->
'a list ->
'b list ->
(bool, 'trace) Pervasives.result Lwt.tval exists2_s :
when_different_lengths:'trace ->
('a -> 'b -> bool Lwt.t) ->
'a list ->
'b list ->
(bool, 'trace) Pervasives.result Lwt.tCombine 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) listcombine_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
type ('a, 'b) left_or_right_list = [ | `Left of 'a list| `Right of 'b list
]A type like result but which is symmetric
val combine_with_leftovers :
'a list ->
'b list ->
('a * 'b) list * ('a, 'b) left_or_right_list optioncombine_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.
compare / equal
val compare : ('a -> 'a -> int) -> 'a list -> 'a list -> intval compare_lengths : 'a list -> 'b list -> intval compare_length_with : 'a list -> int -> intval equal : ('a -> 'a -> bool) -> 'a list -> 'a list -> boolSorting
val sort : ('a -> 'a -> int) -> 'a list -> 'a listval stable_sort : ('a -> 'a -> int) -> 'a list -> 'a listval fast_sort : ('a -> 'a -> int) -> 'a list -> 'a listval sort_uniq : ('a -> 'a -> int) -> 'a list -> 'a listconversion
val to_seq : 'a list -> 'a Seq.tval of_seq : 'a Seq.t -> 'a list