module Seq: sig .. end
Functional iterators.
The type 'a Seq.t
is a delayed list, i.e. a list where some
evaluation is needed to access the next element. This makes it possible
to build infinite sequences, to build sequences as we traverse them, and
to transform them in a lazy fashion rather than upfront.
type t('a) = unit => node('a);
The type of delayed lists containing elements of type 'a
.
Note that the concrete list node 'a node
is delayed under a closure,
not a lazy
block, which means it might be recomputed every time
we access it.
type 'a node =
| |
Nil |
| |
Cons of 'a * 'a t |
A fully-evaluated list node, either empty or containing an element and a delayed tail.
let empty: t('a);
The empty sequence, containing no elements.
let return: 'a => t('a);
The singleton sequence containing only the given element.
let cons: ('a, t('a)) => t('a);
cons x xs
is the sequence containing the element x
followed by
the sequence xs
let append: (t('a), t('a)) => t('a);
append xs ys
is the sequence xs
followed by the sequence ys
let map: ('a => 'b, t('a)) => t('b);
map f seq
returns a new sequence whose elements are the elements of
seq
, transformed by f
.
This transformation is lazy, it only applies when the result is traversed.
If seq = [1;2;3]
, then map f seq = [f 1; f 2; f 3]
.
let filter: ('a => bool, t('a)) => t('a);
Remove from the sequence the elements that do not satisfy the given predicate. This transformation is lazy, it only applies when the result is traversed.
let filter_map: ('a => option('b), t('a)) => t('b);
Apply the function to every element; if f x = None
then x
is dropped;
if f x = Some y
then y
is returned.
This transformation is lazy, it only applies when the result is
traversed.
let flat_map: ('a => t('b), t('a)) => t('b);
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.
let fold_left: (('a, 'b) => 'a, 'a, t('b)) => 'a;
Traverse the sequence from left to right, combining each element with the accumulator using the given function. The traversal happens immediately and will not terminate on infinite sequences.
Also see List.fold_left
let iter: ('a => unit, t('a)) => unit;
Iterate on the sequence, calling the (imperative) function on every element. The traversal happens immediately and will not terminate on infinite sequences.
let unfold: ('b => option(('a, 'b)), 'b) => t('a);
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
.