module Sequence:`sig`

..`end`

The iterators are designed to allow easy transfer (mappings) between data structures, without defining

`n^2`

conversions between the `n`

types. The
implementation relies on the assumption that a sequence can be iterated
on as many times as needed; this choice allows for high performance
of many combinators. However, for transient iterators, the `Sequence.persistent`

function is provided, storing elements of a transient iterator
in memory; the iterator can then be used several times (See further).
Note that some combinators also return sequences (e.g. `group`

). The
transformation is computed on the fly every time one iterates over
the resulting sequence. If a transformation performs heavy computation,
`Sequence.persistent`

can also be used as intermediate storage.

Most functions are **lazy**, i.e. they do not actually use their arguments
until their result is iterated on. For instance, if one calls `Sequence.map`

on a sequence, one gets a new sequence, but nothing else happens until
this new sequence is used (by folding or iterating on it).

If a sequence is built from an iteration function that is **repeatable**
(i.e. calling it several times always iterates on the same set of
elements, for instance List.iter or Map.iter), then
the resulting `Sequence.t`

object is also repeatable. For **one-time iter functions**
such as iteration on a file descriptor or a `Stream`

,
the `Sequence.persistent`

function can be used to iterate and store elements in
a memory structure; the result is a sequence that iterates on the elements
of this memory structure, cheaply and repeatably.

type`'a`

t =`('a -> unit) -> unit`

A sequence of values of type

`'a`

. If you give it a function `'a -> unit`

it will be applied to every element of the sequence successively.type`'a`

sequence =`'a t`

type`('a, 'b)`

t2 =`('a -> 'b -> unit) -> unit`

Sequence of pairs of values of type

`'a`

and `'b`

.type`'a`

equal =`'a -> 'a -> bool`

type`'a`

hash =`'a -> int`

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

Build a sequence from a iter function

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

Call the function repeatedly until it returns None. This
sequence is transient, use

`Sequence.persistent`

if needed!`val empty : ``'a t`

Empty sequence. It contains no element.

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

Singleton sequence, with exactly one element.

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

Sequence with exactly two elements

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

`init f`

is the infinite sequence `f 0; f 1; f 2; …`

.`val cons : ``'a -> 'a t -> 'a t`

`cons x l`

yields `x`

, then yields from `l`

.
Same as `append (singleton x) l`

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

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

Synonym to

`Sequence.singleton`

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

Synonym to

`Sequence.singleton`

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

Infinite sequence of the same element. You may want to look
at

`Sequence.take`

and the likes if you iterate on it.`val iterate : ``('a -> 'a) -> 'a -> 'a t`

`iterate f x`

is the infinite sequence `x, f(x), f(f(x)), ...`

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

Sequence that calls the given function to produce elements.
The sequence may be transient (depending on the function), and definitely
is infinite. You may want to use

`Sequence.take`

and `Sequence.persistent`

.`val cycle : ``'a t -> 'a t`

Cycle forever through the given sequence. Assume the given sequence can
be traversed any amount of times (not transient). This yields an
infinite sequence, you should use something like

`Sequence.take`

not to loop
forever.`val iter : ``('a -> unit) -> 'a t -> unit`

Consume the sequence, passing all its arguments to the function.
Basically

`iter f seq`

is just `seq f`

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

Iterate on elements and their index in the sequence

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

Fold over elements of the sequence, consuming it

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

Fold over elements of the sequence and their index, consuming it

`val fold_map : ``('acc -> 'a -> 'acc * 'b) -> 'acc -> 'a t -> 'b t`

`fold_map f acc l`

is like `Sequence.map`

, but it carries some state as in
`Sequence.fold`

. The state is not returned, it is just used to thread some
information to the map function.`val fold_filter_map : ``('acc -> 'a -> 'acc * 'b option) -> 'acc -> 'a t -> 'b t`

`fold_filter_map f acc l`

is a `Sequence.fold_map`

-like function, but the
function can choose to skip an element by retuning `None`

.`val map : ``('a -> 'b) -> 'a t -> 'b t`

Map objects of the sequence into other elements, lazily

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

Map objects, along with their index in the sequence

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

Map objects two by two. lazily.
The last element is kept in the sequence if the count is odd.

**Since** 0.7

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

Do all elements satisfy the predicate?

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

Exists there some element satisfying the predicate?

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

Is the value a member of the sequence?

**Since** 0.5

`eq`

: the equality predicate to use (default `(=)`

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

Find the first element on which the function doesn't return

**Since** 0.5

`None`

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

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

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

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

`find_pred p l`

finds the first element of `l`

that satisfies `p`

,
or returns `None`

if no element satisfies `p`

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

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

How long is the sequence? Forces the sequence.

`val is_empty : ``'a t -> bool`

Is the sequence empty? Forces the sequence.

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

Filter on elements of the sequence

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

Append two sequences. Iterating on the result is like iterating
on the first, then on the second.

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

Concatenate a sequence of sequences into one sequence.

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

Alias for

`Sequence.concat`

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

Monadic bind. Intuitively, it applies the function to every
element of the initial sequence, and calls

**Since** 0.5

`Sequence.concat`

.
Formerly `flatMap`

`val flat_map_l : ``('a -> 'b list) -> 'a t -> 'b t`

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

Map and only keep non-

**Since** 0.5

`None`

elements
Formerly `fmap`

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

Insert the single element between every element of the sequence

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

Iterate on the sequence, storing elements in an efficient internal structure..
The resulting sequence can be iterated on as many times as needed.
**Note**: calling persistent on an already persistent sequence
will still make a new copy of the sequence!

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

Lazy version of

`Sequence.persistent`

. When calling `persistent_lazy s`

,
a new sequence `s'`

is immediately returned (without actually consuming
`s`

) in constant time; the first time `s'`

is iterated on,
it also consumes `s`

and caches its content into a inner data
structure that will back `s'`

for future iterations.
**warning**: on the first traversal of `s'`

, if the traversal
is interrupted prematurely (`Sequence.take`

, etc.) then `s'`

will not be
memorized, and the next call to `s'`

will traverse `s`

again.

`val sort : ``?cmp:('a -> 'a -> int) -> 'a t -> 'a t`

Sort the sequence. Eager, O(n) ram and O(n ln(n)) time.
It iterates on elements of the argument sequence immediately,
before it sorts them.

`val sort_uniq : ``?cmp:('a -> 'a -> int) -> 'a t -> 'a t`

Sort the sequence and remove duplicates. Eager, same as

`sort`

`val sorted : ``?cmp:('a -> 'a -> int) -> 'a t -> bool`

`val group_succ_by : ``?eq:('a -> 'a -> bool) -> 'a t -> 'a list t`

Group equal consecutive elements.
Formerly synonym to

**Since** 0.6

`group`

.`val group_by : ``?hash:('a -> int) ->`

?eq:('a -> 'a -> bool) -> 'a t -> 'a list t

Group equal elements, disregarding their order of appearance.
The result sequence is traversable as many times as required.

**Since** 0.6

`val count : ``?hash:('a -> int) ->`

?eq:('a -> 'a -> bool) -> 'a t -> ('a * int) t

Map each distinct element to its number of occurrences in the whole seq.
Similar to

**Since** 0.10

`group_by seq |> map (fun l->List.hd l, List.length l)`

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

Remove consecutive duplicate elements. Basically this is
like

`fun seq -> map List.hd (group seq)`

.`val product : ``'a t -> 'b t -> ('a * 'b) t`

Cartesian product of the sequences. When calling **MUST** ensure that

`product a b`

,
the caller `b`

can be traversed as many times
as required (several times), possibly by calling `Sequence.persistent`

on it
beforehand.`val diagonal_l : ``'a list -> ('a * 'a) t`

All pairs of distinct positions of the list.

**Since** 0.9

`diagonal l`

will
return the sequence of all `List.nth i l, List.nth j l`

if `i < j`

.`val diagonal : ``'a t -> ('a * 'a) t`

All pairs of distinct positions of the sequence.
Iterates only once on the sequence, which must be finite.

**Since** 0.9

`val product2 : ``'a t -> 'b t -> ('a, 'b) t2`

`val join : ``join_row:('a -> 'b -> 'c option) ->`

'a t -> 'b t -> 'c t

`join ~join_row a b`

combines every element of `a`

with every
element of `b`

using `join_row`

. If `join_row`

returns None, then
the two elements do not combine. Assume that `b`

allows for multiple
iterations.`val join_by : ``?eq:'key equal ->`

?hash:'key hash ->

('a -> 'key) ->

('b -> 'key) ->

merge:('key -> 'a -> 'b -> 'c option) ->

'a t -> 'b t -> 'c t

`join key1 key2 ~merge`

is a binary operation
that takes two sequences `a`

and `b`

, projects their
elements resp. with `key1`

and `key2`

, and combine
values `(x,y)`

from `(a,b)`

with the same `key`

using `merge`

. If `merge`

returns `None`

, the combination
of values is discarded.`val join_all_by : ``?eq:'key equal ->`

?hash:'key hash ->

('a -> 'key) ->

('b -> 'key) ->

merge:('key -> 'a list -> 'b list -> 'c option) ->

'a t -> 'b t -> 'c t

`join_all_by key1 key2 ~merge`

is a binary operation
that takes two sequences `a`

and `b`

, projects their
elements resp. with `key1`

and `key2`

, and, for each key `k`

occurring in at least one of them:- compute the list
`l1`

of elements of`a`

that map to`k`

- compute the list
`l2`

of elements of`b`

that map to`k`

- call
`merge k l1 l2`

. If`merge`

returns`None`

, the combination of values is discarded, otherwise it returns`Some c`

and`c`

is inserted in the result.

`val group_join_by : ``?eq:'a equal ->`

?hash:'a hash ->

('b -> 'a) -> 'a t -> 'b t -> ('a * 'b list) t

`group_join_by key2`

associates to every element `x`

of
the first sequence, all the elements `y`

of the second
sequence such that `eq x (key y)`

. Elements of the first
sequences without corresponding values in the second one
are mapped to `[]`

`val inter : ``?eq:'a equal ->`

?hash:'a hash -> 'a t -> 'a t -> 'a t

Intersection of two collections. Each element will occur at most once
in the result. Eager.

**Since** 0.10

`val union : ``?eq:'a equal ->`

?hash:'a hash -> 'a t -> 'a t -> 'a t

Union of two collections. Each element will occur at most once
in the result. Eager.

**Since** 0.10

`val diff : ``?eq:'a equal ->`

?hash:'a hash -> 'a t -> 'a t -> 'a t

Set difference. Eager.

**Since** 0.10

`val subset : ``?eq:'a equal ->`

?hash:'a hash -> 'a t -> 'a t -> bool

`subset a b`

returns `true`

if all elements of `a`

belong to `b`

. Eager.`val unfoldr : ``('b -> ('a * 'b) option) -> 'b -> 'a t`

`unfoldr f b`

will apply `f`

to `b`

. If it
yields `Some (x,b')`

then `x`

is returned
and unfoldr recurses with `b'`

.`val scan : ``('b -> 'a -> 'b) -> 'b -> 'a t -> 'b t`

Sequence of intermediate results

`val max : ``?lt:('a -> 'a -> bool) -> 'a t -> 'a option`

Max element of the sequence, using the given comparison function.

**Returns** None if the sequence is empty, Some

`m`

where `m`

is the maximal
element otherwise`val max_exn : ``?lt:('a -> 'a -> bool) -> 'a t -> 'a`

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

Min element of the sequence, using the given comparison function.
see

`Sequence.max`

for more details.`val min_exn : ``?lt:('a -> 'a -> bool) -> 'a t -> 'a`

`val head : ``'a t -> 'a option`

First element, if any, otherwise

**Since** 0.5.1

`None`

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

First element, if any, fails

**Since** 0.5.1

**Raises**

`Invalid_argument`

if the sequence is empty`val take : ``int -> 'a t -> 'a t`

Take at most

`n`

elements from the sequence. Works on infinite
sequences.`val take_while : ``('a -> bool) -> 'a t -> 'a t`

Take elements while they satisfy the predicate, then stops iterating.
Will work on an infinite sequence

`s`

if the predicate is false for at
least one element of `s`

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

Folds over elements of the sequence, stopping early if the accumulator
returns

**Since** 0.5.5

`('a, `Stop)`

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

Drop the

`n`

first elements of the sequence. Lazy.`val drop_while : ``('a -> bool) -> 'a t -> 'a t`

Predicate version of

`Sequence.drop`

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

Reverse the sequence. O(n) memory and time, needs the
sequence to be finite. The result is persistent and does
not depend on the input being repeatable.

`val empty2 : ``('a, 'b) t2`

`val is_empty2 : ``('a, 'b) t2 -> bool`

`val length2 : ``('a, 'b) t2 -> int`

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

`val unzip : ``('a * 'b) t -> ('a, 'b) t2`

`val zip_i : ``'a t -> (int, 'a) t2`

Zip elements of the sequence with their index in the sequence

`val fold2 : ``('c -> 'a -> 'b -> 'c) -> 'c -> ('a, 'b) t2 -> 'c`

`val iter2 : ``('a -> 'b -> unit) -> ('a, 'b) t2 -> unit`

`val map2 : ``('a -> 'b -> 'c) -> ('a, 'b) t2 -> 'c t`

`val map2_2 : ``('a -> 'b -> 'c) ->`

('a -> 'b -> 'd) -> ('a, 'b) t2 -> ('c, 'd) t2

`map2_2 f g seq2`

maps each `x, y`

of seq2 into `f x y, g x y`

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

Convert the sequence into a list. Preserves order of elements.
This function is tail-recursive, but consumes 2*n memory.
If order doesn't matter to you, consider

`Sequence.to_rev_list`

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

Get the list of the reversed sequence (more efficient than

`Sequence.to_list`

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

`val on_list : ``('a t -> 'b t) -> 'a list -> 'b list`

`on_list f l`

is equivalent to `to_list @@ f @@ of_list l`

.`val to_opt : ``'a t -> 'a option`

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

Convert to an array. Currently not very efficient because
an intermediate list is used.

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

`val of_array_i : ``'a array -> (int * 'a) t`

Elements of the array, with their index

`val of_array2 : ``'a array -> (int, 'a) t2`

`val array_slice : ``'a array -> int -> int -> 'a t`

`array_slice a i j`

Sequence of elements whose indexes range
from `i`

to `j`

`val of_opt : ``'a option -> 'a t`

Iterate on 0 or 1 values.

**Since** 0.5.1

`val of_stream : ``'a Stream.t -> 'a t`

Sequence of elements of a stream (usable only once)

`val to_stream : ``'a t -> 'a Stream.t`

Convert to a stream. linear in memory and time (a copy is made in memory)

`val to_stack : ``'a Stack.t -> 'a t -> unit`

Push elements of the sequence on the stack

`val of_stack : ``'a Stack.t -> 'a t`

Sequence of elements of the stack (same order as

`Stack.iter`

)`val to_queue : ``'a Queue.t -> 'a t -> unit`

Push elements of the sequence into the queue

`val of_queue : ``'a Queue.t -> 'a t`

Sequence of elements contained in the queue, FIFO order

`val hashtbl_add : ``('a, 'b) Hashtbl.t -> ('a * 'b) t -> unit`

Add elements of the sequence to the hashtable, with
Hashtbl.add

`val hashtbl_replace : ``('a, 'b) Hashtbl.t -> ('a * 'b) t -> unit`

Add elements of the sequence to the hashtable, with
Hashtbl.replace (erases conflicting bindings)

`val to_hashtbl : ``('a * 'b) t -> ('a, 'b) Hashtbl.t`

Build a hashtable from a sequence of key/value pairs

`val to_hashtbl2 : ``('a, 'b) t2 -> ('a, 'b) Hashtbl.t`

Build a hashtable from a sequence of key/value pairs

`val of_hashtbl : ``('a, 'b) Hashtbl.t -> ('a * 'b) t`

Sequence of key/value pairs from the hashtable

`val of_hashtbl2 : ``('a, 'b) Hashtbl.t -> ('a, 'b) t2`

Sequence of key/value pairs from the hashtable

`val hashtbl_keys : ``('a, 'b) Hashtbl.t -> 'a t`

`val hashtbl_values : ``('a, 'b) Hashtbl.t -> 'b t`

`val of_str : ``string -> char t`

`val to_str : ``char t -> string`

`val concat_str : ``string t -> string`

`exception OneShotSequence`

Raised when the user tries to iterate several times on
a transient iterator

`val of_in_channel : ``Pervasives.in_channel -> char t`

Iterates on characters of the input (can block when one
iterates over the sequence). If you need to iterate
several times on this sequence, use

**Raises**

`Sequence.persistent`

.`OneShotSequence`

when used more than once.`val to_buffer : ``char t -> Buffer.t -> unit`

Copy content of the sequence into the buffer

`val int_range : ``start:int -> stop:int -> int t`

Iterator on integers in

`start...stop`

by steps 1. Also see
`(--)`

for an infix version.`val int_range_dec : ``start:int -> stop:int -> int t`

Iterator on decreasing integers in

`stop...start`

by steps -1.
See `(--^)`

for an infix version`val int_range_by : ``step:int -> int -> int -> int t`

`int_range_by ~step i j`

is the range starting at `i`

, including `j`

,
where the difference between successive elements is `step`

.
use a negative `step`

for a decreasing sequence.`Invalid_argument`

if `step=0`

`val bools : ``bool t`

Iterates on

**Since** 0.7

`true`

and `false`

`val of_set : ``(module Set.S with type elt = 'a and type t = 'b) -> 'b -> 'a t`

Convert the given set to a sequence. The set module must be provided.

`val to_set : ``(module Set.S with type elt = 'a and type t = 'b) -> 'a t -> 'b`

Convert the sequence to a set, given the proper set module

type`'a`

gen =`unit -> 'a option`

type`'a`

klist =`unit -> [ `Cons of 'a * 'a klist | `Nil ]`

`val of_gen : ``'a gen -> 'a t`

Traverse eagerly the generator and build a sequence from it

`val to_gen : ``'a t -> 'a gen`

Make the sequence persistent (O(n)) and then iterate on it. Eager.

`val of_klist : ``'a klist -> 'a t`

Iterate on the lazy list

`val to_klist : ``'a t -> 'a klist`

Make the sequence persistent and then iterate on it. Eager.

module Set:`sig`

..`end`

module Map:`sig`

..`end`

`val random_int : ``int -> int t`

Infinite sequence of random integers between 0 and
the given higher bound (see Random.int)

`val random_bool : ``bool t`

Infinite sequence of random bool values

`val random_float : ``float -> float t`

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

Sequence of choices of an element in the array

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

Infinite sequence of random elements of the list. Basically the
same as

`Sequence.random_array`

.`val shuffle : ``'a t -> 'a t`

`shuffle seq`

returns a perfect shuffle of `seq`

.
Uses O(length seq) memory and time. Eager.`val shuffle_buffer : ``int -> 'a t -> 'a t`

`shuffle_buffer n seq`

returns a sequence of element of `seq`

in random
order. The shuffling is *not* uniform. Uses O(n) memory.
The first `n`

elements of the sequence are consumed immediately. The
rest is consumed lazily.

**Since** 0.7

`val sample : ``int -> 'a t -> 'a array`

`sample n seq`

returns k samples of `seq`

, with uniform probability.
It will consume the sequence and use O(n) memory.
It returns an array of size `min (length seq) n`

.

**Since** 0.7

module Infix:`sig`

..`end`

`include Sequence.Infix`

`val pp_seq : ``?sep:string ->`

(Format.formatter -> 'a -> unit) -> Format.formatter -> 'a t -> unit

Pretty print a sequence of

`'a`

, using the given pretty printer
to print each elements. An optional separator string can be provided.`val pp_buf : ``?sep:string -> (Buffer.t -> 'a -> unit) -> Buffer.t -> 'a t -> unit`

Print into a buffer

`val to_string : ``?sep:string -> ('a -> string) -> 'a t -> string`

Print into a string

Very basic interface to manipulate files as sequence of chunks/lines. The sequences take care of opening and closing files properly; every time one iterates over a sequence, the file is opened/closed again.

Example: copy a file `"a"`

into file `"b"`

, removing blank lines:

```
Sequence.(IO.lines_of "a" |> filter (fun l-> l<> "") |> IO.write_lines "b");;
```

By chunks of `4096`

bytes:

```
Sequence.IO.(chunks_of ~size:4096 "a" |> write_to "b");;
```

Read the lines of a file into a list:

```
Sequence.IO.lines "a" |> Sequence.to_list
```

module IO:`sig`

..`end`