Legend:
Library
Module
Module type
Parameter
Class
Class type
Sequence of elements
A sequence represents a collection of elements, for which you never construct the complete representation.
Basically you should use a sequence when you would prefer using a list or a lazy-list but constructing the whole list explicitly would explode your memory.
All functions returning a sequence operates in time and space O(1).
Note that if you want a ``consumable sequence'', you should prefer using enumerations (from module BatEnum).
Build a sequence from a step function and an initial value. unfold f u returns empty if f u returns None, or fun () -> Cons (x, unfold f y) if f u returns Some (x, y).
For example, unfold (function [] -> None | h::t -> Some (h,t)) l is equivalent to List.to_seq l.
Map each element to a subsequence, then return each element of this sub-sequence in turn. This transformation is lazy, it only applies when the result is traversed.
Most functions in the following sections have a shortcut semantic similar to the behavior of the usual (&&) and (||) operators : they will force the sequence until they find an satisfying element, and then return immediately.
For example, for_all will only diverge if the sequence begins with an infinite number of true elements --- elements for which the predicate p returns true.
filter p s returns the sequence of elements of s satisfying p. Lazy.
Note filter is lazy in that it returns a lazy sequence, but each element in the result is eagerly searched in the input sequence. Therefore, the access to a given element in the result will diverge if it is preceded, in the input sequence, by infinitely many false elements (elements on which the predicate p returns false).
Other functions that may drop an unbound number of elements (filter_map, take_while, etc.) have the same behavior.
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.
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.
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.
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->'bt->'ct->'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).
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).
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_stdlib : ('a->'b-> bool)->'at->'bt-> 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.
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.
drop n xs is the sequence xs, deprived of its first n elements.
If xs has fewer than n elements, then drop n xs 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 drop n xs is demanded. For this reason, drop 1 xs is not equivalent to tail xs, which queries xs immediately.
Provided the function eq defines an equality on elements, group eq xs is the sequence of the maximal runs of adjacent duplicate elements of the sequence xs.
Every element of group eq xs is a nonempty sequence of equal elements.
The concatenation concat (group eq xs) is equal to xs.
Consuming group eq xs, and consuming the sequences that it contains, can cause xs to be consumed more than once. Therefore, xs must be persistent.
The sequence memoize xs has the same elements as the sequence xs.
Regardless of whether xs is ephemeral or persistent, memoize xs is persistent: even if it is queried several times, xs is queried at most once.
The construction of the sequence memoize xs internally relies on suspensions provided by the module Lazy. These suspensions are not thread-safe. Therefore, the sequence memoize xs must not be queried by multiple threads concurrently.
since 4.14
exceptionForced_twice
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.
zip xs ys 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.
zip xs ys is equivalent to map2 (fun a b -> (a, b)) xs ys.
map2 f xs ys is the sequence of the elements f x y, 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.
map2 f xs ys is equivalent to map (fun (x, y) -> f x y) (zip xs ys).
If the sequences xs and ys are sorted according to the total preorder cmp, then sorted_merge cmp xs ys is the sorted sequence obtained by merging the sequences xs and ys.
For more details on comparison functions, see Array.sort.
unzip transforms a sequence of pairs into a pair of sequences.
unzip xs is equivalent to (map fst xs, map snd xs).
Querying either of the sequences returned by unzip 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 unzip (memoize xs).
val partition_map : ('a->('b, 'c)Either.t)->'at->'bt * 'ct
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).
since 4.14
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.
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).