Legend:
Library
Module
Module type
Parameter
Class
Class type
List operations.
OCaml's lists are immutable, singly-linked lists, which therefore give 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.
val fold : 'at->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 :
'at->init:'accum->f:('accum->'a->('accum, 'e)Result.t)->('accum, 'e)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.
fold_until t ~init ~f 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.
Returns a minimum (resp maximum) element from the collection using the provided cmp 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.
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 Pervasives.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.
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.
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.
val iter2_exn : 'at->'bt->f:('a->'b-> unit)-> unit
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 fold2_exn : 'at->'bt->init:'c->f:('c->'a->'b->'c)->'c
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.
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).
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.
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.
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.
val reduce_balanced : 'at->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.
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' ->
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 is_prefix : 'at->prefix:'at->equal:('a->'a-> bool)-> bool
is_prefix xs ~prefix returns true if xs starts with prefix.
val find_consecutive_duplicate :
'at->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 : 'at->equal:('a->'a-> bool)->'at
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.
val dedup_and_sort : ?compare:('a->'a-> int)->'at->'at
dedup_and_sort The same list with duplicates removed and in sorted order.
val exn_if_dup :
?compare:('a->'a-> int)->?context:string ->'at->to_sexp:('a->Sexp.t)->
unit
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
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).
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.
val rev_filter_mapi : 'at->f:(int ->'a->'b option)->'bt
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.
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.
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. *