Module Iter
Simple and Efficient Iterators
type +'a t
= ('a -> unit) -> unit
An iterator of values of type
'a
. If you give it a function'a -> unit
it will be applied to every element of the iterator successively.
type +'a iter
= 'a t
Creation
val from_iter : (('a -> unit) -> unit) -> 'a t
Build an iterator from a iter function
val from_labelled_iter : (f:('a -> unit) -> unit) -> 'a t
Build an iterator from a labelled iter function
- since
- 1.2
val from_fun : (unit -> 'a option) -> 'a t
Call the function repeatedly until it returns None. This iterator is transient, use
persistent
if needed!
val empty : 'a t
Empty iterator. It contains no element.
val singleton : 'a -> 'a t
Singleton iterator, with exactly one element.
val doubleton : 'a -> 'a -> 'a t
Iterator with exactly two elements
val init : (int -> 'a) -> 'a t
init f
is the infinite iteratorf 0; f 1; f 2; …
.- since
- 0.9
val repeat : 'a -> 'a t
Infinite iterator of the same element. You may want to look at
take
and the likes if you iterate on it.
val iterate : ('a -> 'a) -> 'a -> 'a t
iterate f x
is the infinite iteratorx, f(x), f(f(x)), ...
val forever : (unit -> 'b) -> 'b t
Iterator that calls the given function to produce elements. The iterator may be transient (depending on the function), and definitely is infinite. You may want to use
take
andpersistent
.
val cycle : 'a t -> 'a t
Cycle forever through the given iterator. Assume the given iterator can be traversed any amount of times (not transient). This yields an infinite iterator, you should use something like
take
not to loop forever.
val unfoldr : ('b -> ('a * 'b) option) -> 'b -> 'a t
unfoldr f b
will applyf
tob
. If it yieldsSome (x,b')
thenx
is returned and unfoldr recurses withb'
.
Consumption
val iter : ('a -> unit) -> 'a t -> unit
Consume the iterator, passing all its arguments to the function. Basically
iter f seq
is justseq f
.
val iteri : (int -> 'a -> unit) -> 'a t -> unit
Iterate on elements and their index in the iterator
val fold : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a
Fold over elements of the iterator, consuming it
val foldi : ('a -> int -> 'b -> 'a) -> 'a -> 'b t -> 'a
Fold over elements of the iterator and their index, consuming it
val fold_map : ('acc -> 'a -> 'acc * 'b) -> 'acc -> 'a t -> 'b t
fold_map f acc l
is likemap
, but it carries some state as infold
. The state is not returned, it is just used to thread some information to the map function.- since
- 0.9
val fold_filter_map : ('acc -> 'a -> 'acc * 'b option) -> 'acc -> 'a t -> 'b t
fold_filter_map f acc l
is afold_map
-like function, but the function can choose to skip an element by retuningNone
.- since
- 0.9
val map_by_2 : ('a -> 'a -> 'a) -> 'a t -> 'a t
Map objects two by two. lazily. The last element is kept in the iterator if the count is odd.
- since
- 0.7
val for_all : ('a -> bool) -> 'a t -> bool
Do all elements satisfy the predicate?
val exists : ('a -> bool) -> 'a t -> bool
Exists there some element satisfying the predicate?
val mem : ?eq:('a -> 'a -> bool) -> 'a -> 'a t -> bool
Is the value a member of the iterator?
- parameter eq
the equality predicate to use (default
(=)
)
- since
- 0.5
val find : ('a -> 'b option) -> 'a t -> 'b option
Find the first element on which the function doesn't return
None
- since
- 0.5
val find_pred : ('a -> bool) -> 'a t -> 'a option
find_pred p l
finds the first element ofl
that satisfiesp
, or returnsNone
if no element satisfiesp
- since
- 0.9
val find_pred_exn : ('a -> bool) -> 'a t -> 'a
Unsafe version of
find_pred
- raises Not_found
if no such element is found
- since
- 0.9
val length : 'a t -> int
How long is the iterator? Forces the iterator.
val is_empty : 'a t -> bool
Is the iterator empty? Forces the iterator.
Transformation
val append : 'a t -> 'a t -> 'a t
Append two iterators. Iterating on the result is like iterating on the first, then on the second.
val append_l : 'a t list -> 'a t
Append iterators. Iterating on the result is like iterating on the each iterator of the list in order.
- since
- 0.11
val flat_map : ('a -> 'b t) -> 'a t -> 'b t
Monadic bind. Intuitively, it applies the function to every element of the initial iterator, and calls
concat
. FormerlyflatMap
- since
- 0.5
val flat_map_l : ('a -> 'b list) -> 'a t -> 'b t
Convenience function combining
flat_map
andof_list
- since
- 0.9
val seq_list : 'a t list -> 'a list t
seq_list l
returns all the ways to pick one element in each sub-iterator inl
. Assumes the sub-iterators can be iterated on several times.- since
- 0.11
val seq_list_map : ('a -> 'b t) -> 'a list -> 'b list t
seq_list_map f l
mapsf
over every element ofl
, then callsseq_list
- since
- 0.11
val filter_map : ('a -> 'b option) -> 'a t -> 'b t
Map and only keep non-
None
elements Formerlyfmap
- since
- 0.5
val filter_mapi : (int -> 'a -> 'b option) -> 'a t -> 'b t
Map with indices, and only keep non-
None
elements- since
- 0.11
val filter_count : ('a -> bool) -> 'a t -> int
Count how many elements satisfy the given predicate
- since
- 1.0
val keep_some : 'a option t -> 'a t
filter_some l
retains only elements of the formSome x
. Same asfilter_map (fun x->x)
- since
- 1.0
Caching
val persistent : 'a t -> 'a t
Iterate on the iterator, storing elements in an efficient internal structure.. The resulting iterator can be iterated on as many times as needed. Note: calling persistent on an already persistent iterator will still make a new copy of the iterator!
val persistent_lazy : 'a t -> 'a t
Lazy version of
persistent
. When callingpersistent_lazy s
, a new iterators'
is immediately returned (without actually consumings
) in constant time; the first times'
is iterated on, it also consumess
and caches its content into a inner data structure that will backs'
for future iterations.warning: on the first traversal of
s'
, if the traversal is interrupted prematurely (take
, etc.) thens'
will not be memorized, and the next call tos'
will traverses
again.
Misc
val sort : ?cmp:('a -> 'a -> int) -> 'a t -> 'a t
Sort the iterator. Eager, O(n) ram and O(n ln(n)) time. It iterates on elements of the argument iterator immediately, before it sorts them.
val sort_uniq : ?cmp:('a -> 'a -> int) -> 'a t -> 'a t
Sort the iterator and remove duplicates. Eager, same as
sort
val sorted : ?cmp:('a -> 'a -> int) -> 'a t -> bool
Checks whether the iterator is sorted. Eager, same as
sort
.- since
- 0.9
val group_succ_by : ?eq:('a -> 'a -> bool) -> 'a t -> 'a list t
Group equal consecutive elements. Linear time. Formerly synonym to
group
.- since
- 0.6
val group_by : ?hash:('a -> int) -> ?eq:('a -> 'a -> bool) -> 'a t -> 'a list t
Group equal elements, disregarding their order of appearance. The result iterator is traversable as many times as required. precondition: for any
x
andy
, ifeq x y
thenhash x=hash y
must hold.- since
- 0.6
val count : ?hash:('a -> int) -> ?eq:('a -> 'a -> bool) -> 'a t -> ('a * int) t
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 anyx
andy
, ifeq x y
thenhash x=hash y
must hold.- since
- 0.10
val uniq : ?eq:('a -> 'a -> bool) -> 'a t -> 'a t
Remove consecutive duplicate elements. Basically this is like
fun seq -> map List.hd (group seq)
.
val product : 'a t -> 'b t -> ('a * 'b) t
Cartesian product of iterators. When calling
product a b
, the caller MUST ensure thatb
can be traversed as many times as required (several times), possibly by callingpersistent
on it beforehand.
val diagonal_l : 'a list -> ('a * 'a) t
All pairs of distinct positions of the list.
diagonal l
will return the iterator of allList.nth i l, List.nth j l
ifi < j
.- since
- 0.9
val diagonal : 'a t -> ('a * 'a) t
All pairs of distinct positions of the iterator. Iterates only once on the iterator, which must be finite.
- since
- 0.9
val join : join_row:('a -> 'b -> 'c option) -> 'a t -> 'b t -> 'c t
join ~join_row a b
combines every element ofa
with every element ofb
usingjoin_row
. Ifjoin_row
returns None, then the two elements do not combine. Assume thatb
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 iteratorsa
andb
, projects their elements resp. withkey1
andkey2
, and combine values(x,y)
from(a,b)
with the samekey
usingmerge
. Ifmerge
returnsNone
, the combination of values is discarded. precondition: for anyx
andy
, ifeq x y
thenhash x=hash y
must hold.- since
- 0.10
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 iteratorsa
andb
, projects their elements resp. withkey1
andkey2
, and, for each keyk
occurring in at least one of them:- compute the list
l1
of elements ofa
that map tok
- compute the list
l2
of elements ofb
that map tok
- call
merge k l1 l2
. Ifmerge
returnsNone
, the combination of values is discarded, otherwise it returnsSome c
andc
is inserted in the result.
- since
- 0.10
- compute the list
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 elementx
of the first iterator, all the elementsy
of the second iterator such thateq x (key y)
. Elements of the first iterators without corresponding values in the second one are mapped to[]
precondition: for anyx
andy
, ifeq x y
thenhash x=hash y
must hold.- since
- 0.10
Set-like
val inter : ?eq:'a equal -> ?hash:'a hash -> 'a t -> 'a t -> 'a t
Intersection of two collections. Each element will occur at most once in the result. Eager. precondition: for any
x
andy
, ifeq x y
thenhash x=hash y
must hold.- since
- 0.10
Arithmetic
val max : ?lt:('a -> 'a -> bool) -> 'a t -> 'a option
Max element of the iterator, using the given comparison function.
- returns
None if the iterator is empty, Some
m
wherem
is the maximal element otherwise
val max_exn : ?lt:('a -> 'a -> bool) -> 'a t -> 'a
Unsafe version of
max
- raises Not_found
if the iterator is empty
- since
- 0.10
val min : ?lt:('a -> 'a -> bool) -> 'a t -> 'a option
Min element of the iterator, using the given comparison function. see
max
for more details.
val min_exn : ?lt:('a -> 'a -> bool) -> 'a t -> 'a
Unsafe version of
min
- raises Not_found
if the iterator is empty
- since
- 0.10
val sum : int t -> int
Sum of elements
- since
- 0.11
val sumf : float t -> float
Sum of elements, using Kahan summation
- since
- 0.11
List-like
val head : 'a t -> 'a option
First element, if any, otherwise
None
- since
- 0.5.1
val head_exn : 'a t -> 'a
First element, if any, fails
- raises Invalid_argument
if the iterator is empty
- since
- 0.5.1
val take : int -> 'a t -> 'a t
Take at most
n
elements from the iterator. Works on infinite iterators.
val take_while : ('a -> bool) -> 'a t -> 'a t
Take elements while they satisfy the predicate, then stops iterating. Will work on an infinite iterator
s
if the predicate is false for at least one element ofs
.
val fold_while : ('a -> 'b -> 'a * [ `Stop | `Continue ]) -> 'a -> 'b t -> 'a
Folds over elements of the iterator, stopping early if the accumulator returns
('a, `Stop)
- since
- 0.5.5
Pair iterators
Data structures converters
val to_list : 'a t -> 'a list
Convert the iterator 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 iterator (more efficient than
to_list
)
val of_list : 'a list -> 'a t
val on_list : ('a t -> 'b t) -> 'a list -> 'b list
on_list f l
is equivalent toto_list @@ f @@ of_list l
.- since
- 0.5.2
val pair_with_idx : 'a t -> (int * 'a) t
Similar to
zip_i
but returns a normal iterator of tuples- since
- 0.11
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 of_array_i : 'a array -> (int * 'a) t
Elements of the array, with their index
val array_slice : 'a array -> int -> int -> 'a t
array_slice a i j
Iterator of elements whose indexes range fromi
toj
val of_opt : 'a option -> 'a t
Iterate on 0 or 1 values.
- since
- 0.5.1
val of_stream : 'a Stream.t -> 'a t
Iterator of elements of a stream (usable only once)
val to_stream : 'a t -> 'a Stream.t
Convert to a stream. linear in memory and time (a copy is made in memory)
val to_stack : 'a Stack.t -> 'a t -> unit
Push elements of the iterator on the stack
val of_stack : 'a Stack.t -> 'a t
Iterator of elements of the stack (same order as
Stack.iter
)
val to_queue : 'a Queue.t -> 'a t -> unit
Push elements of the iterator into the queue
val of_queue : 'a Queue.t -> 'a t
Iterator of elements contained in the queue, FIFO order
val hashtbl_add : ('a, 'b) Hashtbl.t -> ('a * 'b) t -> unit
Add elements of the iterator to the hashtable, with Hashtbl.add
val hashtbl_replace : ('a, 'b) Hashtbl.t -> ('a * 'b) t -> unit
Add elements of the iterator to the hashtable, with Hashtbl.replace (erases conflicting bindings)
val to_hashtbl : ('a * 'b) t -> ('a, 'b) Hashtbl.t
Build a hashtable from an iterator of key/value pairs
val of_hashtbl : ('a, 'b) Hashtbl.t -> ('a * 'b) t
Iterator of key/value pairs from the hashtable
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.- since
- 0.5
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 iterator). If you need to iterate several times on this iterator, use
persistent
.- raises OneShotIterator
when used more than once.
val to_buffer : char t -> Buffer.t -> unit
Copy content of the iterator into the buffer
val int_range : start:int -> stop:int -> int t
Iterator on integers in
start...stop
by steps 1. Also see(--)
for an infix version.
val int_range_dec : start:int -> stop:int -> int t
Iterator on decreasing integers in
stop...start
by steps -1. See(--^)
for an infix version
val int_range_by : step:int -> int -> int -> int t
int_range_by ~step i j
is the range starting ati
, includingj
, where the difference between successive elements isstep
. use a negativestep
for a decreasing iterator.- raises Invalid_argument
if
step=0
val bools : bool t
Iterates on
true
andfalse
- since
- 0.7
val of_set : (module Set.S with type elt = 'a and type t = 'b) -> 'b -> 'a t
Convert the given set to an iterator. 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 iterator to a set, given the proper set module
type 'a gen
= unit -> 'a option
type 'a klist
= unit -> [ `Nil | `Cons of 'a * 'a klist ]
Sets
module Set : sig ... end
Maps
module Map : sig ... end
Random iterators
val random_int : int -> int t
Infinite iterator of random integers between 0 and the given higher bound (see Random.int)
val random_bool : bool t
Infinite iterator of random bool values
val random_float : float -> float t
val random_array : 'a array -> 'a t
Iterator of choices of an element in the array
val random_list : 'a list -> 'a t
Infinite iterator of random elements of the list. Basically the same as
random_array
.
val shuffle : 'a t -> 'a t
shuffle seq
returns a perfect shuffle ofseq
. Uses O(length seq) memory and time. Eager.- since
- 0.7
val shuffle_buffer : int -> 'a t -> 'a t
shuffle_buffer n seq
returns an iterator of element ofseq
in random order. The shuffling is *not* uniform. Uses O(n) memory.The first
n
elements of the iterator are consumed immediately. The rest is consumed lazily.- since
- 0.7
Sampling
val sample : int -> 'a t -> 'a array
sample n seq
returns k samples ofseq
, with uniform probability. It will consume the iterator and use O(n) memory.It returns an array of size
min (length seq) n
.- since
- 0.7
Infix functions
module Infix : sig ... end
include module type of Infix
val (--) : int -> int -> int t
a -- b
is the range of integers froma
tob
, both included, in increasing order. It will therefore be empty ifa > b
.
val (--^) : int -> int -> int t
a --^ b
is the range of integers fromb
toa
, both included, in decreasing order (starts froma
). It will therefore be empty ifa < b
.
Pretty printing
val pp_seq : ?sep:string -> (Format.formatter -> 'a -> unit) -> Format.formatter -> 'a t -> unit
Pretty print an iterator 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
val to_string : ?sep:string -> ('a -> string) -> 'a t -> string
Print into a string
Basic IO
Very basic interface to manipulate files as iterator of chunks/lines. The iterators take care of opening and closing files properly; every time one iterates over an iterator, the file is opened/closed again.
Example: copy a file "a"
into file "b"
, removing blank lines:
Iterator.(IO.lines_of "a" |> filter (fun l-> l<> "") |> IO.write_lines "b");;
By chunks of 4096
bytes:
Iterator.IO.(chunks_of ~size:4096 "a" |> write_to "b");;
Read the lines of a file into a list:
Iterator.IO.lines "a" |> Iterator.to_list
- since
- 0.5.1
module IO : sig ... end