# package containers

Library

Module

Module type

Parameter

Class

Class type

Helpers for the standard **Seq** type

See oseq for a richer API.

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

### Basics

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

#### Constructing sequences

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

#### 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

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

.

`partition p xs`

returns a pair of the subsequence of the elements of `xs`

that satisfy `p`

and the subsequence of the elements of `xs`

that do not satisfy `p`

.

`partition p xs`

is equivalent to `filter p xs, filter (fun x -> not (p x)) xs`

.

Consuming both of the sequences returned by `partition p xs`

causes `xs`

to be consumed twice and causes the function `f`

to be applied twice to each element of the list. Therefore, `f`

should be pure and cheap. Furthermore, `xs`

should be persistent and cheap. If that is not the case, use `partition p (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.

`val nil : 'a t`

`val empty : 'a t`

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

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

`init n f`

corresponds to the sequence `f 0; f 1; ...; f (n-1)`

.

`val repeat : ?n:int -> 'a -> 'a t`

`repeat ~n x`

repeats `x`

`n`

times then stops. If `n`

is omitted, then `x`

is repeated forever.

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

`forever f`

corresponds to the infinite sequence containing all the `f ()`

.

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

`iterate f a`

corresponds to the infinite sequence containing `a`

, `f a`

, `f (f a)`

, ...

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

`unfold f acc`

calls `f acc`

and:

- if
`f acc = Some (x, acc')`

, yield`x`

, continue with`unfold f acc'`

. - if
`f acc = None`

, stops.

`val is_empty : 'a t -> bool`

`is_empty xs`

checks in the sequence `xs`

is empty

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

Head of the list.

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

Fold on values.

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

`fold_lefti f init xs`

applies `f acc i x`

where `acc`

is the result of the previous computation or `init`

for the first one, `i`

is the index in the sequence (starts at 0) and `x`

is the element of the sequence.

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

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

Iterate with index (starts at 0).

`val length : _ t -> int`

Number of elements in the list. Will not terminate if the list if infinite: use (for instance) `take`

to make the list finite if necessary.

Fair product of two (possibly infinite) lists into a new list. Lazy. The first parameter is used to combine each pair of elements.

Alias of `product_with`

.

Specialization of `product_with`

producing tuples.

`group eq l`

groups together consecutive elements that satisfy `eq`

. Lazy. For instance `group (=) [1;1;1;2;2;3;3;1]`

yields `[1;1;1]; [2;2]; [3;3]; [1]`

.

`uniq eq l`

returns `l`

but removes consecutive duplicates. Lazy. In other words, if several values that are equal follow one another, only the first of them is kept.

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

`for_all p [a1; ...; an]`

checks if all elements of the sequence satisfy the predicate `p`

. That is, it returns `(p a1) && ... && (p an)`

for a non-empty list and `true`

if the sequence is empty. It consumes the sequence until it finds an element not satisfying the predicate.

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

`exists p [a1; ...; an]`

checks if at least one element of the sequence satisfies the predicate `p`

. That is, it returns `(p a1) || ... || (p an)`

for a non-empty sequence and `false`

if the list is empty. It consumes the sequence until it finds an element satisfying the predicate.

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

`find p [a1; ...; an]`

return `Some ai`

for the first `ai`

satisfying the predicate `p`

and return `None`

otherwise.

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

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

return `Some (f ai)`

for the first `ai`

such that `f ai = Some _`

and return `None`

otherwise.

`scan f init xs`

is the sequence containing the intermediate result of `fold f init xs`

.

`val range : int -> int -> int t`

`val (--) : int -> int -> int t`

`a -- b`

is the range of integers containing `a`

and `b`

(therefore, never empty).

`val (--^) : int -> int -> int t`

`a -- b`

is the integer range from `a`

to `b`

, where `b`

is excluded.

### Operations on two Collections

Fold on two collections at once. Stop as soon as one of them ends.

Map on two collections at once. Stop as soon as one of the arguments is exhausted.

Iterate on two collections at once. Stop as soon as one of them ends.

Combine elements pairwise. Stop as soon as one of the lists stops.

### Misc

Eager sort. Require the iterator to be finite. `O(n ln(n))`

time and space.

Eager sort that removes duplicate values. Require the iterator to be finite. `O(n ln(n))`

time and space.

### Fair Combinations

### Implementations

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

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

Infix version of `fair_flat_map`

.

### Infix operators

`module Infix : sig ... end`

`module type MONAD = sig ... end`

### Conversions

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

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

Gather all values into a list.

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

Iterate on the array.

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

Convert into array.

`val of_string : string -> char t`

Iterate on characters.

### IO

```
val pp :
?pp_start:unit printer ->
?pp_stop:unit printer ->
?pp_sep:unit printer ->
'a printer ->
'a t printer
```

`pp ~pp_start ~pp_stop ~pp_sep pp_item ppf s`

formats the sequence `s`

on `ppf`

. Each element is formatted with `pp_item`

, `pp_start`

is called at the beginning, `pp_stop`

is called at the end, `pp_sep`

is called between each elements. By defaults `pp_start`

and `pp_stop`

does nothing and `pp_sep`

defaults to (fun out -> Format.fprintf out ",@ ").