A sequence of elements that can be produced one at a time, on demand, normally with no sharing.
The elements are computed on demand, possibly repeating work if they are demanded multiple times. A sequence can be built by unfolding from some initial state, which will in practice often be other containers.
Most functions constructing a sequence will not immediately compute any elements of the sequence. These functions will always return in O(1), but traversing the resulting sequence may be more expensive. The most they will do immediately is generate a new internal state and a new step function.
Functions that transform existing sequences sometimes have to reconstruct some suffix
of the input sequence, even if it is unmodified. For example, calling
drop 1 will
return a sequence with a slightly larger state and whose elements all cost slightly
more to traverse. Because this is sometimes undesirable (for example, applying
1 n times will cost O(n) per element traversed in the result), there are also more
eager versions of many functions (whose names are suffixed with
_eagerly) that do
more work up front. A function has the
_eagerly suffix iff it matches both of these
* It might consume an element from an input
t before returning.
* It only returns a
t (not paired with something else, not wrapped in an
etc.). If it returns anything other than a
t and it has at least one
it's probably demanding elements from the input
*_exn functions can raise exceptions, except if the function underlying the
f passed to
unfold) raises, in which case the exception will
Checks whether the provided element is there, using polymorphic compare if
is not provided
fold t ~init ~f returns
f (... f (f (f init e1) e2) e3 ...) en, where
are the elements of
true if and only if there exists an element for which the provided
function evaluates to
true. This is a short-circuiting operation.
true if and only if the provided function evaluates to
true for all
elements. This is a short-circuiting operation.
Returns the number of elements for which the provided function evaluates to true.
Returns as an
option the first element for which
f evaluates to true.
Returns the first evaluation of
f that returns
Some, and returns
None if there
is no such element.
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
fold so it has the same complexity as
A monad is an abstraction of the concept of sequencing of computations. A value of type 'a monad represents a computation that returns a value of type 'a.
return v returns the (trivial) computation that returns v.
empty is a sequence with no elements.
Stepdescribes the next step of the sequence construction.
unfold ~init f is a simplified version of
unfold_step that does not allow
unfold_with_and_finish t ~init ~running_step ~inner_finished ~finishing_step folds a
state through the sequence
t to create a new sequence. The new sequence can
t has finished.
return the nth element
find_exn t ~f returns the first element of
t that satisfies
f. It raises if
there is no such element.
interleave tt produces each element of the inner sequences of
tt eventually, even
if any or all of the inner sequences are infinite. The elements of each inner
sequence are produced in order with respect to that inner sequence. The manner of
interleaving among the separate inner sequences is deterministic but unspecified.
Transforms a pair of sequences into a sequence of pairs. The length of the returned sequence is the length of the shorter input. The remaining elements of the longer input are discarded.
List.zip, this will not error out if the two input sequences are of
different lengths, because
zip may have already returned some elements by the time
this becomes apparent.
iteri is just like
iter, but it also passes in the index of each element to
foldi is just like
fold, but it also passes in the index of each element to
reduce_exn f [a1; ...; an] is
f (... (f (f a1 a2) a3) ...) an. It fails on the
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
range ?stride ?start ?stop start_i stop_i is the sequence of integers from
stop_i, stepping by
stride < 0 then we need
for the result to be nonempty (or
stop_i in the case where both bounds
init n ~f is
[(f 0); (f 1); ...; (f (n-1))]. It is an error if
n < 0.
drop_while_option t ~f immediately consumes the elements from
t until the
f fails and returns the first element that failed along with the
unevaluated tail of
t. The first element is returned separately because the
alternatives would mean forcing the consumer to evaluate the first element again (if
the previous state of the sequence is returned) or take on extra cost for each element
(if the element is added to the final state of the sequence using
shift_right_with_list t l produces the elements of
l, then produces the elements
t. It is better to call
shift_right_with_list with a list of size n than
shift_right n times; the former will require O(1) work per element produced and the
latter O(n) work per element produced.
Returns a sequence with all possible pairs. The stepper function of the second
sequence passed as argument may be applied to the same state multiple times, so be
cartesian_product with expensive or side-effecting functions. If the
second sequence is infinite, some values in the first sequence may not be reached.
Returns a sequence that eventually reaches every possible pair of elements of the
inputs, even if either or both are infinite. The step function of both inputs may be
applied to the same state repeatedly, so be careful using
interleaved_cartesian_product with expensive or side-effecting functions.
cycle_list_exn xs repeats the elements of
xs forever. If
xs is empty, it
repeat a repeats
singleton a produces
a exactly once.
delayed_fold allows to do an on-demand fold, while maintaining a state. This
function is sufficient to implement
fold_m in any monad.
let fold_m t ~init ~f = let open M in delayed_fold t ~init ~f:(fun s a ~k -> f s a >>= k) ~finish:return
It is possible to exit early by not calling
f. It is also possible to call
k multiple times. This results in the rest of the sequence being folded over
multiple times, independently.
to_list_rev t returns a list of the elements of
t, in reverse order. It is faster
bounded_length ~at_most t returns
`Is len if
len = length t <= at_most, and
`Greater. Walks through only as much of the sequence as
necessary. Always returns
at_most < 0.
length_is_bounded_by ~min ~max t returns true if
min <= length t and
length t <=
max are not provided, the check for that bound is omitted. Walks
through only as much of the sequence as necessary.
Generator is a monadic interface to generate sequences in a direct style, similar to
Here are some examples:
open Generator let rec traverse_list = function |  -> return () | x :: xs -> yield x >>= fun () -> traverse_list xs let traverse_option = function | None -> return () | Some x -> yield x let traverse_array arr = let n = Array.length arr in let rec loop i = if i >= n then return () else yield arr.(i) >>= fun () -> loop (i + 1) in loop 0 let rec traverse_bst = function | Node.Empty -> return () | Node.Branch (left, value, right) -> traverse_bst left >>= fun () -> yield value >>= fun () -> traverse_bst right let sequence_of_list x = Generator.run (traverse_list x) let sequence_of_option x = Generator.run (traverse_option x) let sequence_of_array x = Generator.run (traverse_array x) let sequence_of_bst x = Generator.run (traverse_bst x)