Module Gen
Generators
Values of type 'a Gen.t
represent a possibly infinite sequence of values of type 'a. One can only iterate once on the sequence, as it is consumed by iteration/deconstruction/access. None
is returned when the generator is exhausted.
The submodule Restart
provides utilities to work with restartable generators, that is, functions unit -> 'a Gen.t
that allow to build as many generators from the same source as needed.
Global type declarations
type 'a t
= unit -> 'a option
A generator may be called several times, yielding the next value each time. It returns
None
when no elements remain
type 'a gen
= 'a t
module type S = Gen_intf.S
Transient generators
val get : 'a t -> 'a option
Get the next value
val get_exn : 'a t -> 'a
Get the next value, or fails
- raises Invalid_argument
if no element remains
val junk : 'a t -> unit
Drop the next value, discarding it.
val repeatedly : (unit -> 'a) -> 'a t
Call the same function an infinite number of times (useful for instance if the function is a random generator).
Operations on transient generators
include S with type 'a S.t := 'a gen
val empty : 'a t
Empty generator, with no elements
val singleton : 'a -> 'a t
One-element generator
val repeat : 'a -> 'a t
Repeat same element endlessly
val iterate : 'a -> ('a -> 'a) -> 'a t
iterate x f
is[x; f x; f (f x); f (f (f x)); ...]
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, untilNone
is returned.
val init : ?limit:int -> (int -> 'a) -> 'a t
Calls the function, starting from 0, on increasing indices. If
limit
is provided and is a positive int, iteration will stop at the limit (excluded). For instanceinit ~limit:4 id
will yield 0, 1, 2, and 3.
Basic combinators
Note: those combinators, applied to generators (not restartable generators) consume their argument. Sometimes they consume it lazily, sometimes eagerly, but in any case once f gen
has been called (with f
a combinator), gen
shouldn't be used anymore.
val is_empty : _ t -> bool
Check whether the gen is empty. Pops an element, if any
val fold : ('b -> 'a -> 'b) -> 'b -> 'a t -> 'b
Fold on the generator, tail-recursively. Consumes the generator.
val reduce : ('a -> 'a -> 'a) -> 'a t -> 'a
Fold on non-empty sequences. Consumes the generator.
- raises Invalid_argument
on an empty gen
val scan : ('b -> 'a -> 'b) -> 'b -> 'a t -> 'b t
Like
fold
, but keeping successive values of the accumulator. Consumes the generator.
val unfold_scan : ('b -> 'a -> 'b * 'c) -> 'b -> 'a t -> 'c t
A mix of
unfold
andscan
. The current state is combined with the current element to produce a new state, and an output value of type 'c.- since
- 0.2.2
val iter : ('a -> unit) -> 'a t -> unit
Iterate on the gen, consumes it.
val iteri : (int -> 'a -> unit) -> 'a t -> unit
Iterate on elements with their index in the gen, from 0, consuming it.
val length : _ t -> int
Length of an gen (linear time), consuming it
val map : ('a -> 'b) -> 'a t -> 'b t
Lazy map. No iteration is performed now, the function will be called when the result is traversed.
val mapi : (int -> 'a -> 'b) -> 'a t -> 'b t
Lazy map with indexing starting from 0. No iteration is performed now, the function will be called when the result is traversed.
- since
- 0.5
val fold_map : ('b -> 'a -> 'b) -> 'b -> 'a t -> 'b t
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.
- since
- 0.2.4
val append : 'a t -> 'a t -> 'a t
Append the two gens; the result contains the elements of the first, then the elements of the second gen.
val flatten : 'a Gen_intf.gen t -> 'a t
Flatten the generator of generators
val flat_map : ('a -> 'b Gen_intf.gen) -> 'a t -> 'b t
Monadic bind; each element is transformed to a sub-gen which is then iterated on, before the next element is processed, and so on.
val mem : ?eq:('a -> 'a -> bool) -> 'a -> 'a t -> bool
Is the given element, member of the gen?
val nth : int -> 'a t -> 'a
n-th element, or Not_found
- raises Not_found
if the generator contains less than
n
arguments
val take_nth : int -> 'a t -> 'a t
take_nth n g
returns every element ofg
whose index is a multiple ofn
. For instancetake_nth 2 (1--10) |> to_list
will return1;3;5;7;9
val take_while : ('a -> bool) -> 'a t -> 'a t
Take elements while they satisfy the predicate. The initial generator itself is not to be used anymore after this.
val fold_while : ('a -> 'b -> 'a * [ `Stop | `Continue ]) -> 'a -> 'b t -> 'a
Fold elements until (
'a, `Stop
) is indicated by the accumulator.- since
- 0.2.4
val drop_while : ('a -> bool) -> 'a t -> 'a t
Drop elements while they satisfy the predicate. The initial generator itself should not be used anymore, only the result of
drop_while
.
val partition : ('a -> bool) -> 'a t -> 'a t * 'a t
partition p l
returns the elements that satisfyp
, and the elements that do not satisfyp
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.
- raises Invalid_argument
if the generator is empty
val max : ?lt:('a -> 'a -> bool) -> 'a t -> 'a
Maximum element, see
min
- raises Invalid_argument
if the generator is empty
val lexico : ?cmp:('a -> 'a -> int) -> 'a t -> 'a t -> int
Lexicographic comparison of generators. If a generator 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 ofe
to satisfyp
, or None.
val sum : int t -> int
Sum of all elements
Multiple iterators
val map2 : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t
Map on the two sequences. Stops once one of them is exhausted.
val iter2 : ('a -> 'b -> unit) -> 'a t -> 'b t -> unit
Iterate on the two sequences. Stops once one of them is exhausted.
val fold2 : ('acc -> 'a -> 'b -> 'acc) -> 'acc -> 'a t -> 'b t -> 'acc
Fold the common prefix of the two iterators
val for_all2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool
Succeeds if all pairs of elements satisfy the predicate. Ignores elements of an iterator if the other runs dry.
val exists2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool
Succeeds if some pair of elements satisfy the predicate. Ignores elements of an iterator if the other runs dry.
Complex combinators
val merge : 'a Gen_intf.gen t -> 'a t
Pick elements fairly in each sub-generator. The merge of gens
e1, e2, ...
picks elements ine1
,e2
, ine3
,e1
,e2
.... Once a generator 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
.
val intersection : ?cmp:('a -> 'a -> int) -> 'a t -> 'a t -> 'a t
Intersection of two sorted sequences. Only elements that occur in both inputs appear in the output
val sorted_merge : ?cmp:('a -> 'a -> int) -> 'a t -> 'a t -> 'a t
Merge two sorted sequences into a sorted sequence
val sorted_merge_n : ?cmp:('a -> 'a -> int) -> 'a t list -> 'a t
Sorted merge of multiple sorted sequences
val tee : ?n:int -> 'a t -> 'a Gen_intf.gen list
Duplicate the gen into
n
generators (default 2). The generators share the same underlying instance of the gen, so the optimal case is when they are consumed evenly
val round_robin : ?n:int -> 'a t -> 'a Gen_intf.gen list
Split the gen into
n
generators in a fair way. Elements withindex = k mod n
with go to the k-th gen.n
default value is 2.
val interleave : 'a t -> 'a t -> 'a t
interleave a b
yields an element ofa
, then an element ofb
, and so on. When a generator is exhausted, this behaves like the other generator.
val product : 'a t -> 'b t -> ('a * 'b) t
Cartesian product, in no predictable order. Works even if some of the arguments are infinite.
val uniq : ?eq:('a -> 'a -> bool) -> 'a t -> 'a t
Remove consecutive duplicate elements. Basically this is like
fun e -> map List.hd (group e)
.
val sort : ?cmp:('a -> 'a -> int) -> 'a t -> 'a t
Sort according to the given comparison function. The gen must be finite.
val sort_uniq : ?cmp:('a -> 'a -> int) -> 'a t -> 'a t
Sort and remove duplicates. The gen must be finite.
val chunks : int -> 'a t -> 'a array t
chunks n e
returns a generator of arrays of lengthn
, composed of successive elements ofe
. The last array may be smaller thann
val permutations_heap : 'a t -> 'a array t
Permutations of the gen, using Heap's algorithm.
- since
- 0.2.3
Basic conversion functions
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 gen to an array (not very efficient)
val of_array : ?start:int -> ?len:int -> 'a array -> 'a t
Iterate on (a slice of) the given array
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
val to_buffer : Buffer.t -> char t -> unit
Consumes the iterator and writes to the buffer
val rand_int : int -> int t
Random ints in the given range.
val int_range : ?step:int -> int -> int -> int t
int_range ~step a b
generates integers betweena
andb
, included, with steps of lengthstep
(1 if omitted).a
is assumed to be smaller thanb
, otherwise the result will be empty.- raises Invalid_argument
if
step=0
- parameter step
step between two numbers; must not be zero, but it can be negative for decreasing ranges (@since 0.5).
val unlines : string t -> char t
Explode lines into their chars, adding a
'\n'
after each one- since
- 0.3
module Infix : sig ... end
val (--) : int -> int -> int t
Synonym for
int_range ~by:1
val (>>=) : 'a t -> ('a -> 'b Gen_intf.gen) -> 'b t
Monadic bind operator
val pp : ?start:string -> ?stop:string -> ?sep:string -> ?horizontal:bool -> (Format.formatter -> 'a -> unit) -> Format.formatter -> 'a t -> unit
Pretty print the content of the generator on a formatter.
Restartable generators
A restartable generator is a function that produces copies of the same generator, on demand. It has the type unit -> 'a gen
and it is assumed that every generated returned by the function behaves the same (that is, that it traverses the same sequence of elements).
module Restart : sig ... end
Utils
val persistent : 'a t -> 'a Restart.t
Store content of the transient generator in memory, to be able to iterate on it several times later. If possible, consider using combinators from
Restart
directly instead.
val persistent_lazy : ?caching:bool -> ?max_chunk_size:int -> 'a t -> 'a Restart.t
Same as
persistent
, but consumes the generator on demand (by chunks). This allows to make a restartable generator out of an ephemeral one, without paying a big cost upfront (nor even consuming it fully). Optional parameters: seeGenMList.of_gen_lazy
.- since
- 0.2.2
val peek : 'a t -> ('a * 'a option) t
peek g
transforms the generatorg
into a generator ofx, Some next
ifx
was followed bynext
ing
, orx, None
ifx
was the last element ofg
- since
- 0.4
Basic IO
Very basic interface to manipulate files as sequence of chunks/lines.
- since
- 0.2.3
module IO : sig ... end