The iterators are designed to allow easy transfer (mappings) between data
structures, without defining n^2
conversions between the n
types. The
implementation relies on the assumption that a sequence can be iterated
on as many times as needed; this choice allows for high performance
of many combinators. However, for transient iterators, the persistent
function is provided, storing elements of a transient iterator
in memory; the iterator can then be used several times (See further).
Note that some combinators also return sequences (e.g. group). The transformation is computed on the fly every time one iterates over the resulting sequence. If a transformation performs heavy computation, persistent can also be used as intermediate storage.
Most functions are lazy, i.e. they do not actually use their arguments until their result is iterated on. For instance, if one calls map on a sequence, one gets a new sequence, but nothing else happens until this new sequence is used (by folding or iterating on it).
If a sequence is built from an iteration function that is repeatable (i.e. calling it several times always iterates on the same set of elements, for instance List.iter or Map.iter), then the resulting t object is also repeatable. For one-time iter functions such as iteration on a file descriptor or a Stream, the persistent function can be used to iterate and store elements in a memory structure; the result is a sequence that iterates on the elements of this memory structure, cheaply and repeatably.
type +'a t
= ('a ‑> unit) ‑> unit
A sequence of values of type 'a
. If you give it a function 'a -> unit
it will be applied to every element of the sequence successively.
NOTE Type ('a, 'b) t2 = ('a -> 'b -> unit) -> unit
has been removed and subsumed by ('a * 'b) t
val from_fun : (unit ‑> 'a option) ‑> 'a t
Call the function repeatedly until it returns None. This sequence is transient, use persistent if needed!
val repeat : 'a ‑> 'a t
Infinite sequence of the same element. You may want to look at take and the likes if you iterate on it.
val forever : (unit ‑> 'b) ‑> 'b t
Sequence that calls the given function to produce elements. The sequence may be transient (depending on the function), and definitely is infinite. You may want to use take and persistent.
Cycle forever through the given sequence. Assume the given sequence can be traversed any amount of times (not transient). This yields an infinite sequence, you should use something like take not to loop forever.
val iter : ('a ‑> unit) ‑> 'a t ‑> unit
Consume the sequence, passing all its arguments to the function.
Basically iter f seq
is just seq f
.
val foldi : ('a ‑> int ‑> 'b ‑> 'a) ‑> 'a ‑> 'b t ‑> 'a
Fold over elements of the sequence and their index, consuming it
fold_filter_map f acc l
is a fold_map-like function, but the
function can choose to skip an element by retuning None
.
Map objects two by two. lazily. The last element is kept in the sequence if the count is odd.
val mem : ?eq:('a ‑> 'a ‑> bool) ‑> 'a ‑> 'a t ‑> bool
Is the value a member of the sequence?
(=)
)val find : ('a ‑> 'b option) ‑> 'a t ‑> 'b option
Find the first element on which the function doesn't return None
val find_pred : ('a ‑> bool) ‑> 'a t ‑> 'a option
find_pred p l
finds the first element of l
that satisfies p
,
or returns None
if no element satisfies p
val find_pred_exn : ('a ‑> bool) ‑> 'a t ‑> 'a
Unsafe version of find_pred
Append sequences. Iterating on the result is like iterating on the each sequence of the list in order.
Monadic bind. Intuitively, it applies the function to every
element of the initial sequence, and calls concat.
Formerly flatMap
seq_list l
returns all the ways to pick one element in each sub-sequence
in l
. Assumes the sub-sequences can be iterated on several times.
seq_list_map f l
maps f
over every element of l
,
then calls seq_list
val filter_count : ('a ‑> bool) ‑> 'a t ‑> int
Count how many elements satisfy the given predicate
Iterate on the sequence, storing elements in an efficient internal structure.. The resulting sequence can be iterated on as many times as needed. Note: calling persistent on an already persistent sequence will still make a new copy of the sequence!
Lazy version of persistent. When calling persistent_lazy s
,
a new sequence s'
is immediately returned (without actually consuming
s
) in constant time; the first time s'
is iterated on,
it also consumes s
and caches its content into a inner data
structure that will back s'
for future iterations.
warning: on the first traversal of s'
, if the traversal
is interrupted prematurely (take, etc.) then s'
will not be
memorized, and the next call to s'
will traverse s
again.
Sort the sequence. Eager, O(n) ram and O(n ln(n)) time. It iterates on elements of the argument sequence immediately, before it sorts them.
val sorted : ?cmp:('a ‑> 'a ‑> int) ‑> 'a t ‑> bool
Checks whether the sequence is sorted. Eager, same as sort.
Group equal elements, disregarding their order of appearance.
The result sequence is traversable as many times as required.
precondition: for any x
and y
, if eq x y
then hash x=hash y
must hold.
Map each distinct element to its number of occurrences in the whole seq.
Similar to group_by seq |> map (fun l->List.hd l, List.length l)
precondition: for any x
and y
, if eq x y
then hash x=hash y
must hold.
Cartesian product of the sequences. When calling product a b
,
the caller MUST ensure that b
can be traversed as many times
as required (several times), possibly by calling persistent on it
beforehand.
val diagonal_l : 'a list ‑> ('a * 'a) t
All pairs of distinct positions of the list. diagonal l
will
return the sequence of all List.nth i l, List.nth j l
if i < j
.
All pairs of distinct positions of the sequence. Iterates only once on the sequence, which must be finite.
join ~join_row a b
combines every element of a
with every
element of b
using join_row
. If join_row
returns None, then
the two elements do not combine. Assume that b
allows for multiple
iterations.
val join_by : ?eq:'key equal ‑> ?hash:'key hash ‑> ('a ‑> 'key) ‑> ('b ‑> 'key) ‑> merge:('key ‑> 'a ‑> 'b ‑> 'c option) ‑> 'a t ‑> 'b t ‑> 'c t
join key1 key2 ~merge
is a binary operation
that takes two sequences a
and b
, projects their
elements resp. with key1
and key2
, and combine
values (x,y)
from (a,b)
with the same key
using merge
. If merge
returns None
, the combination
of values is discarded.
precondition: for any x
and y
, if eq x y
then hash x=hash y
must hold.
val join_all_by : ?eq:'key equal ‑> ?hash:'key hash ‑> ('a ‑> 'key) ‑> ('b ‑> 'key) ‑> merge:('key ‑> 'a list ‑> 'b list ‑> 'c option) ‑> 'a t ‑> 'b t ‑> 'c t
join_all_by key1 key2 ~merge
is a binary operation
that takes two sequences a
and b
, projects their
elements resp. with key1
and key2
, and, for each key k
occurring in at least one of them:
l1
of elements of a
that map to k
l2
of elements of b
that map to k
merge k l1 l2
. If merge
returns None
, the combination
of values is discarded, otherwise it returns Some c
and c
is inserted in the result.val group_join_by : ?eq:'a equal ‑> ?hash:'a hash ‑> ('b ‑> 'a) ‑> 'a t ‑> 'b t ‑> ('a * 'b list) t
group_join_by key2
associates to every element x
of
the first sequence, all the elements y
of the second
sequence such that eq x (key y)
. Elements of the first
sequences without corresponding values in the second one
are mapped to []
precondition: for any x
and y
, if eq x y
then hash x=hash y
must hold.
Intersection of two collections. Each element will occur at most once
in the result. Eager.
precondition: for any x
and y
, if eq x y
then hash x=hash y
must hold.
Union of two collections. Each element will occur at most once
in the result. Eager.
precondition: for any x
and y
, if eq x y
then hash x=hash y
must hold.
subset a b
returns true
if all elements of a
belong to b
. Eager.
precondition: for any x
and y
, if eq x y
then hash x=hash y
must hold.
val unfoldr : ('b ‑> ('a * 'b) option) ‑> 'b ‑> 'a t
unfoldr f b
will apply f
to b
. If it
yields Some (x,b')
then x
is returned
and unfoldr recurses with b'
.
val max : ?lt:('a ‑> 'a ‑> bool) ‑> 'a t ‑> 'a option
Max element of the sequence, using the given comparison function.
m
where m
is the maximal
element otherwiseval max_exn : ?lt:('a ‑> 'a ‑> bool) ‑> 'a t ‑> 'a
Unsafe version of max
val min : ?lt:('a ‑> 'a ‑> bool) ‑> 'a t ‑> 'a option
Min element of the sequence, using the given comparison function. see max for more details.
val min_exn : ?lt:('a ‑> 'a ‑> bool) ‑> 'a t ‑> 'a
Unsafe version of min
val head_exn : 'a t ‑> 'a
First element, if any, fails
Take elements while they satisfy the predicate, then stops iterating.
Will work on an infinite sequence s
if the predicate is false for at
least one element of s
.
val fold_while : ('a ‑> 'b ‑> 'a * [ `Stop | `Continue ]) ‑> 'a ‑> 'b t ‑> 'a
Folds over elements of the sequence, stopping early if the accumulator
returns ('a, `Stop)
Reverse the sequence. O(n) memory and time, needs the sequence to be finite. The result is persistent and does not depend on the input being repeatable.
val fold2 : ('c ‑> 'a ‑> 'b ‑> 'c) ‑> 'c ‑> ('a * 'b) t ‑> 'c
val iter2 : ('a ‑> 'b ‑> unit) ‑> ('a * 'b) t ‑> unit
val to_list : 'a t ‑> 'a list
Convert the sequence into a list. Preserves order of elements. This function is tail-recursive, but consumes 2*n memory. If order doesn't matter to you, consider to_rev_list.
val to_rev_list : 'a t ‑> 'a list
Get the list of the reversed sequence (more efficient than to_list)
val of_list : 'a list ‑> 'a t
Similar to zip_i but returns a normal sequence of tuples
val to_array : 'a t ‑> 'a array
Convert to an array. Currently not very efficient because an intermediate list is used.
val of_array : 'a array ‑> 'a t
val array_slice : 'a array ‑> int ‑> int ‑> 'a t
array_slice a i j
Sequence of elements whose indexes range
from i
to j
val to_stream : 'a t ‑> 'a Stream.t
Convert to a stream. linear in memory and time (a copy is made in memory)
val hashtbl_add : ('a, 'b) Hashtbl.t ‑> ('a * 'b) t ‑> unit
Add elements of the sequence to the hashtable, with Hashtbl.add
val hashtbl_replace : ('a, 'b) Hashtbl.t ‑> ('a * 'b) t ‑> unit
Add elements of the sequence to the hashtable, with Hashtbl.replace (erases conflicting bindings)
val to_hashtbl : ('a * 'b) t ‑> ('a, 'b) Hashtbl.t
Build a hashtable from a sequence of key/value pairs
val hashtbl_keys : ('a, 'b) Hashtbl.t ‑> 'a t
val hashtbl_values : ('a, 'b) Hashtbl.t ‑> 'b t
val of_str : string ‑> char t
val to_str : char t ‑> string
val concat_str : string t ‑> string
Concatenate strings together, eagerly. Also see intersperse to add a separator.
exception
OneShotSequence
Raised when the user tries to iterate several times on a transient iterator
val of_in_channel : Pervasives.in_channel ‑> char t
Iterates on characters of the input (can block when one iterates over the sequence). If you need to iterate several times on this sequence, use persistent.
val int_range : start:int ‑> stop:int ‑> int t
val int_range_dec : start:int ‑> stop:int ‑> int t
val int_range_by : step:int ‑> int ‑> int ‑> int t
int_range_by ~step i j
is the range starting at i
, including j
,
where the difference between successive elements is step
.
use a negative step
for a decreasing sequence.
step=0
val of_set : (module Set.S with type elt = 'a and type t = 'b) ‑> 'b ‑> 'a t
Convert the given set to a sequence. The set module must be provided.
val to_set : (module Set.S with type elt = 'a and type t = 'b) ‑> 'a t ‑> 'b
Convert the sequence to a set, given the proper set module
module Set : sig ... end
module Map : sig ... end
val random_int : int ‑> int t
Infinite sequence of random integers between 0 and the given higher bound (see Random.int)
val random_float : float ‑> float t
val random_list : 'a list ‑> 'a t
Infinite sequence of random elements of the list. Basically the same as random_array.
shuffle_buffer n seq
returns a sequence of element of seq
in random
order. The shuffling is *not* uniform. Uses O(n) memory.
The first n
elements of the sequence are consumed immediately. The
rest is consumed lazily.
val sample : int ‑> 'a t ‑> 'a array
sample n seq
returns k samples of seq
, with uniform probability.
It will consume the sequence and use O(n) memory.
It returns an array of size min (length seq) n
.
module Infix : sig ... end
include module type of Infix
val (--) : int ‑> int ‑> int t
a -- b
is the range of integers from a
to b
, both included,
in increasing order. It will therefore be empty if a > b
.
val (--^) : int ‑> int ‑> int t
a --^ b
is the range of integers from b
to a
, both included,
in decreasing order (starts from a
).
It will therefore be empty if a < b
.
val pp_seq : ?sep:string ‑> (Format.formatter ‑> 'a ‑> unit) ‑> Format.formatter ‑> 'a t ‑> unit
Pretty print a sequence of 'a
, using the given pretty printer
to print each elements. An optional separator string can be provided.
val pp_buf : ?sep:string ‑> (Buffer.t ‑> 'a ‑> unit) ‑> Buffer.t ‑> 'a t ‑> unit
Print into a buffer
Very basic interface to manipulate files as sequence of chunks/lines. The sequences take care of opening and closing files properly; every time one iterates over a sequence, the file is opened/closed again.
Example: copy a file "a"
into file "b"
, removing blank lines:
Sequence.(IO.lines_of "a" |> filter (fun l-> l<> "") |> IO.write_lines "b");;
By chunks of 4096
bytes:
Sequence.IO.(chunks_of ~size:4096 "a" |> write_to "b");;
Read the lines of a file into a list:
Sequence.IO.lines "a" |> Sequence.to_list
module IO : sig ... end