Concatenates a nested container. The elements of the inner containers are concatenated together in order to give the result.
Sourceval filter : 'a list->f:('a-> bool)->'a list
filter t ~f returns all the elements of t that satisfy the predicate f.
Sourceval filter_map : 'a list->f:('a->'b option)->'b list
filter_map t ~f applies f to every x in t. The result contains every y for which f x returns Some y.
Sourceval concat_map : 'a list->f:('a->'b list)->'b list
concat_map t ~f is equivalent to concat (map t ~f).
Sourceval partition_tf : 'a list->f:('a-> bool)->'a list * 'a list
partition_tf t ~f returns a pair t1, t2, where t1 is all elements of t that satisfy f, and t2 is all elements of t that do not satisfy f. The "tf" suffix is mnemonic to remind readers that the result is (trues, falses).
Sourceval partition_map :
'a list->f:('a->('b, 'c)Base__.Either0.t)->'b list * 'c list
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.
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.
Example:
type maybe_negative =
| Found_negative of int
| All_nonnegative of { sum : int }
(** [first_neg_or_sum list] returns the first negative number in [list], if any,
otherwise returns the sum of the list. *)
let first_neg_or_sum =
List.fold_until ~init:0
~f:(fun sum x ->
if x < 0
then Stop (Found_negative x)
else Continue (sum + x))
~finish:(fun sum -> All_nonnegative { sum })
;;
let x = first_neg_or_sum [1; 2; 3; 4; 5]
val x : maybe_negative = All_nonnegative {sum = 15}
let y = first_neg_or_sum [1; 2; -3; 4; 5]
val y : maybe_negative = Found_negative -3
Sourceval min_elt : 'a list->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.
Sourceval max_elt : 'a list->compare:('a->'a-> int)->'a option
These are all like their equivalents in Container except that an index starting at 0 is added as the first argument to f.
Sourceval foldi : 'a list->init:_->f:(int ->_->'a->_)->_
Sourceval iteri : 'a list->f:(int ->'a-> unit)-> unit
Sourceval existsi : 'a list->f:(int ->'a-> bool)-> bool
Sourceval for_alli : 'a list->f:(int ->'a-> bool)-> bool
Sourceval counti : 'a list->f:(int ->'a-> bool)-> int
Sourceval findi : 'a list->f:(int ->'a-> bool)->(int * 'a) option
Sourceval find_mapi : 'a list->f:(int ->'a->'b option)->'b option
t >>= f returns a computation that sequences the computations represented by two monad elements. The resulting computation first does t to yield a value v, and then runs the computation returned by f v.
ignore_m t is map t ~f:(fun _ -> ()). ignore_m used to be called ignore, but we decided that was a bad name, because it shadowed the widely used Stdlib.ignore. Some monads still do let ignore = ignore_m for historical reasons.
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.
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.
Sourceval unordered_append : 'a list->'a list->'a 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.
Sourceval fold2_exn :
'a list->'b list->init:'acc->f:('acc->'a->'b->'acc)->'acc
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.
Sourceval fold_right2_exn :
'a list->'b list->f:('a->'b->'acc->'acc)->init:'acc->'acc
fold_right2 ~f [a1; ...; an] [b1; ...; bn] ~init:c is f a1 b1 (f a2 b2 (... (f an bn c) ...)). The exn version will raise if the two lists have different lengths.
Sourceval rev_filter : 'a list->f:('a-> bool)->'a list
Like filter, but reverses the order of the input list.
Sourceval partition3_map :
'a list->f:('a->[ `Fst of 'b| `Snd of 'c| `Trd of 'd ])->'b list * 'c list * 'd list
Sourceval partition_result :
('ok, 'error)Base.Result.t list->'ok list * 'error list
partition_result l returns a pair of lists (l1, l2), where l1 is the list of all Ok elements in l and l2 is the list of all Error elements. The order of elements in the input list is preserved.
Sourceval split_n : 'a list->int ->'a list * 'a list
split_n [e1; ...; em] n is ([e1; ...; en], [en+1; ...; em]).
If n >= m, ([e1; ...; em], []) is returned.
If n <= 0, ([], [e1; ...; em]) is returned.
In either of these cases, the input list is returned as one side of the pair, rather than being copied.
Sourceval sort : 'a list->compare:('a->'a-> int)->'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, Poly.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.
Sourceval stable_sort : 'a list->compare:('a->'a-> int)->'a list
Like sort, but guaranteed to be stable.
Sourceval merge : 'a list->'a list->compare:('a->'a-> int)->'a list
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.
Sourceval rev_map_append : 'a list->'b list->f:('a->'b)->'b list
rev_map_append l1 l2 ~f reverses l1 mapping f over each element, and appends the result to the front of l2.
Sourceval fold_right : 'a list->f:('a->'acc->'acc)->init:'acc->'acc
fold_right [a1; ...; an] ~f ~init:b is f a1 (f a2 (... (f an b) ...)).
Sourceval fold_left : 'a list->init:'acc->f:('acc->'a->'acc)->'acc
fold_left is the same as Container.S1.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.
Transform a list of pairs into a pair of lists: unzip [(a1,b1); ...; (an,bn)] is ([a1; ...; an], [b1; ...; bn]).
Sourceval unzip : ('a * 'b) list->'a list * 'b list
Sourceval unzip3 : ('a * 'b * 'c) list->'a list * 'b list * 'c list
Transform a pair of lists into an (optional) list of pairs: zip [a1; ...; an] [b1; ...; bn] is [(a1,b1); ...; (an,bn)]. Returns Unequal_lengths if the two lists have different lengths.
Sourceval zip_exn : 'a list->'b list->('a * 'b) list
Sourceval rev_mapi : 'a list->f:(int ->'a->'b)->'b list
Sourceval reduce_exn : 'a list->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.
Sourceval reduce : 'a list->f:('a->'a->'a)->'a option
Sourceval reduce_balanced : 'a list->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.
Sourceval reduce_balanced_exn : 'a list->f:('a->'a->'a)->'a
Sourceval group : 'a list->break:('a->'a-> bool)->'a list list
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']]
Sourceval groupi : 'a list->break:(int ->'a->'a-> bool)->'a list list
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']]
Sourceval sort_and_group : 'a list->compare:('a->'a-> int)->'a list list
Group equal elements into the same buckets. Sorting is stable.
Sourceval chunks_of : 'a list->length:int ->'a list list
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.
Sourceval is_prefix : 'a list->prefix:'a list->equal:('a->'a-> bool)-> bool
is_prefix xs ~prefix returns true if xs starts with prefix.
Sourceval is_suffix : 'a list->suffix:'a list->equal:('a->'a-> bool)-> bool
is_suffix xs ~suffix returns true if xs ends with suffix.
Sourceval find_consecutive_duplicate :
'a list->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.
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.
Sourceval dedup_and_sort : 'a list->compare:('a->'a-> int)->'a list
Returns the given list with duplicates removed and in sorted order. Of duplicates in the original list, the element occurring last in the original list is kept.
Sourceval stable_dedup : 'a list->compare:('a->'a-> int)->'a list
Returns the original list, dropping all occurrences of duplicates after the first.
Sourceval find_a_dup : 'a list->compare:('a->'a-> int)->'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.
Sourceval contains_dup : 'a list->compare:('a->'a-> int)-> bool
Returns true if there are any two elements in the list which are the same. O(n log n) time complexity.
Sourceval find_all_dups : 'a list->compare:('a->'a-> int)->'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.
Sourceval all_equal : 'a list->equal:('a->'a-> bool)->'a option
all_equal returns a single element of the list that is equal to all other elements, or None if no such element exists.
Sourceval range :
?stride:int ->?start:[ `inclusive | `exclusive ]->?stop:[ `inclusive | `exclusive ]->int ->int ->int list
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).
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.
Sourceval rev_filter_map : 'a list->f:('a->'b option)->'b list
rev_filter_map l ~f is the reversed sublist of l containing only elements for which f returns Some e.
Sourceval rev_filter_mapi : 'a list->f:(int ->'a->'b option)->'b list
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.
drop l n returns l without the first n elements, or the empty list if n > length l. drop l n is equivalent to snd (split_n l n). If n <= 0, returns l rather than a copy.
Sourceval take_while : 'a list->f:('a-> bool)->'a list
take_while l ~f returns the longest prefix of l for which f is true.
Sourceval drop_while : 'a list->f:('a-> bool)->'a list
drop_while l ~f drops the longest prefix of l for which f is true.
Sourceval split_while : 'a list->f:('a-> bool)->'a list * 'a list
Sourceval transpose : 'a list list->'a list list option
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.
Sourceval transpose_exn : 'a list list->'a list list
transpose_exn transposes the rows and columns of its argument, throwing an exception if the list is not rectangular.
stable_dedup_staged is the same as dedup_and_sort but maintains the order of the list. This function is staged because it instantiates a functor when compare is passed.
See also Set.stable_dedup_list, which is the underlying implementation of this function and lets you avoid the functor instantiation when you already have such a module on hand.
deprecated [since 2023-04] Use [List.stable_dedup] instead.
exn_if_dup ~compare ?context t ~to_sexp raises if t contains a duplicate. It will specifically raise a Duplicate_found exception and use context as its second argument. O(n log n) time complexity.
slice t start stop returns a new list including elements t.(start) through t.(stop-1), normalized Python-style with the exception that stop = 0 is treated as stop = length t.
zip_with_remainder xs ys zips as many elements as possible of xs and ys together and also returns the un-zipped remainder of the longer input, if the inputs have different lengths.
If xs and ys have the same length, zip_with_remainder xs ys returns the same thing as (zip_exn xs ys, None)