Module Base__List

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

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 reversal.

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.

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.

List.rev_map2_exn l1 l2 ~f gives the same result as List.rev (List.map2_exn l1 l2 ~f), but is more efficient.

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.

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.

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.

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.

Like filter, but reverses the order of the input list

partition_map t ~f partitions t according to f.

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]).

• If n > m, ([e1; ...; em], []) is returned.
• If 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.

Like sort, but guaranteed to be stable

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.

Return the first element of the given list. Raise if the list is empty.

Return the given list without its first element. Raise if the list is empty.

find_exn t ~f returns the first element of t that satisfies f. It raises Not_found if there is no such element.

Returns the first evaluation of f that returns Some. Raises Not_found if f always returns None.

Like find_map and find_map_exn, but pass the index as an argument.

E.g. append [1; 2] [3; 4; 5] is [1; 2; 3; 4; 5]

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.

concat_mapi t ~f is like concat_map, but passes the index as an argument

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.

analogous to rev_map2

analogous to map2

rev_map_append l1 l2 ~f reverses l1 mapping f over each element, and appends the result to the front of l2.

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.

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.

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.

reduce_exn [a1; ...; an] ~f is f (... (f (f a1 a2) a3) ...) an. It fails on the empty list. Tail recursive.

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.

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.

The final element of a list. The _exn version raises on the empty list.

is_prefix xs ~prefix returns true if xs starts with prefix.

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.

remove_consecutive_duplicates. The same list with consecutive duplicates removed. The relative order of the other elements is unaffected. The element kept from a run of duplicates is the last one.

dedup_and_sort The same list with duplicates removed and in sorted order.

contains_dup True if there are any two elements in the list which are the same.

find_a_dup returns a duplicate from the list (no guarantees about which duplicate you get), or None if there are no dups.

find_all_dups returns a list of all elements that occur more than once, with no guarantees about order.

exn_if_dup ?compare ?context t ~to_sexp will run find_a_dup on t, and raise Duplicate_found if a duplicate is found. The context is the second argument of the exception

count l ~f is the number of elements in l that satisfy the predicate f.

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.

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_map l ~f is the sublist of l containing only elements for which f returns Some e.

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.

sub pos len l is the len-element sublist of l, starting at pos.

slice l start stop returns a new list including elements l.(start) through l.(stop-1), normalized python-style.

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).

take_while l ~f returns the longest prefix of l for which f is true.

drop_while l ~f drops the longest prefix of l for which f is true.

split_while xs ~f = (take_while xs ~f, drop_while xs ~f)

Concatenate 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.

permute ?random_state t returns a permutation of t.

permute side affects random_state by repeated calls to Random.State.int. If random_state is not supplied, permute uses Random.State.default.

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 affects random_state by calling Random.State.int. If random_state is not supplied, random_element uses Random.State.default.

is_sorted t ~compare returns true iff forall adjacent a1; a2 in t, compare a1 a2 <= 0.

is_sorted_strictly is similar, except it uses < instead of <=.

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. *

transpose_exn transposes the rows and columns of its argument, throwing an exception if the list is not rectangular. *

intersperse xs ~sep places sep between adjacent elements of xs. e.g. intersperse [1;2;3] ~sep:0 = [1;0;2;0;3]