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 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 consume all values from any generator passed to them, and will not return if any of their arguments are infinite.

Generator constructors

generator make-iota-generator make-range-generator make-coroutine-generator list->generator vector->generator reverse-vector->generator string->generator bytevector->generator make-for-each-generator make-unfold-generator

Generator operations

gcons* gappend gcombine gfilter gremove gtake gdrop gtake-while gdrop-while gdelete gdelete-neighbor-dups gindex gselect

Consuming generated values

generator->list generator->reverse-list generator->vector generator->vector! generator->string generator-fold generator-for-each generator-find generator-count generator-any generator-every 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.