Legend:
Library
Module
Module type
Parameter
Class
Class type
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.

and +'a node =
| Nil
| Cons of 'a * 'a t

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.

val is_empty : 'a t -> bool

is_empty xs determines whether the sequence xs is empty.

It is recommended that the sequence xs be persistent. Indeed, is_empty xs demands the head of the sequence xs, so, if xs is ephemeral, it may be the case that xs cannot be used any more after this call has taken place.

  • since 4.14
val uncons : 'a t -> ('a * 'a t) option

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.

  • since 4.14
val length : 'a t -> int

length xs is the length of the sequence xs.

The sequence xs must be finite.

  • since 4.14
val iter : ( 'a -> unit ) -> 'a t -> unit

iter f xs invokes f x successively for every element x of the sequence xs, from left to right.

It terminates only if the sequence xs is finite.

val fold_left : ( 'a -> 'b -> 'a ) -> 'a -> 'b t -> 'a

fold_left f _ xs invokes f _ x successively for every element x of the sequence xs, from left to right.

An accumulator of type 'a is threaded through the calls to f.

It terminates only if the sequence xs is finite.

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

iteri f xs invokes f i x successively for every element x located at index i in the sequence xs.

It terminates only if the sequence xs is finite.

iteri f xs is equivalent to iter (fun (i, x) -> f i x) (zip (ints 0) xs).

  • since 4.14
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).

  • since 4.14
val for_all : ( 'a -> bool ) -> 'a t -> bool

for_all p xs determines whether all elements x of the sequence xs satisfy p x.

The sequence xs must be finite.

  • since 4.14
val exists : ( 'a -> bool ) -> 'a t -> bool

exists xs p determines whether at least one element x of the sequence xs satisfies p x.

The sequence xs must be finite.

  • since 4.14
val find : ( 'a -> bool ) -> 'a t -> 'a option

find p xs returns Some x, where x is the first element of the sequence xs that satisfies p x, if there is such an element.

It returns None if there is no such element.

The sequence xs must be finite.

  • since 4.14
val find_map : ( 'a -> 'b option ) -> 'a t -> 'b option

find_map f xs returns Some y, where x is the first element of the sequence xs such that f x = Some _, if there is such an element, and where y is defined by f x = Some y.

It returns None if there is no such element.

The sequence xs must be finite.

  • since 4.14
val iter2 : ( 'a -> 'b -> unit ) -> 'a t -> 'b t -> unit

iter2 f xs ys invokes f x y successively for every pair (x, y) of elements drawn synchronously from the sequences xs and ys.

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.

iter2 f xs ys is equivalent to iter (fun (x, y) -> f x y) (zip xs ys).

  • since 4.14
val fold_left2 : ( 'a -> 'b -> 'c -> 'a ) -> 'a -> 'b t -> 'c t -> 'a

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

  • since 4.14
val for_all2 : ( 'a -> 'b -> bool ) -> 'a t -> 'b t -> bool

for_all2 p xs ys determines whether all pairs (x, y) of elements drawn synchronously from the sequences xs and ys satisfy p x y.

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. In particular, if xs or ys is empty, then for_all2 p xs ys is true. This is where for_all2 and equal differ: equal eq xs ys can be true only if xs and ys have the same length.

At least one of the sequences xs and ys must be finite.

for_all2 p xs ys is equivalent to for_all (fun b -> b) (map2 p xs ys).

  • since 4.14
val exists2 : ( 'a -> 'b -> bool ) -> 'a t -> 'b t -> bool

exists2 p xs ys determines whether some pair (x, y) of elements drawn synchronously from the sequences xs and ys satisfies p x y.

If the sequences xs and ys have different lengths, then iteration must stop as soon as one sequence is exhausted; the excess elements in the other sequence are ignored.

At least one of the sequences xs and ys must be finite.

exists2 p xs ys is equivalent to exists (fun b -> b) (map2 p xs ys).

  • since 4.14
val equal : ( 'a -> 'b -> bool ) -> 'a t -> 'b t -> bool

Provided the function eq defines an equality on elements, equal eq xs ys determines whether the sequences xs and ys are pointwise equal.

At least one of the sequences xs and ys must be finite.

  • since 4.14
val compare : ( 'a -> 'b -> int ) -> 'a t -> 'b t -> int

Provided the function cmp defines a preorder on elements, compare cmp xs ys compares the sequences xs and ys according to the lexicographic preorder.

For more details on comparison functions, see Array.sort.

At least one of the sequences xs and ys must be finite.

  • since 4.14

Constructing sequences

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

val empty : 'a t

empty is the empty sequence. It has no elements. Its length is 0.

val return : 'a -> 'a t

return x is the sequence whose sole element is x. Its length is 1.

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

cons x xs is the sequence that begins with the element x, followed with the sequence xs.

Writing cons (f()) xs causes the function call f() to take place immediately. For this call to be delayed until the sequence is queried, one must instead write (fun () -> Cons(f(), xs)).

  • since 4.11
val init : int -> ( int -> 'a ) -> 'a t

init n f is the sequence f 0; f 1; ...; f (n-1).

n must be nonnegative.

If desired, the infinite sequence f 0; f 1; ... can be defined as map f (ints 0).

  • raises Invalid_argument

    if n is negative.

  • since 4.14
val unfold : ( 'b -> ('a * 'b) option ) -> 'b -> 'a t

unfold constructs a sequence out of a step function and an initial state.

If f u is None then unfold f u is the empty sequence. If f u is Some (x, u') then unfold f u is the nonempty sequence cons x (unfold f u').

For example, unfold (function [] -> None | h :: t -> Some (h, t)) l is equivalent to List.to_seq l.

  • since 4.11
val repeat : 'a -> 'a t

repeat x is the infinite sequence where the element x is repeated indefinitely.

repeat x is equivalent to cycle (return x).

  • since 4.14
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 ()).

  • since 4.14
val cycle : 'a t -> 'a t

cycle xs is the infinite sequence that consists of an infinite number of repetitions of the sequence xs.

If xs is an empty sequence, then cycle xs is empty as well.

Consuming (a prefix of) the sequence cycle xs once can cause the sequence xs to be consumed more than once. Therefore, xs must be persistent.

  • since 4.14
val iterate : ( 'a -> 'a ) -> 'a -> 'a t

iterate f x is the infinite sequence whose elements are x, f x, f (f x), and so on.

In other words, it is the orbit of the function f, starting at x.

  • since 4.14

Transforming sequences

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

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

map f xs is the image of the sequence xs through the transformation f.

If xs is the sequence x0; x1; ... then map f xs is the sequence f x0; f x1; ....

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

mapi is analogous to map, but applies the function f to an index and an element.

mapi f xs is equivalent to map2 f (ints 0) xs.

  • since 4.14
val filter : ( 'a -> bool ) -> 'a t -> 'a t

filter p xs is the sequence of the elements x of xs that satisfy p x.

In other words, filter p xs is the sequence xs, deprived of the elements x such that p x is false.

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

filter_map f xs is the sequence of the elements y such that f x = Some y, where x ranges over xs.

filter_map f xs is equivalent to map Option.get (filter Option.is_some (map f xs)).

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

If xs is a sequence [x0; x1; x2; ...], then scan f a0 xs is a sequence of accumulators [a0; a1; a2; ...] where a1 is f a0 x0, a2 is f a1 x1, and so on.

Thus, scan f a0 xs is conceptually related to fold_left f a0 xs. However, instead of performing an eager iteration and immediately returning the final accumulator, it returns a sequence of accumulators.

For instance, scan (+) 0 transforms a sequence of integers into the sequence of its partial sums.

If xs has length n then scan f a0 xs has length n+1.

  • since 4.14
val take : int -> 'a t -> 'a t

take n xs is the sequence of the first n elements of xs.

If xs has fewer than n elements, then take n xs is equivalent to xs.

n must be nonnegative.

  • raises Invalid_argument

    if n is negative.

  • since 4.14
val drop : int -> 'a t -> 'a t

drop n xs is the sequence