#### oseq

## OSeq: Functional Iterators

`include module type of Seq with type 'a node = 'a Seq.node`

`type 'a t = unit -> 'a node`

A sequence `xs`

of type `'a t`

is a delayed list of elements of type `'a`

. Such a sequence is queried by performing a function application `xs()`

. This function application returns a node, allowing the caller to determine whether the sequence is empty or nonempty, and in the latter case, to obtain its head and tail.

A node is either `Nil`

, which means that the sequence is empty, or `Cons (x, xs)`

, which means that `x`

is the first element of the sequence and that `xs`

is the remainder of the sequence.

## Consuming sequences

The functions in this section consume their argument, a sequence, either partially or completely:

`is_empty`

and`uncons`

consume the sequence down to depth 1. That is, they demand the first argument of the sequence, if there is one.`iter`

,`fold_left`

,`length`

, etc., consume the sequence all the way to its end. They terminate only if the sequence is finite.`for_all`

,`exists`

,`find`

, etc. consume the sequence down to a certain depth, which is a priori unpredictable.

Similarly, among the functions that consume two sequences, one can distinguish two groups:

`iter2`

and`fold_left2`

consume both sequences all the way to the end, provided the sequences have the same length.`for_all2`

,`exists2`

,`equal`

,`compare`

consume the sequences down to a certain depth, which is a priori unpredictable.

The functions that consume two sequences can be applied to two sequences of distinct lengths: in that case, the excess elements in the longer sequence are ignored. (It may be the case that one excess element is demanded, even though this element is not used.)

None of the functions in this section is lazy. These functions are consumers: they force some computation to take place.

If `xs`

is empty, then `uncons xs`

is `None`

.

If `xs`

is nonempty, then `uncons xs`

is `Some (head xs, tail xs)`

, that is, a pair of the head and tail of the sequence `xs`

.

This equivalence holds if `xs`

is persistent. If `xs`

is ephemeral, then `uncons`

must be preferred over separate calls to `head`

and `tail`

, which would cause `xs`

to be queried twice.

`val fold_lefti : ( 'b -> int -> 'a -> 'b ) -> 'b -> 'a t -> 'b`

`fold_lefti f _ xs`

invokes `f _ i x`

successively for every element `x`

located at index `i`

of the sequence `xs`

.

An accumulator of type `'b`

is threaded through the calls to `f`

.

It terminates only if the sequence `xs`

is finite.

`fold_lefti f accu xs`

is equivalent to `fold_left (fun accu (i, x) -> f accu i x) accu (zip (ints 0) xs)`

.

`fold_left2 f _ xs ys`

invokes `f _ x y`

successively for every pair `(x, y)`

of elements drawn synchronously from the sequences `xs`

and `ys`

.

An accumulator of type `'a`

is threaded through the calls to `f`

.

If the sequences `xs`

and `ys`

have different lengths, then iteration stops as soon as one sequence is exhausted; the excess elements in the other sequence are ignored.

Iteration terminates only if at least one of the sequences `xs`

and `ys`

is finite.

`fold_left2 f accu xs ys`

is equivalent to `fold_left (fun accu (x, y) -> f accu x y) (zip xs ys)`

.

## Constructing sequences

The functions in this section are lazy: that is, they return sequences whose elements are computed only when demanded.

`val forever : ( unit -> 'a ) -> 'a t`

`forever f`

is an infinite sequence where every element is produced (on demand) by the function call `f()`

.

For instance, `forever Random.bool`

is an infinite sequence of random bits.

`forever f`

is equivalent to `map f (repeat ())`

.

## Transforming sequences

The functions in this section are lazy: that is, they return sequences whose elements are computed only when demanded.

This exception is raised when a sequence returned by `once`

(or a suffix of it) is queried more than once.

The sequence `once xs`

has the same elements as the sequence `xs`

.

Regardless of whether `xs`

is ephemeral or persistent, `once xs`

is an ephemeral sequence: it can be queried at most once. If it (or a suffix of it) is queried more than once, then the exception `Forced_twice`

is raised. This can be useful, while debugging or testing, to ensure that a sequence is consumed at most once.

If `xss`

is a matrix (a sequence of rows), then `transpose xss`

is the sequence of the columns of the matrix `xss`

.

The rows of the matrix `xss`

are not required to have the same length.

The matrix `xss`

is not required to be finite (in either direction).

The matrix `xss`

must be persistent.

## Combining sequences

If `xss`

is a sequence of sequences, then `concat xss`

is its concatenation.

If `xss`

is the sequence `xs0; xs1; ...`

then `concat xss`

is the sequence `xs0 @ xs1 @ ...`

.

`concat_map f xs`

is equivalent to `concat (map f xs)`

.

`concat_map`

is an alias for `flat_map`

.

The sequence `map_product f xs ys`

is the image through `f`

of the Cartesian product of the sequences `xs`

and `ys`

.

For every element `x`

of `xs`

and for every element `y`

of `ys`

, the element `f x y`

appears once as an element of `map_product f xs ys`

.

The order in which these elements appear is unspecified.

The sequences `xs`

and `ys`

are not required to be finite.

The sequences `xs`

and `ys`

must be persistent.

`map_product f xs ys`

is equivalent to `map (fun (x, y) -> f x y) (product xs ys)`

.

## Splitting a sequence into two sequences

`partition_map f xs`

returns a pair of sequences `(ys, zs)`

, where:

`ys`

is the sequence of the elements`y`

such that`f x = Left y`

, where`x`

ranges over`xs`

;

`zs`

is the sequence of the elements`z`

such that`f x = Right z`

, where`x`

ranges over`xs`

.

`partition_map f xs`

is equivalent to a pair of `filter_map Either.find_left (map f xs)`

and `filter_map Either.find_right (map f xs)`

.

Querying either of the sequences returned by `partition_map f xs`

causes `xs`

to be queried. Therefore, querying both of them causes `xs`

to be queried twice. Thus, `xs`

must be persistent and cheap. If that is not the case, use `partition_map f (memoize xs)`

.

## Converting between sequences and dispensers

A dispenser is a representation of a sequence as a function of type `unit -> 'a option`

. Every time this function is invoked, it returns the next element of the sequence. When there are no more elements, it returns `None`

. A dispenser has mutable internal state, therefore is ephemeral: the sequence that it represents can be consumed at most once.

`val of_dispenser : ( unit -> 'a option ) -> 'a t`

`of_dispenser it`

is the sequence of the elements produced by the dispenser `it`

. It is an ephemeral sequence: it can be consumed at most once. If a persistent sequence is needed, use `memoize (of_dispenser it)`

.

`val to_dispenser : 'a t -> unit -> 'a option`

`to_dispenser xs`

is a fresh dispenser on the sequence `xs`

.

This dispenser has mutable internal state, which is not protected by a lock; so, it must not be used by several threads concurrently.

## Sequences of integers

`val ints : int -> int t`

`ints i`

is the infinite sequence of the integers beginning at `i`

and counting up.

`type 'a seq = 'a t`

`type 'a printer = Format.formatter -> 'a -> unit`

`val empty : 'a t`

Empty iterator, with no elements

`val return : 'a -> 'a t`

One-element iterator

`val repeat : 'a -> 'a t`

Repeat same element endlessly

`val head_exn : 'a t -> 'a`

Returns first element, or fails.

Cycle through the iterator infinitely. The iterator shouldn't be empty.

```
# OSeq.(cycle (1--3) |> take 10 |> to_list);;
- : int list = [1; 2; 3; 1; 2; 3; 1; 2; 3; 1]
```

`val iterate : 'a -> ( 'a -> 'a ) -> 'a t`

`iterate x f`

is `[x; f x; f (f x); f (f (f x)); ...]`

.

```
# OSeq.(iterate 0 succ |> take 10 |> to_list);;
- : int list = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9]
```

`val unfold : ( 'b -> ('a * 'b) option ) -> 'b -> 'a t`

Dual of `fold`

, with a deconstructing operation. It keeps on unfolding the `'b`

value into a new `'b`

, and a `'a`

which is yielded, until `None`

is returned.

```
# OSeq.(unfold (fun x -> if x<5 then Some (string_of_int x, x+1) else None) 0 |> to_list);;
- : string list = ["0"; "1"; "2"; "3"; "4"]
```

`val repeatedly : ( unit -> 'a ) -> 'a t`

Call the same function an infinite number of times (useful for instance if the function is a random iterator).

`val init : ?n:int -> ( int -> 'a ) -> 'a t`

Calls the function, starting from 0, on increasing indices. If `n`

is provided and is a positive int, iteration will stop at the limit (excluded). For instance `init ~n:4 (fun x->x)`

will yield 0, 1, 2, and 3.

### Basic combinators

`val is_empty : _ t -> bool`

Check whether the iterator is empty. Pops an element, if any

`val fold : ( 'b -> 'a -> 'b ) -> 'b -> 'a t -> 'b`

Fold on the iterator, tail-recursively.

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

Fold on the iterator, tail-recursively.

`val reduce : ( 'a -> 'a -> 'a ) -> 'a t -> 'a`

Fold on non-empty iterators.

Like `fold`

, but keeping successive values of the accumulator.

```
# OSeq.(scan (+) 0 (1--5) |> to_list);;
- : int list = [0; 1; 3; 6; 10; 15]
```

`val iter : ( 'a -> unit ) -> 'a t -> unit`

Iterate on the iterator .

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

Iterate on elements with their index in the iterator, from 0.

`val length : _ t -> int`

Length of an iterator (linear time).

Lazy map. No iteration is performed now, the function will be called when the result is traversed.

Lazy map with indexing starting from 0. No iteration is performed now, the function will be called when the result is traversed.

Lazy fold and map. No iteration is performed now, the function will be called when the result is traversed. The result is an iterator over the successive states of the fold. The final accumulator is discarded. Unlike `scan`

, fold_map does not return the first accumulator.

Append the two iterators; the result contains the elements of the first, then the elements of the second iterator.

Monadic bind; each element is transformed to a sub-iterator which is then iterated on, before the next element is processed, and so on.

Same as `app`

but interleaves the values of the function and the argument iterators. See `interleave`

for more details.

`flat_map_interleave f seq`

is similar to `flat_map f seq`

, except that each sub-sequence is interleaved rather than concatenated in order. See `interleave`

for more details.

`val mem : eq:( 'a -> 'a -> bool ) -> 'a -> 'a t -> bool`

Is the given element, member of the iterator?

`val nth : int -> 'a t -> 'a`

n-th element, or Not_found

`take_nth n g`

returns every element of `g`

whose index is a multiple of `n`

. For instance `take_nth 2 (1--10) |> to_list`

will return `[1;3;5;7;9]`

`val fold_while : ( 'a -> 'b -> 'a * [ `Stop | `Continue ] ) -> 'a -> 'b t -> 'a`

Fold elements until (`'a, `Stop`

) is indicated by the accumulator.

`partition p l`

returns the elements that satisfy `p`

, and the elements that do not satisfy `p`

`val for_all : ( 'a -> bool ) -> 'a t -> bool`

Is the predicate true for all elements?

`val exists : ( 'a -> bool ) -> 'a t -> bool`

Is the predicate true for at least one element?

`val min : lt:( 'a -> 'a -> bool ) -> 'a t -> 'a`

Minimum element, according to the given comparison function.

Lexicographic comparison of iterators. If a iterator is a prefix of the other one, it is considered smaller.

`val find : ( 'a -> bool ) -> 'a t -> 'a option`

`find p e`

returns the first element of `e`

to satisfy `p`

, or None.

`val find_map : ( 'a -> 'b option ) -> 'a t -> 'b option`

`find_map f e`

returns the result of `f`

on the first element of `e`

for which it returns `Some _`

, or `None`

otherwise.

`val sum : int t -> int`

Sum of all elements

### Multiple iterators

Map on the two iterators. Stops once one of them is exhausted.

Iterate on the two iterators. Stops once one of them is exhausted.

Fold the common prefix of the two iterators

Succeeds if all pairs of elements satisfy the predicate. Ignores elements of an iterator if the other runs dry.

Succeeds if some pair of elements satisfy the predicate. Ignores elements of an iterator if the other runs dry.

Combine common part of the gens (stops when one is exhausted)

### Complex combinators

Pick elements fairly in each sub-iterator. The merge of gens `e1, e2, ... `

picks elements in `e1`

, `e2`

, in `e3`

, `e1`

, `e2`

.... Once an iterator is empty, it is skipped; when they are all empty, and none remains in the input, their merge is also empty. For instance, `merge [1;3;5] [2;4;6]`

will be, in disorder, `1;2;3;4;5;6`

.

Intersection of two sorted iterators. Only elements that occur in both inputs appear in the output

Merge two sorted iterators into a sorted iterator

Split the iterator into `n`

iterators in a fair way. Elements with `index = k mod n`

with go to the k-th iterator. `n`

default value is 2.

`interleave a b`

yields an element of `a`

, then an element of `b`

, and so on. When one of the iterators is exhausted, this behaves like the other iterator.

Put the separator element between all elements of the given iterator

Cartesian product, in no predictable order. Works even if some of the arguments are infinite.

Cartesian product of three iterators, see product.

Cartesian product of four iterators, see product.

Cartesian product of five iterators, see product.

Cartesian product of six iterators, see product.

```
val product7 :
'a t ->
'b t ->
'c t ->
'd t ->
'e t ->
'f t ->
'g t ->
('a * 'b * 'c * 'd * 'e * 'f * 'g) t
```

Cartesian product of seven iterators, see product.

Produce the cartesian product of this sequence of sequences, by returning all the ways of picking one element per sequence. **NOTE** the order of the returned sequence is unspecified.

This assumes each sub-sequence is finite, and that the main sequence is also finite.

For example:

```
# cartesian_product [[1;2];[3];[4;5;6]] |> sort =
[[1;3;4];[1;3;5];[1;3;6];[2;3;4];[2;3;5];[2;3;6]];;
# cartesian_product [[1;2];[];[4;5;6]] = [];;
# cartesian_product [[1;2];[3];[4];[5];[6]] |> sort =
[[1;3;4;5;6];[2;3;4;5;6]];;
```

invariant: `cartesian_product l = map_product_l id l`

.

`map_product_l f l`

maps each element of `l`

to a list of objects of type `'b`

using `f`

. We obtain `[l1;l2;...;ln]`

where `length l=n`

and `li : 'b list`

. Then, it returns all the ways of picking exactly one element per `li`

.

Remove consecutive duplicate elements. Basically this is like `fun e -> map List.hd (group e)`

.

Sort according to the given comparison function. The iterator must be finite.

Sort and remove duplicates. The iterator must be finite.

`chunks n e`

returns a iterator of arrays of length `n`

, composed of successive elements of `e`

. The last array may be smaller than `n`

`val permutations : 'a list -> 'a list t`

Permutations of the list.

Combinations of given length. The ordering of the elements within each combination is unspecified. Example (ignoring ordering): `combinations 2 (1--3) |> to_list = [[1;2]; [1;3]; [2;3]]`

All subsets of the iterator (in no particular order). The ordering of the elements within each subset is unspecified.

### Relational combinators

`module type HashedType = Hashtbl.HashedType`

A type that can be compared and hashed. invariant: for any `x`

and `y`

, if `equal x y`

then `hash x=hash y`

must hold.

```
val group_by :
(module HashedType with type t = 'key) ->
project:( 'a -> 'key ) ->
'a t ->
('key * 'a list) t
```

Group together elements that project onto the same key, ignoring their order of appearance. The order of each resulting list is unspecified.

This function needs to consume the whole input before it can emit anything.

```
val group_by_fold :
(module HashedType with type t = 'key) ->
project:( 'a -> 'key ) ->
fold:( 'b -> 'a -> 'b ) ->
init:'b ->
'a t ->
('key * 'b) t
```

Group together elements that project onto the same key, folding them into some aggregate of type `'b`

as they are met. This is the most general version of the "group_by" functions.

This function needs to consume the whole input before it can emit anything.

`val group_count : (module HashedType with type t = 'a) -> 'a t -> ('a * int) t`

Map each distinct element to its number of occurrences in the whole seq. Similar to `group_by_fold hash_key ~project:(fun x->x) ~fold:(fun a _->a+1) ~init:0 seq`

.

This function needs to consume the whole input before it can emit anything.

```
val join_by :
(module HashedType with type t = 'key) ->
project_left:( 'a -> 'key ) ->
project_right:( 'b -> 'key ) ->
merge:( 'key -> 'a -> 'b -> 'c option ) ->
'a t ->
'b t ->
'c t
```

`join_by ~project_left ~project_right ~merge a b`

takes every pair of elements `x`

from `a`

and `y`

from `b`

, and if they map onto the same key `k`

by `project_left`

and `project_right`

respectively, and if `merge k x y = Some res`

, then it yields `res`

.

If `merge k x y`

returns `None`

, the combination of values is discarded.

This function works with infinite inputs, it does not have to consume the whole input before yielding elements.

```
val join_by_fold :
(module HashedType with type t = 'key) ->
project_left:( 'a -> 'key ) ->
project_right:( 'b -> 'key ) ->
init:'c ->
merge:( 'key -> 'a -> 'b -> 'c -> 'c ) ->
'a t ->
'b t ->
'c t
```

`join_by_fold ~project_left ~project_right ~init ~merge a b`

takes every pair of elements `x`

from `a`

and `y`

from `b`

, and if they map onto the same key `k`

by `project_left`

and `project_right`

respectively, it fold `x`

and `y`

into the accumulator for this key (which starts at `init`

).

This function consumes both inputs entirely before it emits anything.

### Basic conversion functions

`val of_list : 'a list -> 'a t`

Enumerate elements of the list

`val to_list : 'a t -> 'a list`

non tail-call trasnformation to list, in the same order

`val to_rev_list : 'a t -> 'a list`

Tail call conversion to list, in reverse order (more efficient)

`val to_array : 'a t -> 'a array`

Convert the iterator to an array (not very efficient). The iterator must be memoized, as it's traversed twice.

`val of_array : ?start:int -> ?len:int -> 'a array -> 'a t`

Iterate on (a slice of) the given array

Build a functional iterator from a mutable, imperative generator. The result is properly memoized and can be iterated on several times, as a normal functional value.

`val of_string : ?start:int -> ?len:int -> string -> char t`

Iterate on bytes of the string

`val to_string : char t -> string`

Convert into a string

Traverse the iterator and writes its content to the buffer

`val concat_string : sep:string -> string t -> string`

`concat_string ~sep s`

concatenates all strings of `i`

, separated with `sep`

. The iterator must be memoized.

`module Infix : sig ... end`

Pretty print the content of the iterator on a formatter.

Store content of the transient iterator in memory, to be able to iterate on it several times later.

### Easy interface to Produce Iterators

`module Generator : sig ... end`

This interface is designed to make it easy to build complex streams of values in a way that resembles Python's generators (using "yield").

`module IO : sig ... end`

`module type MONAD = sig ... end`