Up
# module Sequence

: sig

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 ```
drop
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
conditions:

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 `option`

,
etc.). If it returns anything other than a `t`

and it has at least one `t`

input,
it's probably demanding elements from the input `t`

anyway.

Only `*_exn`

functions can raise exceptions, except if the function underlying the
sequence (the `f`

passed to `unfold`

) raises, in which case the exception will
cascade.

#

type +'a t

#

module Step : sig

A `Step`

describes the next step of the sequence construction. `Done`

indicates the
sequence is finished. `Skip`

indicates the sequence continues with another state
without producing the next element yet. `Yield`

outputs an element and introduces a
new state.

Modifying `'s`

doesn't violate any *internal* invariants, but it may violate some
undocumented expectations. For example, one might expect that producing an element
from the same point in the sequence would always give the same value, but if the state
can mutate, that is not so.

end

#

val unfold : init:'s -> f:('s -> ('a * 's) option) -> 'a t

`unfold ~init f`

is a simplified version of `unfold_step`

that does not allow
`Skip`

.

#

val find_exn : 'a t -> f:('a -> bool) -> 'a

`find_exn t ~f`

returns the first element of `t`

that satisfies `f`

. It raises if
there is no such element.

#

val zip : 'a t -> 'b t -> ('a * 'b) t

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.

WARNING: Unlike `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.

#

val iteri : 'a t -> f:(int -> 'a -> unit) -> unit

`iteri`

is just like `iter`

, but it also passes in the index of each element to
`f`

.

#

val foldi : 'a t -> f:(int -> 'b -> 'a -> 'b) -> init:'b -> 'b

`foldi`

is just like `fold`

, but it also passes in the index of each element to
`f`

.

#

val reduce_exn : 'a t -> f:('a -> 'a -> 'a) -> 'a

`reduce_exn f [a1; ...; an]`

is `f (... (f (f a1 a2) a3) ...) an`

. It fails on the
empty sequence.

#

val find_consecutive_duplicate : 'a t -> 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`

.

#

val range : ?stride:int -> ?start:[

| `inclusive

| `exclusive

] -> ?stop:[ | `inclusive

| `exclusive

] -> int -> int -> int t
`range ?stride ?start ?stop start_i stop_i`

is the sequence 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).

#

val init : int -> f:(int -> 'a) -> 'a t

`init n ~f`

is `[(f 0); (f 1); ...; (f (n-1))]`

. It is an error if `n < 0`

.

#

val drop_while_option : 'a t -> f:('a -> bool) -> ('a * 'a t) option

`drop_while_option t ~f`

immediately consumes the elements from `t`

until the
predicate `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`

).

#

val shift_right_with_list : 'a t -> 'a list -> 'a t

`shift_right_with_list t l`

produces the elements of `l`

, then produces the elements
of `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
later O(n) work per element produced.

#

val delayed_fold : 'a t -> init:'s -> f:('s -> 'a -> k:('s -> 'r) -> 'r) -> finish:('s -> 'r) -> 'r

`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 `k`

in `f`

. It is also possible to call
`k`

multiple times. This results in the rest of the sequence being folded over
multiple times, independently.

#

val to_list_rev : 'a t -> 'a list

`to_list_rev t`

returns a list of the elements of `t`

, in reverse order. It is faster
than `to_list`

.

#

val bounded_length : _ t -> at_most:int -> [

| `Is of int

| `Greater

]
`bounded_length ~at_most t`

returns ``Is len`

if `len = length t <= at_most`

, and
otherwise returns ``Greater`

. Walks through only as much of the sequence as
necessary. Always returns ``Greater`

if `at_most < 0`

.

#

val length_is_bounded_by : ?min:int -> ?max:int -> _ t -> bool

`length_is_bounded_by ~min ~max t`

returns true if `min <= length t`

and ```
length t <=
max
```

When `min`

or `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
Python's generators.

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

end