gen

library gen

module GenLabels_intf

module GenMList

module GenShims_
Generators
Label version of Gen
Global type declarations
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 = GenLabels_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
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 t := 'a gen
val empty : 'a gen
Empty generator, with no elements
val singleton : 'a > 'a gen
Oneelement generator
val repeat : 'a > 'a gen
Repeat same element endlessly
val iterate : 'a > ( 'a > 'a ) > 'a gen
iterate x f
is [x; f x; f (f x); f (f (f x)); ...]
val unfold : ( 'b > ('a * 'b) option ) > 'b > 'a gen
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.
val init : ?limit:int > ( int > 'a ) > 'a gen
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 instance init ~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 : _ gen > bool
Check whether the gen is empty. Pops an element, if any
val fold : f:( 'b > 'a > 'b ) > init:'b > 'a gen > 'b
Fold on the generator, tailrecursively. Consumes the generator.
val reduce : f:( 'a > 'a > 'a ) > 'a gen > 'a
Fold on nonempty sequences. Consumes the generator.
Like fold
, but keeping successive values of the accumulator. Consumes the generator.
val iter : f:( 'a > unit ) > 'a gen > unit
Iterate on the gen, consumes it.
val iteri : f:( int > 'a > unit ) > 'a gen > unit
Iterate on elements with their index in the gen, from 0, consuming it.
val length : _ gen > int
Length of an gen (linear time), consuming it
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.
Append the two gens; the result contains the elements of the first, then the elements of the second gen.
val flatten : 'a GenLabels_intf.gen gen > 'a gen
Flatten the generator of generators
val flat_map : f:( 'a > 'b GenLabels_intf.gen ) > 'a gen > 'b gen
Monadic bind; each element is transformed to a subgen which is then iterated on, before the next element is processed, and so on.
val mem : ?eq:( 'a > 'a > bool ) > x:'a > 'a gen > bool
Is the given element, member of the gen?
val nth : int > 'a gen > 'a
nth 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 (110) > to_list
will return 1;3;5;7;9
Filter out elements that do not satisfy the predicate.
Take elements while they satisfy the predicate. The initial generator itself is not to be used anymore after this.
val fold_while :
f:( 'a > 'b > 'a * [ `Stop  `Continue ] ) >
init:'a >
'b gen >
'a
Fold elements until ('a, `Stop
) is indicated by the accumulator.
Drop elements while they satisfy the predicate. The initial generator itself should not be used anymore, only the result of drop_while
.
Maps some elements to 'b, drop the other ones
partition p l
returns the elements that satisfy p
, and the elements that do not satisfy p
val for_all : f:( 'a > bool ) > 'a gen > bool
Is the predicate true for all elements?
val exists : f:( 'a > bool ) > 'a gen > bool
Is the predicate true for at least one element?
val min : ?lt:( 'a > 'a > bool ) > 'a gen > 'a
Minimum element, according to the given comparison function.
Lexicographic comparison of generators. If a generator is a prefix of the other one, it is considered smaller.
val find : f:( 'a > bool ) > 'a gen > 'a option
find p e
returns the first element of e
to satisfy p
, or None.
val sum : int gen > int
Sum of all elements
Multiple iterators
Map on the two sequences. Stops once one of them is exhausted.
Iterate on the two sequences. 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)
Complex combinators
val merge : 'a GenLabels_intf.gen gen > 'a gen
Pick elements fairly in each subgenerator. The merge of gens e1, e2, ...
picks elements in e1
, e2
, in e3
, 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
.
Intersection of two sorted sequences. Only elements that occur in both inputs appear in the output
Merge two sorted sequences into a sorted sequence
Sorted merge of multiple sorted sequences
val tee : ?n:int > 'a gen > 'a GenLabels_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 gen > 'a GenLabels_intf.gen list
Split the gen into n
generators in a fair way. Elements with index = k mod n
with go to the kth gen. n
default value is 2.
interleave a b
yields an element of a
, then an element of b
, and so on. When a generator is exhausted, this behaves like the other generator.
Put the separator element between all elements of the given gen
Cartesian product, in no predictable order. Works even if some of the arguments are infinite.
Group equal consecutive elements together.
Remove consecutive duplicate elements. Basically this is like fun e > map List.hd (group e)
.
Sort according to the given comparison function. The gen must be finite.
Sort and remove duplicates. The gen must be finite.
chunks n e
returns a generator of arrays of length n
, composed of successive elements of e
. The last array may be smaller than n
Combinations of given length. The ordering of the elements within each combination is unspecified. Example (ignoring ordering): combinations 2 (13) > to_list = [[1;2]; [1;3]; [2;3]]
All subsets of the gen (in no particular order). The ordering of the elements within each subset is unspecified.
Basic conversion functions
val of_list : 'a list > 'a gen
Enumerate elements of the list
val to_list : 'a gen > 'a list
non tailcall trasnformation to list, in the same order
val to_rev_list : 'a gen > 'a list
Tail call conversion to list, in reverse order (more efficient)
val to_array : 'a gen > 'a array
Convert the gen to an array (not very efficient)
val of_array : ?start:int > ?len:int > 'a array > 'a gen
Iterate on (a slice of) the given array
val of_string : ?start:int > ?len:int > string > char gen
Iterate on bytes of the string
val to_string : char gen > string
Convert into a string
val rand_int : int > int gen
Random ints in the given range.
val int_range : ?step:int > int > int > int gen
int_range ~step a b
generates integers between a
and b
, included, with steps of length step
(1 if omitted). a
is assumed to be smaller than b
. step
must not be null, but it can be negative for decreasing integers.
module Infix : sig ... end
val () : int > int > int gen
Synonym for int_range ~by:1
val (>>=) : 'a gen > ( 'a > 'b GenLabels_intf.gen ) > 'b gen
Monadic bind operator
val pp :
?start:string >
?stop:string >
?sep:string >
?horizontal:bool >
( Format.formatter > 'a > unit ) >
Format.formatter >
'a gen >
unit
Pretty print the content of the generator on a formatter.
Restartable generators
module Restart : sig ... end
Utils
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.
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: see GenMList.of_gen_lazy
.
peek g
transforms the generator g
into a generator of x, Some next
if x
was followed by next
in g
, or x, None
if x
was the last element of g
peek_n ~n g
iterates on g
, returning along with each element the array of the (at most) n
elements that follow it immediately
Create a new transient generator. start gen
is the same as gen ()
but is included for readability.
Basic IO
Very basic interface to manipulate files as sequence of chunks/lines.
module IO : sig ... end