Module Seq
: sigend
Sequences.
A sequence of type 'aSeq.t can be thought of as a delayed list, that is, a list whose elements are
computed only when they are demanded by a consumer. This allows sequences to be produced and transformed
lazily (one element at a time) rather than eagerly (all elements at once). This also allows constructing
conceptually infinite sequences.
The type 'aSeq.t is defined as a synonym for unit->'aSeq.node . This is a function type: therefore,
it is opaque. The consumer can query a sequence in order to request the next element (if there is
one), but cannot otherwise inspect the sequence in any way.
Because it is opaque, the type 'aSeq.t does not reveal whether a sequence is:
-persistent, which means that the sequence can be used as many times as desired, producing the same
elements every time, just like an immutable list; or
-ephemeral, which means that the sequence is not persistent. Querying an ephemeral sequence might have
an observable side effect, such as incrementing a mutable counter. As a common special case, an
ephemeral sequence can be affine, which means that it must be queried at most once.
It also does not reveal whether the elements of the sequence are:
-pre-computed and stored in memory, which means that querying the sequence is cheap;
-computed when first demanded and then stored in memory, which means that querying the sequence once can
be expensive, but querying the same sequence again is cheap; or
-re-computed every time they are demanded, which may or may not be cheap.
It is up to the programmer to keep these distinctions in mind so as to understand the time and space
requirements of sequences.
For the sake of simplicity, most of the documentation that follows is written under the implicit
assumption that the sequences at hand are persistent. We normally do not point out when or how many
times each function is invoked, because that would be too verbose. For instance, in the description of
map , we write: "if xs is the sequence x0;x1;... then mapfxs is the sequence fx0;fx1;... ". If
we wished to be more explicit, we could point out that the transformation takes place on demand: that is,
the elements of mapfxs are computed only when they are demanded. In other words, the definition letys=mapfxs terminates immediately and does not invoke f . The function call fx0 takes place only when
the first element of ys is demanded, via the function call ys() . Furthermore, calling ys() twice causes
fx0 to be called twice as well. If one wishes for f to be applied at most once to each element of xs ,
even in scenarios where ys is queried more than once, then one should use letys=memoize(mapfxs) .
As a general rule, the functions that build sequences, such as map , filter , scan , take , etc., produce
sequences whose elements are computed only on demand. The functions that eagerly consume sequences, such
as is_empty , find , length , iter , fold_left , etc., are the functions that force computation to take
place.
When possible, we recommend using sequences rather than dispensers (functions of type unit->'aoption
that produce elements upon demand). Whereas sequences can be persistent or ephemeral, dispensers are
always ephemeral, and are typically more difficult to work with than sequences. Two conversion functions,
Seq.to_dispenser and Seq.of_dispenser , are provided.
Since 4.07
type'at = unit->'anode
A sequence xs of type 'at 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.
type'anode =
| Nil
| Cons of'a*'at
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.
Consumingsequences
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.
valis_empty : 'at->boolis_emptyxs determines whether the sequence xs is empty.
It is recommended that the sequence xs be persistent. Indeed, is_emptyxs 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
valuncons : 'at->('a*'at)option
If xs is empty, then unconsxs is None .
If xs is nonempty, then unconsxs is Some(x,ys) where x is the head of the sequence and ys its tail.
Since 4.14
vallength : 'at->intlengthxs is the length of the sequence xs .
The sequence xs must be finite.
Since 4.14
valiter : ('a->unit)->'at->unititerfxs invokes fx successively for every element x of the sequence xs , from left to right.
It terminates only if the sequence xs is finite.
valfold_left : ('acc->'a->'acc)->'acc->'at->'accfold_leftf_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.
valiteri : (int->'a->unit)->'at->unititerifxs invokes fix successively for every element x located at index i in the sequence xs .
It terminates only if the sequence xs is finite.
iterifxs is equivalent to iter(fun(i,x)->fix)(zip(ints0)xs) .
Since 4.14
valfold_lefti : ('acc->int->'a->'acc)->'acc->'at->'accfold_leftif_xs invokes f_ix 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_leftifaccuxs is equivalent to fold_left(funaccu(i,x)->faccuix)accu(zip(ints0)xs) .
Since 4.14
valfor_all : ('a->bool)->'at->boolfor_allpxs determines whether all elements x of the sequence xs satisfy px .
The sequence xs must be finite.
Since 4.14
valexists : ('a->bool)->'at->boolexistsxsp determines whether at least one element x of the sequence xs satisfies px .
The sequence xs must be finite.
Since 4.14
valfind : ('a->bool)->'at->'aoptionfindpxs returns Somex , where x is the first element of the sequence xs that satisfies px , if there
is such an element.
It returns None if there is no such element.
The sequence xs must be finite.
Since 4.14
valfind_index : ('a->bool)->'at->intoptionfind_indexpxs returns Somei , where i is the index of the first element of the sequence xs that
satisfies px , if there is such an element.
It returns None if there is no such element.
The sequence xs must be finite.
Since 5.1
valfind_map : ('a->'boption)->'at->'boptionfind_mapfxs returns Somey , where x is the first element of the sequence xs such that fx=Some_ ,
if there is such an element, and where y is defined by fx=Somey .
It returns None if there is no such element.
The sequence xs must be finite.
Since 4.14
valfind_mapi : (int->'a->'boption)->'at->'boption
Same as find_map , but the predicate is applied to the index of the element as first argument (counting
from 0), and the element itself as second argument.
The sequence xs must be finite.
Since 5.1
valiter2 : ('a->'b->unit)->'at->'bt->unititer2fxsys invokes fxy 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.
iter2fxsys is equivalent to iter(fun(x,y)->fxy)(zipxsys) .
Since 4.14
valfold_left2 : ('acc->'a->'b->'acc)->'acc->'at->'bt->'accfold_left2f_xsys invokes f_xy 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_left2faccuxsys is equivalent to fold_left(funaccu(x,y)->faccuxy)(zipxsys) .
Since 4.14
valfor_all2 : ('a->'b->bool)->'at->'bt->boolfor_all2pxsys determines whether all pairs (x,y) of elements drawn synchronously from the sequences
xs and ys satisfy pxy .
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_all2pxsys is true. This is where for_all2 and equal differ: equaleqxsys 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_all2pxsys is equivalent to for_all(funb->b)(map2pxsys) .
Since 4.14
valexists2 : ('a->'b->bool)->'at->'bt->boolexists2pxsys determines whether some pair (x,y) of elements drawn synchronously from the sequences xs
and ys satisfies pxy .
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.
exists2pxsys is equivalent to exists(funb->b)(map2pxsys) .
Since 4.14
valequal : ('a->'b->bool)->'at->'bt->bool
Provided the function eq defines an equality on elements, equaleqxsys 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
valcompare : ('a->'b->int)->'at->'bt->int
Provided the function cmp defines a preorder on elements, comparecmpxsys 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
Constructingsequences
The functions in this section are lazy: that is, they return sequences whose elements are computed only
when demanded.
valempty : 'atempty is the empty sequence. It has no elements. Its length is 0.
valreturn : 'a->'atreturnx is the sequence whose sole element is x . Its length is 1.
valcons : 'a->'at->'atconsxxs 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
valinit : int->(int->'a)->'atinitnf is the sequence f0;f1;...;f(n-1) .
n must be nonnegative.
If desired, the infinite sequence f0;f1;... can be defined as mapf(ints0) .
Since 4.14
RaisesInvalid_argument if n is negative.
valunfold : ('b->('a*'b)option)->'b->'atunfold constructs a sequence out of a step function and an initial state.
If fu is None then unfoldfu is the empty sequence. If fu is Some(x,u') then unfoldfu is the
nonempty sequence consx(unfoldfu') .
For example, unfold(function[]->None|h::t->Some(h,t))l is equivalent to List.to_seql .
Since 4.11
valrepeat : 'a->'atrepeatx is the infinite sequence where the element x is repeated indefinitely.
repeatx is equivalent to cycle(returnx) .
Since 4.14
valforever : (unit->'a)->'atforeverf is an infinite sequence where every element is produced (on demand) by the function call f() .
For instance, foreverRandom.bool is an infinite sequence of random bits.
foreverf is equivalent to mapf(repeat()) .
Since 4.14
valcycle : 'at->'atcyclexs is the infinite sequence that consists of an infinite number of repetitions of the sequence xs .
If xs is an empty sequence, then cyclexs is empty as well.
Consuming (a prefix of) the sequence cyclexs once can cause the sequence xs to be consumed more than
once. Therefore, xs must be persistent.
Since 4.14
valiterate : ('a->'a)->'a->'atiteratefx is the infinite sequence whose elements are x , fx , f(fx) , and so on.
In other words, it is the orbit of the function f , starting at x .
Since 4.14
Transformingsequences
The functions in this section are lazy: that is, they return sequences whose elements are computed only
when demanded.
valmap : ('a->'b)->'at->'btmapfxs is the image of the sequence xs through the transformation f .
If xs is the sequence x0;x1;... then mapfxs is the sequence fx0;fx1;... .
valmapi : (int->'a->'b)->'at->'btmapi is analogous to map , but applies the function f to an index and an element.
mapifxs is equivalent to map2f(ints0)xs .
Since 4.14
valfilter : ('a->bool)->'at->'atfilterpxs is the sequence of the elements x of xs that satisfy px .
In other words, filterpxs is the sequence xs , deprived of the elements x such that px is false.
valfilter_map : ('a->'boption)->'at->'btfilter_mapfxs is the sequence of the elements y such that fx=Somey , where x ranges over xs .
filter_mapfxs is equivalent to mapOption.get(filterOption.is_some(mapfxs)) .
valscan : ('b->'a->'b)->'b->'at->'bt
If xs is a sequence [x0;x1;x2;...] , then scanfa0xs is a sequence of accumulators [a0;a1;a2;...] where a1 is fa0x0 , a2 is fa1x1 , and so on.
Thus, scanfa0xs is conceptually related to fold_leftfa0xs . 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 scanfa0xs has length n+1 .
Since 4.14
valtake : int->'at->'attakenxs is the sequence of the first n elements of xs .
If xs has fewer than n elements, then takenxs is equivalent to xs .
n must be nonnegative.
Since 4.14
RaisesInvalid_argument if n is negative.
valdrop : int->'at->'atdropnxs is the sequence xs , deprived of its first n elements.
If xs has fewer than n elements, then dropnxs is empty.
n must be nonnegative.
drop is lazy: the first n+1 elements of the sequence xs are demanded only when the first element of dropnxs is demanded.
Since 4.14
RaisesInvalid_argument if n is negative.
valtake_while : ('a->bool)->'at->'attake_whilepxs is the longest prefix of the sequence xs where every element x satisfies px .
Since 4.14
valdrop_while : ('a->bool)->'at->'atdrop_whilepxs is the sequence xs , deprived of the prefix take_whilepxs .
Since 4.14
valgroup : ('a->'a->bool)->'at->'att
Provided the function eq defines an equality on elements, groupeqxs is the sequence of the maximal runs
of adjacent duplicate elements of the sequence xs .
Every element of groupeqxs is a nonempty sequence of equal elements.
The concatenation concat(groupeqxs) is equal to xs .
Consuming groupeqxs , and consuming the sequences that it contains, can cause xs to be consumed more
than once. Therefore, xs must be persistent.
Since 4.14
valmemoize : 'at->'at
The sequence memoizexs has the same elements as the sequence xs .
Regardless of whether xs is ephemeral or persistent, memoizexs is persistent: even if it is queried
several times, xs is queried at most once.
The construction of the sequence memoizexs internally relies on suspensions provided by the module Lazy
. These suspensions are not thread-safe. Therefore, the sequence memoizexs must not be queried by
multiple threads concurrently.
Since 4.14
exceptionForced_twice
This exception is raised when a sequence returned by Seq.once (or a suffix of it) is queried more than
once.
Since 4.14
valonce : 'at->'at
The sequence oncexs has the same elements as the sequence xs .
Regardless of whether xs is ephemeral or persistent, oncexs 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.
Since 4.14
RaisesForced_twice if oncexs , or a suffix of it, is queried more than once.
valtranspose : 'att->'att
If xss is a matrix (a sequence of rows), then transposexss 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.
Since 4.14
Combiningsequencesvalappend : 'at->'at->'atappendxsys is the concatenation of the sequences xs and ys .
Its elements are the elements of xs , followed by the elements of ys .
Since 4.11
valconcat : 'att->'at
If xss is a sequence of sequences, then concatxss is its concatenation.
If xss is the sequence xs0;xs1;... then concatxss is the sequence xs0@xs1@... .
Since 4.13
valflat_map : ('a->'bt)->'at->'btflat_mapfxs is equivalent to concat(mapfxs) .
valconcat_map : ('a->'bt)->'at->'btconcat_mapfxs is equivalent to concat(mapfxs) .
concat_map is an alias for flat_map .
Since 4.13
valzip : 'at->'bt->('a*'b)tzipxsys is the sequence of pairs (x,y) drawn synchronously from the sequences xs and ys .
If the sequences xs and ys have different lengths, then the sequence ends as soon as one sequence is
exhausted; the excess elements in the other sequence are ignored.
zipxsys is equivalent to map2(funab->(a,b))xsys .
Since 4.14
valmap2 : ('a->'b->'c)->'at->'bt->'ctmap2fxsys is the sequence of the elements fxy , where the pairs (x,y) are drawn synchronously from
the sequences xs and ys .
If the sequences xs and ys have different lengths, then the sequence ends as soon as one sequence is
exhausted; the excess elements in the other sequence are ignored.
map2fxsys is equivalent to map(fun(x,y)->fxy)(zipxsys) .
Since 4.14
valinterleave : 'at->'at->'atinterleavexsys is the sequence that begins with the first element of xs , continues with the first
element of ys , and so on.
When one of the sequences xs and ys is exhausted, interleavexsys continues with the rest of the other
sequence.
Since 4.14
valsorted_merge : ('a->'a->int)->'at->'at->'at
If the sequences xs and ys are sorted according to the total preorder cmp , then sorted_mergecmpxsys
is the sorted sequence obtained by merging the sequences xs and ys .
For more details on comparison functions, see Array.sort .
Since 4.14
valproduct : 'at->'bt->('a*'b)tproductxsys is the Cartesian product of the sequences xs and ys .
For every element x of xs and for every element y of ys , the pair (x,y) appears once as an element of
productxsys .
The order in which the pairs appear is unspecified.
The sequences xs and ys are not required to be finite.
The sequences xs and ys must be persistent.
Since 4.14
valmap_product : ('a->'b->'c)->'at->'bt->'ct
The sequence map_productfxsys 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 fxy appears once as an element of
map_productfxsys .
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_productfxsys is equivalent to map(fun(x,y)->fxy)(productxsys) .
Since 4.14
Splittingasequenceintotwosequencesvalunzip : ('a*'b)t->'at*'btunzip transforms a sequence of pairs into a pair of sequences.
unzipxs is equivalent to (mapfstxs,mapsndxs) .
Querying either of the sequences returned by unzipxs 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 unzip(memoizexs) .
Since 4.14
valsplit : ('a*'b)t->'at*'btsplit is an alias for unzip .
Since 4.14
valpartition_map : ('a->('b,'c)Either.t)->'at->'bt*'ctpartition_mapfxs returns a pair of sequences (ys,zs) , where:
- ys is the sequence of the elements y such that fx=Lefty , where x ranges over xs ;
- zs is the sequence of the elements z such that fx=Rightz , where x ranges over xs .
partition_mapfxs is equivalent to a pair of filter_mapEither.find_left(mapfxs) and filter_mapEither.find_right(mapfxs) .
Querying either of the sequences returned by partition_mapfxs 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_mapf(memoizexs) .
Since 4.14
valpartition : ('a->bool)->'at->'at*'atpartitionpxs 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 .
partitionpxs is equivalent to filterpxs,filter(funx->not(px))xs .
Consuming both of the sequences returned by partitionpxs 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 partitionp(memoizexs) .
Since 4.14
Convertingbetweensequencesanddispensers
A dispenser is a representation of a sequence as a function of type unit->'aoption . 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.
valof_dispenser : (unit->'aoption)->'atof_dispenserit 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_dispenserit) .
Since 4.14
valto_dispenser : 'at->unit->'aoptionto_dispenserxs 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.
Since 4.14
Sequencesofintegersvalints : int->inttintsi is the infinite sequence of the integers beginning at i and counting up.
Since 4.14
OCamldoc 2025-06-12 Seq(3o)
Install Now
PNG Icons
