# SRFI 121 - Generators

Defines utility procedures that create, transform and consume generators. A
'generator' is a procedure with no arguments (a 'thunk') that works as a source
of values. Every time a generator is called, it yields a value.

Generators may be finite or infinite; a finite generator returns an end-of-file
object to indicate that it is exhausted (has no more values to give). For
example, ``read-char``, ``read-line`` and ``read`` are generators that produce
characters, lines and objects from the current input port. 

This library is designed to provide lightweight laziness.

See the [SRFI document][http://srfi.schemers.org/srfi-121/srfi-121.html] for more information.

## Definitions

Generators can be divided into two classes: *finite* and *infinite*. Both kinds
of generator can be invoked an indefinite number of times. After a finite
generator has produced all of its values, it will return an end-of-file object
for all subsequent calls. A generator is said to be *exhausted* if calling it
will return an end-of-file object. By definition, an infinite generator can
never be exhausted.

A generator is said to be in an *undefined state* if it cannot be determined how
many values it has produced. This arises because it is impossible to tell by
inspection whether a generator is exhausted or not. For example,
``(generator-fold + 0 (generator 1 2 3) (generator 1 2))`` will compute 0 + 1 +
1 + 2 + 2 = 6, at which time the second generator will be exhausted. If the
first generator is invoked, however, it may return either 3 or an end-of-file
object, depending on whether the implementation of ``generator-fold`` invoked it
or not. Therefore, the first generator is said to be in an undefined state.

Functions provided under [generator operations](#generator-operations) do not
consume elements from their input generators. In general, they produce finite
generators if their inputs are finite.

Functions provided udner [consuming generated
values](#consuming-generated-values) consume all values from any generator
passed to them, and will not return if any of their arguments are infinite.

## Generator constructors
[`generator`](#generator)
[`make-iota-generator`](#make-iota-generator)
[`make-range-generator`](#make-range-generator)
[`make-coroutine-generator`](#make-coroutine-generator)
[`list->generator`](#list-generator)
[`vector->generator`](#vector-generator)
[`reverse-vector->generator`](#reverse-vector-generator)
[`string->generator`](#string-generator)
[`bytevector->generator`](#bytevector-generator)
[`make-for-each-generator`](#make-for-each-generator)
[`make-unfold-generator`](#make-unfold-generator)

## Generator operations
[`gcons*`](#gcons)
[`gappend`](#gappend)
[`gcombine`](#gcombine)
[`gfilter`](#gfilter)
[`gremove`](#gremove)
[`gtake`](#gtake)
[`gdrop`](#gdrop)
[`gtake-while`](#gtake-while)
[`gdrop-while`](#gdrop-while)
[`gdelete`](#gdelete)
[`gdelete-neighbor-dups`](#gdelete-neighbor-dups)
[`gindex`](#gindex)
[`gselect`](#gselect)

## Consuming generated values
[`generator->list`](#generator-list)
[`generator->reverse-list`](#generator-reverse-list)
[`generator->vector`](#generator-vector)
[`generator->vector!`](#generator-vector!)
[`generator->string`](#generator-string)
[`generator-fold`](#generator-fold)
[`generator-for-each`](#generator-for-each)
[`generator-find`](#generator-find)
[`generator-count`](#generator-count)
[`generator-any`](#generator-any)
[`generator-every`](#generator-every)
[`generator-unfold`](#generator-unfold)

# generator

    (generator arg ...)

Returns a generator which produces each of this function's arguments in turn.
When given no arguments, returns an empty generator which provides no values.

# make-iota-generator

    (make-iota-generator count)
    (make-iota-generator count start)
    (make-iota-generator count start step)

Returns a finite generator which produces a sequence of ``count`` numbers. The
sequence begins with ``start`` (default 0) and increases by ``step`` (default
1). If both ``start`` and ``step`` are exact, the generator produces exact
values; otherwise, it produces inexact ones. The exactness of ``count`` does not
affect the exactness of results.

Example: ``(generator->list (make-iota-generator 3 8))`` => (8 9 10)``

# make-range-generator

    (make-range-generator start)
    (make-range-generator start end)
    (make-range-generator start end step)

Returns a generator which produces a sequence of numbers. The sequence begins
with ``start``, increases by ``step`` (default 1), and continues while the
number is less than ``end``, or forever if ``end`` is not provided. If both
``start`` and ``step`` are exact, the generator produces exact values;
otherwise, it produces inexact ones. The exactness of ``end`` does not affect
the exactness of the results.

Example: ``(generator->list (make-range-generator 3) 4) => (3 4 5 6)``

# make-coroutine-generator

    (make-coroutine-generator proc)

Creates a generator from a coroutine. The ``proc`` argument should be a
procedure that takes a single argument ``yield``. When called,
``make-coroutine-generator`` immediately returns a generator ``g``. When ``g``
is called, ``proc`` runs until it calls ``yield``. Calling ``yield`` causes the
execution of ``proc`` to be suspended, and ``g`` returns the value passed to
``yield``.

Whether ``g`` is finite or infinite depends on the behaviour of ``proc``: if
``proc`` returns, it is the end of the sequence, and ``g`` will return an
end-of-file object from then on. The return value of ``proc`` is ignored.

# list->generator

    (list->generator lis)

Returns a generator that produces each element of the list ``lis`` in turn.
Mutating ``lis`` will affect the results of the generator.

``list->generator`` and ``generator->list`` (when given no arguments) are 
inverses up to ``equal?``; thus, for any list ``x``, 
``(equal? x (generator->list (list->generator x))) => #t``.

# vector->generator

    (vector->generator vec)
    (vector->generator vec start)
    (vector->generator vec start end)

Returns a generator that produces elements of ``vec``, in turn, from the index
``start`` (inclusive, default 0) to ``end`` (exclusive, default 
``(vector-length vec)``). Mutating ``vec`` will affect the results of the 
generator.

When given no arguments, ``vector->generator`` and ``generator->vector`` are
inverses up to ``equal?``; thus, for any vector ``x``, ``(equal? x
(generator->vector (vector->generator x))) => #t``.

# reverse-vector->generator

    (reverse-vector->generator vec)
    (reverse-vector->generator vec start)
    (reverse-vector->generator vec start end)

Returns a generator that produces elements of ``vec``, in turn, from ``end``
(exclusive, default ``(vector-length vec)``) to ``start`` (inclusive, default
0), in reverse order of indices. Mutating ``vec`` will affect the results of the
generator.

# string->generator

    (string->generator str)
    (string->generator str start)
    (string->generator str start end)

Returns a generator that produces characters of ``str``, in turn, from ``start``
(inclusive, default 0) to ``end`` (exclusive, default ``(string-length str)``).
Mutating ``str`` will affect the results of the generator.

When given no arguments, ``string->generator`` and ``generator->string`` are
inverses up to ``string=?``; thus, for any string ``s``, ``(string=? s
(generator->string (string->generator s))) => #t``.

# bytevector->generator

    (bytevector->generator bv)
    (bytevector->generator bv start)
    (bytevector->generator bv start end)

Returns a generator that produces bytes of ``bv``, in turn, from ``start``
(inclusive, default 0) to ``end`` (exclusive, default ``(bytevector-length
bv)``). Mutating ``bv`` will affect the results of the generator.

# make-for-each-generator

    (make-for-each-generator for-each obj)

Constructs a generator over any collection ``obj``, using a ``for-each``
procedure appropriate to ``obj``. This must be a procedure that, when called as
``(for-each proc obj)`` calls ``proc`` on each element of ``obj``. Examples of
such procedures are ``for-each``, ``string-for-each`` and ``vector-for-each``.
The value returned by ``for-each`` is ignored. The generator is finite if the
collection is finite.

``obj`` need not be a conventional one (such as a string, list, etc), as long as
``for-each`` can invoke a procedure on everything that counts as a member.

# make-unfold-generator

    (make-unfold-generator stop? mapper successor seed)

A generator similar to [SRFI 1][2]'s ``unfold``. 

The ``stop?`` predicate takes a seed value and determines whether to stop. The 
``mapper`` procedure calculates a value to be returned by the generator from a 
seed value. The ``successor`` procedure calculates the next seed value from 
the current seed value.

For each call of the resulting generator, ``stop?`` is called with the current
seed value. If it returns true, then the generator returns an end-of-file
object. Otherwise, it applies ``mapper`` to the current seed value to get the
value to return, and uses ``successor`` to update the seed value.

The generator is finite unless ``stop?`` is a constant function returning
``#f``.

# gcons\*

    (gcons\* item ... gen)

Returns a generator that adds ``item ...`` in front of ``gen``. Once each of
``item ...`` has been produced, the generator is guaranteed to tail-call
``gen``.

# gappend

    (gappend gen ...)

Returns a generator that yields the items from the first argument generator, and
once it is exhausted, the second generator, and so forth.

If any of the argument generators are infinite, subsequent argument generators
will never be asked to produce any values.

# gcombine

    (gcombine proc seed gen gen2 ...)

Returns a generator for mapping with state. It produces a sequence of sub-folds
over ``proc``.

The ``proc`` argument is a procedure that takes as many arguments as there are
argument generators, plus one. It is called as ``(proc v1 v2 ... seed)``, where
``v1 v2 ...`` are the values produced by the argument generators, and ``seed``
is the current seed value. It must return two values: the produced value and the
next seed. The generator is exhausted when any of its argument generators are
exhausted, at which time, the remaining argument generators are in an undefined
state.

# gfilter

    (gfilter pred gen)

Returns a generator that produces items from ``gen``, except those for which
``pred`` would return ``#f``.

# gremove

    (gremove pred gen)

Equivalent to ``(gfilter (lambda (x) (not (pred x))) gen)``.

# gtake

    (gtake gen k)
    (gtake gen k padding)

A generator analogue to [SRFI 1][2]'s ``take``. Returns a generator that
produces (at most) the first ``k`` items of ``gen``. If ``gen`` is exhausted
before it can produce ``k`` items, the rest will be made up by producing the
``padding`` value.

# gdrop

    (gdrop gen k)

A generator analogue to [SRFI 1][2]'s ``drop``. Returns a generator that
skips the first (at most) ``k`` items of ``gen``, then produces the rest. If
``k`` is greater than, or equal to, the total number of items ``gen`` could
produce, an empty generator is produced instead.

# gtake-while

    (gtake-while pred gen)

A generator analogue to [SRFI 1][2]'s ``take-while``. Returns a generator that
produces values from ``gen`` until ``pred`` returns ``#f`` on a value.

# gdrop-while

    (gdrop-while pred gen)

A generator analogue to [SRFI 1][2]'s ``drop-while``. Returns a generator that
discards values from ``gen`` until ``pred`` returns ``#t`` for a value, and then
produces values from ``gen``.

# gdelete

    (gdelete item gen)
    (gdelete item gen =)

Returns a generator which produces the same items as ``gen``, except any items
that are the same as ``item`` up to ``=``, which defaults to ``equal?``. ``=``
is passed exactly two arguments, one of which is the value produced by ``gen``.

# gdelete-neighbor-dups

    (gdelete-neighbor-dups gen)
    (gdelete-neighbor-dups gen =)

Returns a generator which produces the same items as ``gen``, except any items
that are the same as the preceding items up to ``=``, which defaults to
``equal?``. ``=`` is passed exactly two arguments; the first of which is
produced by ``gen`` before the second.

# gindex

    (gindex value-gen index-gen)

Returns a generator that produces elements of ``value-gen`` specified by the
indices (non-negative exact integers) produced by ``index-gen``. It is an error
if the indices are not strictly increasing, or if any index exceeds the number
of elements produced by ``value-gen``. The generator is exhausted when either of
``value-gen`` or ``index-gen`` is exhausted, at which time the other is in an
undefined state.

# gselect

    (gselect value-gen truth-gen)

Returns a generator that produces elements of ``value-gen`` that correspond to
the values produced by ``truth-gen``. If the current value of ``truth-gen`` is
true, the current value of ``value-gen`` is produced; otherwise, the value is
skipped. The generator is exhausted when either of ``value-gen`` or
``truth-gen`` is exhausted, at which time the other is in an undefined state.

# generator->list

    (generator->list gen)
    (generator->list gen k)

Calls ``gen`` repeatedly to produce its values, then collects them into a list
and returns them. If ``k`` is omitted, ``gen`` will be asked to produce values
until it is exhausted; otherwise, only at most ``k``-many values will be
requested. It is an error for ``k`` to be anything other than a non-negative
integer.

# generator->reverse-list

    (generator->reverse-list gen)
    (generator->reverse-list gen k)

As ``generator->list``, but the returned list is in reverse order.

# generator->vector

    (generator->vector gen)
    (generator->vector gen k)

As ``generator->list``, but the returned result is a vector.

# generator->vector!

    (generator->vector! vec at gen)

Calls ``gen`` repeatedly to produce its values, and puts them into ``vec``,
starting at index ``at``, until ``vec`` is full or ``gen`` is exhausted. Returns
the number of elements produced from ``gen``.

# generator->string

    (generator->string gen)
    (generator->string gen k)

Calls ``gen`` repeatedly to produce characters, and returns a newly-allocated
string of them. It is an error if ``gen`` does not produce only characters. If
``k`` is omitted, the generator will be asked to produce characters until it is
exhausted; otherwise, at most ``k`` characters will be requested. It is an error
for ``k`` to be anything other than a non-negative integer.

# generator-fold

    (generator-fold proc seed gen1 gen2 ...)

An analogue of [SRFI 1][2]'s ``fold`` on values produced by the generator
arguments.

When one generator argument ``gen`` is given, for each value ``v`` produced by 
``gen``, ``proc`` is called as ``(proc v r)``, where ``r`` is the current
accumulated result; the initial value of ``r`` is ``seed``, and the return value
from ``proc`` becomes the new accumulated result. When ``gen`` is exhausted, the
accumulated result at the time is returned.

When more than one generator argument is given, ``proc`` is called on all the
values produced by all the generator arguments, followed by the current
accumulated result. The procedure returns when any of the generator arguments is
exhausted, at which time the others are in an undefined state.

# generator-for-each

    (generator-for-each proc gen1 gen2 ...)

A generator analogue of ``for-each`` that consumes produced values with side
effects. ``proc`` is repeatedly applied to values produced by all the generator
arguments, until any of them is exhausted. The values returned by ``proc`` are
discarded. The procedure terminates when any of the argument generators is
exhausted, at which time the others are in an undefined state.

# generator-find

    (generator-find pred gen)

Returns the first value produced by ``gen`` that satisfies the predicate
``pred``, or ``#f`` if no such value exists. If ``gen`` is infinite, this
procedure will not return if it cannot find an appropriate item.

# generator-count

    (generator-count pred gen)

Returns the number of values that gen can produce which satisfy the predicate
``pred``. This procedure will not return if ``gen`` is infinite.

# generator-any

    (generator-any pred gen)

Applies ``pred`` to each item produced by ``gen``. As soon as ``pred`` returns a
true value, the value is returned without consuming the rest of ``gen``. If
``gen`` is exhausted, returns ``#f``.

# generator-every

    (generator-every pred gen)

Equivalent to ``(not (generator-any (lambda (x) (not (pred x))) gen))``.

# generator-unfold

    (generator-unfold gen unfold arg ...)

Equivalent to ``(unfold eof-object? (lambda (x) x) (lambda (x) (gen)) arg
...)``, where ``unfold`` is the [SRFI 1][http://srfi.schemers.org/srfi-1/srfi-1.html] procedure of the same name.