Library
Module
Module type
Parameter
Class
Class type
include module type of Seq with type 'a node = 'a Seq.node
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.
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.
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.
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)
.
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)
.
The functions in this section are lazy: that is, they return sequences whose elements are computed only when demanded.
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 ())
.
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.
If xss
is a sequence of sequences, then concat xss
is its concatenation.
If xss
is the sequence xs0; xs1; ...
then concat xss
is the sequence xs0 @ xs1 @ ...
.
concat_map f xs
is equivalent to concat (map f xs)
.
concat_map
is an alias for flat_map
.
The sequence map_product f xs ys
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 f x y
appears once as an element of map_product f xs ys
.
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_product f xs ys
is equivalent to map (fun (x, y) -> f x y) (product xs ys)
.
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)
.
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.
val ints : int -> int t
ints i
is the infinite sequence of the integers beginning at i
and counting up.
type 'a seq = 'a t
type 'a printer = Format.formatter -> 'a -> unit
val empty : 'a t
Empty iterator, with no elements
val return : 'a -> 'a t
One-element iterator
val repeat : 'a -> 'a t
Repeat same element endlessly
val head_exn : 'a t -> 'a
Returns first element, or fails.
Cycle through the iterator infinitely. The iterator shouldn't be empty.
# OSeq.(cycle (1--3) |> take 10 |> to_list);;
- : int list = [1; 2; 3; 1; 2; 3; 1; 2; 3; 1]
val iterate : 'a -> ('a -> 'a) -> 'a t
iterate x f
is [x; f x; f (f x); f (f (f x)); ...]
.
# OSeq.(iterate 0 succ |> take 10 |> to_list);;
- : int list = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9]
val unfold : ('b -> ('a * 'b) option) -> 'b -> 'a t
Dual of fold
, with a deconstructing operation. It keeps on unfolding the 'b
value into a new 'b
, and a 'a
which is yielded, until None
is returned.
# OSeq.(unfold (fun x -> if x<5 then Some (string_of_int x, x+1) else None) 0 |> to_list);;
- : string list = ["0"; "1"; "2"; "3"; "4"]
val repeatedly : (unit -> 'a) -> 'a t
Call the same function an infinite number of times (useful for instance if the function is a random iterator).
val init : ?n:int -> (int -> 'a) -> 'a t
Calls the function, starting from 0, on increasing indices. If n
is provided and is a positive int, iteration will stop at the limit (excluded). For instance init ~n:4 (fun x->x)
will yield 0, 1, 2, and 3.
val is_empty : _ t -> bool
Check whether the iterator is empty. Pops an element, if any
val fold : ('b -> 'a -> 'b) -> 'b -> 'a t -> 'b
Fold on the iterator, tail-recursively.
val foldi : (int -> 'b -> 'a -> 'b) -> 'b -> 'a t -> 'b
Fold on the iterator, tail-recursively.
val reduce : ('a -> 'a -> 'a) -> 'a t -> 'a
Fold on non-empty iterators.
Like fold
, but keeping successive values of the accumulator.
# OSeq.(scan (+) 0 (1--5) |> to_list);;
- : int list = [0; 1; 3; 6; 10; 15]
val iter : ('a -> unit) -> 'a t -> unit
Iterate on the iterator .
val iteri : (int -> 'a -> unit) -> 'a t -> unit
Iterate on elements with their index in the iterator, from 0.
val length : _ t -> int
Length of an iterator (linear time).
Lazy map. No iteration is performed now, the function will be called when the result is traversed.
Lazy map with indexing starting from 0. No iteration is performed now, the function will be called when the result is traversed.
Lazy fold and map. No iteration is performed now, the function will be called when the result is traversed. The result is an iterator over the successive states of the fold. The final accumulator is discarded. Unlike scan
, fold_map does not return the first accumulator.
Append the two iterators; the result contains the elements of the first, then the elements of the second iterator.
Monadic bind; each element is transformed to a sub-iterator which is then iterated on, before the next element is processed, and so on.
Same as app
but interleaves the values of the function and the argument iterators. See interleave
for more details.
flat_map_interleave f seq
is similar to flat_map f seq
, except that each sub-sequence is interleaved rather than concatenated in order. See interleave
for more details.
val mem : eq:('a -> 'a -> bool) -> 'a -> 'a t -> bool
Is the given element, member of the iterator?
val nth : int -> 'a t -> 'a
n-th element, or Not_found
take_nth n g
returns every element of g
whose index is a multiple of n
. For instance take_nth 2 (1--10) |> to_list
will return [1;3;5;7;9]
val fold_while : ('a -> 'b -> 'a * [ `Stop | `Continue ]) -> 'a -> 'b t -> 'a
Fold elements until ('a, `Stop
) is indicated by the accumulator.
partition p l
returns the elements that satisfy p
, and the elements that do not satisfy p
val for_all : ('a -> bool) -> 'a t -> bool
Is the predicate true for all elements?
val exists : ('a -> bool) -> 'a t -> bool
Is the predicate true for at least one element?
val min : lt:('a -> 'a -> bool) -> 'a t -> 'a
Minimum element, according to the given comparison function.
Lexicographic comparison of iterators. If a iterator is a prefix of the other one, it is considered smaller.
val find : ('a -> bool) -> 'a t -> 'a option
find p e
returns the first element of e
to satisfy p
, or None.
val find_map : ('a -> 'b option) -> 'a t -> 'b option
find_map f e
returns the result of f
on the first element of e
for which it returns Some _
, or None
otherwise.
val sum : int t -> int
Sum of all elements
Map on the two iterators. Stops once one of them is exhausted.
Iterate on the two iterators. Stops once one of them is exhausted.
Fold the common prefix of the two iterators
Succeeds if all pairs of elements satisfy the predicate. Ignores elements of an iterator if the other runs dry.
Succeeds if some pair of elements satisfy the predicate. Ignores elements of an iterator if the other runs dry.
Combine common part of the gens (stops when one is exhausted)
Pick elements fairly in each sub-iterator. The merge of gens e1, e2, ...
picks elements in e1
, e2
, in e3
, e1
, e2
.... Once an iterator is empty, it is skipped; when they are all empty, and none remains in the input, their merge is also empty. For instance, merge [1;3;5] [2;4;6]
will be, in disorder, 1;2;3;4;5;6
.
Intersection of two sorted iterators. Only elements that occur in both inputs appear in the output
Merge two sorted iterators into a sorted iterator
Split the iterator into n
iterators in a fair way. Elements with index = k mod n
with go to the k-th iterator. n
default value is 2.
interleave a b
yields an element of a
, then an element of b
, and so on. When one of the iterators is exhausted, this behaves like the other iterator.
Put the separator element between all elements of the given iterator
Cartesian product, in no predictable order. Works even if some of the arguments are infinite.
Cartesian product of three iterators, see product.
Cartesian product of four iterators, see product.
Cartesian product of five iterators, see product.
Cartesian product of six iterators, see product.
val product7 :
'a t ->
'b t ->
'c t ->
'd t ->
'e t ->
'f t ->
'g t ->
('a * 'b * 'c * 'd * 'e * 'f * 'g) t
Cartesian product of seven iterators, see product.
Produce the cartesian product of this sequence of sequences, by returning all the ways of picking one element per sequence. NOTE the order of the returned sequence is unspecified.
This assumes each sub-sequence is finite, and that the main sequence is also finite.
For example:
# cartesian_product [[1;2];[3];[4;5;6]] |> sort =
[[1;3;4];[1;3;5];[1;3;6];[2;3;4];[2;3;5];[2;3;6]];;
# cartesian_product [[1;2];[];[4;5;6]] = [];;
# cartesian_product [[1;2];[3];[4];[5];[6]] |> sort =
[[1;3;4;5;6];[2;3;4;5;6]];;
invariant: cartesian_product l = map_product_l id l
.
map_product_l f l
maps each element of l
to a list of objects of type 'b
using f
. We obtain [l1;l2;...;ln]
where length l=n
and li : 'b list
. Then, it returns all the ways of picking exactly one element per li
.
Remove consecutive duplicate elements. Basically this is like fun e -> map List.hd (group e)
.
Sort according to the given comparison function. The iterator must be finite.
Sort and remove duplicates. The iterator must be finite.
chunks n e
returns a iterator of arrays of length n
, composed of successive elements of e
. The last array may be smaller than n
val permutations : 'a list -> 'a list t
Permutations of the list.
Combinations of given length. The ordering of the elements within each combination is unspecified. Example (ignoring ordering): combinations 2 (1--3) |> to_list = [[1;2]; [1;3]; [2;3]]
All subsets of the iterator (in no particular order). The ordering of the elements within each subset is unspecified.
module type HashedType = Hashtbl.HashedType
A type that can be compared and hashed. invariant: for any x
and y
, if equal x y
then hash x=hash y
must hold.
val group_by :
(module HashedType with type t = 'key) ->
project:('a -> 'key) ->
'a t ->
('key * 'a list) t
Group together elements that project onto the same key, ignoring their order of appearance. The order of each resulting list is unspecified.
This function needs to consume the whole input before it can emit anything.
val group_by_fold :
(module HashedType with type t = 'key) ->
project:('a -> 'key) ->
fold:('b -> 'a -> 'b) ->
init:'b ->
'a t ->
('key * 'b) t
Group together elements that project onto the same key, folding them into some aggregate of type 'b
as they are met. This is the most general version of the "group_by" functions.
This function needs to consume the whole input before it can emit anything.
val group_count : (module HashedType with type t = 'a) -> 'a t -> ('a * int) t
Map each distinct element to its number of occurrences in the whole seq. Similar to group_by_fold hash_key ~project:(fun x->x) ~fold:(fun a _->a+1) ~init:0 seq
.
This function needs to consume the whole input before it can emit anything.
val join_by :
(module HashedType with type t = 'key) ->
project_left:('a -> 'key) ->
project_right:('b -> 'key) ->
merge:('key -> 'a -> 'b -> 'c option) ->
'a t ->
'b t ->
'c t
join_by ~project_left ~project_right ~merge a b
takes every pair of elements x
from a
and y
from b
, and if they map onto the same key k
by project_left
and project_right
respectively, and if merge k x y = Some res
, then it yields res
.
If merge k x y
returns None
, the combination of values is discarded.
This function works with infinite inputs, it does not have to consume the whole input before yielding elements.
val join_by_fold :
(module HashedType with type t = 'key) ->
project_left:('a -> 'key) ->
project_right:('b -> 'key) ->
init:'c ->
merge:('key -> 'a -> 'b -> 'c -> 'c) ->
'a t ->
'b t ->
'c t
join_by_fold ~project_left ~project_right ~init ~merge a b
takes every pair of elements x
from a
and y
from b
, and if they map onto the same key k
by project_left
and project_right
respectively, it fold x
and y
into the accumulator for this key (which starts at init
).
This function consumes both inputs entirely before it emits anything.
val of_list : 'a list -> 'a t
Enumerate elements of the list
val to_list : 'a t -> 'a list
non tail-call trasnformation to list, in the same order
val to_rev_list : 'a t -> 'a list
Tail call conversion to list, in reverse order (more efficient)
val to_array : 'a t -> 'a array
Convert the iterator to an array (not very efficient). The iterator must be memoized, as it's traversed twice.
val of_array : ?start:int -> ?len:int -> 'a array -> 'a t
Iterate on (a slice of) the given array
Build a functional iterator from a mutable, imperative generator. The result is properly memoized and can be iterated on several times, as a normal functional value.
val of_string : ?start:int -> ?len:int -> string -> char t
Iterate on bytes of the string
val to_string : char t -> string
Convert into a string
Traverse the iterator and writes its content to the buffer
val concat_string : sep:string -> string t -> string
concat_string ~sep s
concatenates all strings of i
, separated with sep
. The iterator must be memoized.
module Infix : sig ... end
Pretty print the content of the iterator on a formatter.
Store content of the transient iterator in memory, to be able to iterate on it several times later.
module Generator : sig ... end
This interface is designed to make it easy to build complex streams of values in a way that resembles Python's generators (using "yield").
module IO : sig ... end
module type MONAD = sig ... end