Library

Module

Module type

Parameter

Class

Class type

sectionYPositions = computeSectionYPositions($el), 10)" x-init="setTimeout(() => sectionYPositions = computeSectionYPositions($el), 10)">

On This Page

Legend:

Library

Module

Module type

Parameter

Class

Class type

Library

Module

Module type

Parameter

Class

Class type

Simple and Efficient Iterators.

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 an iterator can be iterated on as many times as needed; this choice allows for high performance of many combinators. However, for transient iterators, the `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 iterators (e.g. `group`

). The transformation is computed on the fly every time one iterates over the resulting iterator. If a transformation performs heavy computation, `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 `map`

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

If an iterator 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 `t`

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

, the `persistent`

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

An iterator of values of type `'a`

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

it will be applied to every element of the iterator successively.

`type +'a iter = 'a t`

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

Build an iterator from a iter function

`val from_labelled_iter : (f:('a -> unit) -> unit) -> 'a t`

Build an iterator from a labelled iter function

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

Call the function repeatedly until it returns None. This iterator is transient, use `persistent`

if needed!

`val empty : 'a t`

Empty iterator. It contains no element.

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

Singleton iterator, with exactly one element.

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

Iterator with exactly two elements

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

`init f`

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

.

`cons x l`

yields `x`

, then yields from `l`

. Same as `append (singleton x) l`

.

Caution: it is advised not to build long iterators out of `cons`

, because it's inefficient. Each additional `cons x i`

adds one layer of function call per item traversed in `i`

.

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

Infinite iterator of the same element. You may want to look at `take`

and the likes if you iterate on it.

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

`iterate f x`

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

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

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

and `persistent`

.

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

not to loop forever.

`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 iter : ('a -> unit) -> 'a t -> unit`

Consume the iterator, 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 iterator

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

Consume the iterator, passing all its arguments to the function. `for_each seq f`

is the same as `iter f seq`

, i.e., `iter`

with arguments reversed.

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

Iterate on elements and their index in the iterator. `for_eachi seq f`

is the same as `iteri f seq`

, i.e., `iteri`

with arguments reversed.

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

Fold over elements of the iterator, consuming it

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

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

`fold_filter_map f acc l`

is a `fold_map`

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

.

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

`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 iterator?

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

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

`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 length : 'a t -> int`

How long is the iterator? Forces the iterator.

`val is_empty : 'a t -> bool`

Is the iterator empty? Forces the iterator.

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

Append iterators. Iterating on the result is like iterating on the each iterator of the list in order.

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

. Formerly `flatMap`

`seq_list l`

returns all the ways to pick one element in each sub-iterator in `l`

. Assumes the sub-iterators can be iterated on several times.

`seq_list_map f l`

maps `f`

over every element of `l`

, then calls `seq_list`

Map with indices, and only keep non-`None`

elements

`val filter_count : ('a -> bool) -> 'a t -> int`

Count how many elements satisfy the given predicate

`filter_some l`

retains only elements of the form `Some x`

. Same as `filter_map (fun x->x)`

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

Lazy version of `persistent`

. When calling `persistent_lazy s`

, a new iterator `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 (`take`

, etc.) then `s'`

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

will traverse `s`

again.

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

Sort the iterator and remove duplicates. Eager, same as `sort`

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

Checks whether the iterator is sorted. Eager, same as `sort`

.

Group equal consecutive elements. Linear time. Formerly synonym to `group`

. **note**: Order of items in each list is unspecified.

Group equal elements, disregarding their order of appearance. precondition: for any `x`

and `y`

, if `eq x y`

then `hash x=hash y`

must hold. **note**: Order of items in each list is unspecified.

Map each distinct element to its number of occurrences in the whole seq. Similar to `group_by seq |> map (fun l->List.hd l, List.length l)`

precondition: for any `x`

and `y`

, if `eq x y`

then `hash x=hash y`

must hold.

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

.

Cartesian product of iterators. When calling `product a b`

, the caller **MUST** ensure that `b`

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

on it beforehand.

`val diagonal_l : 'a list -> ('a * 'a) t`

All pairs of distinct positions of the list. `diagonal l`

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

if `i < j`

.

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

`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 iterators `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. precondition: for any `x`

and `y`

, if `eq x y`

then `hash x=hash y`

must hold.

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

`group_join_by key2`

associates to every element `x`

of the first iterator, all the elements `y`

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

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

precondition: for any `x`

and `y`

, if `eq x y`

then `hash x=hash y`

must hold.

Intersection of two collections. Each element will occur at most once in the result. Eager. precondition: for any `x`

and `y`

, if `eq x y`

then `hash x=hash y`

must hold.

Union of two collections. Each element will occur at most once in the result. Eager. precondition: for any `x`

and `y`

, if `eq x y`

then `hash x=hash y`

must hold.

`subset a b`

returns `true`

if all elements of `a`

belong to `b`

. Eager. precondition: for any `x`

and `y`

, if `eq x y`

then `hash x=hash y`

must hold.

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

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

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

Min element of the iterator, using the given comparison function. see `max`

for more details.

`val sum : int t -> int`

Sum of elements

`val sumf : float t -> float`

Sum of elements, using Kahan summation

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

First element, if any, otherwise `None`

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

First element, if any, fails

Take at most `n`

elements from the iterator. Works on infinite iterators.

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

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

.

Maps over elements of the iterator, stopping early if the mapped function returns ``Stop`

or ``Return x`

. At each iteration:

- If
`f`

returns``Yield y`

,`y`

is added to the sequence and the iteration continues. - If
`f`

returns``Stop`

, nothing is added to the sequence and the iteration stops. - If
`f`

returns``Return y`

,`y`

is added to the sequence and the iteration stops.

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

Folds over elements of the iterator, stopping early if the accumulator returns `('a, `Stop)`

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

`val fold2 : ('c -> 'a -> 'b -> 'c) -> 'c -> ('a * 'b) t -> 'c`

`val iter2 : ('a -> 'b -> unit) -> ('a * 'b) t -> unit`

`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 iterator 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 `to_rev_list`

.

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

Get the list of the reversed iterator (more efficient than `to_list`

)

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

`on_list f l`

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

.

`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 array_slice : 'a array -> int -> int -> 'a t`

`array_slice a i j`

Iterator of elements whose indexes range from `i`

to `j`

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

Iterate on 0 or 1 values.

Convert to a `Seq`

. Linear in memory and time (a copy is made in memory). This does not work on infinite iterators.

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

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

Build a hashtable from an iterator of key/value pairs

`val of_str : string -> char t`

`val to_str : char t -> string`

`val concat_str : string t -> string`

Concatenate strings together, eagerly. Also see `intersperse`

to add a separator.

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

`val of_in_channel : in_channel -> char t`

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

.

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

`val bools : bool t`

Iterates on `true`

and `false`

Convert the given set to an iterator. The set module must be provided.

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

One shot iterator using this generator. It must not be traversed twice.

`module Set : sig ... end`

`module Map : sig ... end`

`val random_int : int -> int t`

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

`val random_bool : bool t`

Infinite iterator of random bool values

`val random_float : float -> float t`

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

Iterator of choices of an element in the array

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

Infinite iterator of random elements of the list. Basically the same as `random_array`

.

`shuffle seq`

returns a perfect shuffle of `seq`

. Uses O(length seq) memory and time. Eager.

`shuffle_buffer n seq`

returns an iterator of element of `seq`

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

The first `n`

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

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

`sample n seq`

returns k samples of `seq`

, with uniform probability. It will consume the iterator and use O(n) memory.

It returns an array of size `min (length seq) n`

.

Random iterators use `Random.int`

, `Random.float`

, `Random.bool`

, etc., under the hood, so they will respect seeding of the random generator in the usual way. I.e., if you do not initialize the random generator with one of `Random.init`

, `Random.full_init`

, or `Random.self_init`

before calling these functions, they will yield the same values across seperate invocations of your program.

Example:

```
(* Ensure a fresh random seed each time the program is executed. *)
let () = Random.self_init ()
(* Generate random values. *)
let l = Iter.random_int 1000 |> Iter.take 3 |> Iter.to_list
```

`module Infix : sig ... end`

`include module type of Infix`

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

`a -- b`

is the range of integers from `a`

to `b`

, both included, in increasing order. It will therefore be empty if `a > b`

.

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

`a --^ b`

is the range of integers from `b`

to `a`

, both included, in decreasing order (starts from `a`

). It will therefore be empty if `a < b`

.

```
val pp_seq :
?sep:string ->
(Format.formatter -> 'a -> unit) ->
Format.formatter ->
'a t ->
unit
```

Pretty print an iterator of `'a`

, using the given pretty printer to print each elements. An optional separator string can be provided.

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

Print into a string

`module IO : sig ... end`

Basic IO

On This Page