Generator Utilities

8.12

Generator Utilities🔗ℹ

Siddhartha Kasivajhula

Primitives and utilities for working with generators.

This module provides general-purpose utilities to achieve standard "list-like" transformations with generators without losing the laziness and constant-memory guarantees that generators provide. Alternative bindings for many of those found in racket/generator are included here, so that importing both is generally not necessary.

This module additionally provides a generic interface gen:generator representing a generator, as well as a particular generator type gen implementing that interface. The former allows supporting generator semantics in custom types and the latter is a rich generator type usable as a drop-in replacement for built-in generators, which comes with some conveniences.

Caveat: These utilities are not suitable for use with coroutines, i.e. in cases where there is bidirectional communication with a generator. This is because the utilities wrap underlying generators with intermediary ones in some cases, and values sent to them are not conveyed to the underlying generators.

1 Constructors🔗ℹ

struct
(struct gen (primitive))
primitive : generator?

A type representing a generator. All generators returned by this module are of this type, and they function identically to built-in generators, except that this type also implements gen:collection, enabling convenient construction using the generic construction operator :.

primitive - An underlying generator object, which would typically be a built-in generator, but could also be a gen.

Examples:

> (define g1 (: 1 2 (generator-null)))
> (define g2 (: 3 4 5 g1))
> (g2)
3
> (g2)
4
> (g2)
5
> (g2)
1
> (g2)
2

procedure
(generator-null [return]) → generator?
  return : any/c = (void)
procedure
(generator-cons v g) → generator?
  v : any/c
  g : generator?
procedure
(make-generator v ...) → generator?
  v : any/c

Constructors for generators, analogous to null, cons, and list for lists. generator-null serves as the null constructor as well as the identity value in composing generators, while generator-cons constructs a new generator from an arbitrary value and an existing generator. make-generator is a variadic constructor analogous to list. If a return value is provided to generator-null, it is used as the return value of the generator once it is exhausted – that is, as the return value for any generator with this empty generator instance at its tail.

Note that these constructors are not lazy. In order to construct a generator from a sequence lazily, use generate instead.

These constructors could either be used directly or via the generic construction operator : – see gen for examples of this.

Examples:

> (define g (generator-cons 1 (generator-null)))
> (g)
1
> (void? (g))
#t
> (define g (generator-cons 1 (generator-null 23)))
> (g)
1
> (g)
23
> (define g (make-generator 1 2 3))
> (g)
1
> (->list (in-producer g (void)))
'(2 3)

2 Syntax🔗ℹ

syntax
(generator formals body ...)

Identical to generator except that it produces a gen rather than a built-in generator type. This module also re-provides the yield procedure from racket/generator, so importing that module is unnecessary in many common cases.

3 Predicates🔗ℹ

procedure
(generator-done? g) → boolean?
g : generator?
procedure
(generator-empty? g) →
boolean? generator?
g : generator?

Predicates to assert whether a generator is "empty" or "done." generator-empty? is a statement about the "contents" of the generator, whereas generator-done? is a statement about the "state" of the generator. This distinction is made because Racket generators evaluate to two different kinds of values – first, the values that are yielded from within the generator, and second, the return value of the generator which is not explicitly yielded. For the purposes of this interface, the yielded values are treated as the contents of the generator. Thus, if a generator yields no further values but nevertheless evaluates to a nontrivial return value, it is still considered empty. Explicitly, generator-done? is equivalent to (eq? 'done (generator-state g)). A generator that has exhausted all of its values but has not yet evaluated its return value is empty but not done.

generator-empty? returns both a boolean value indicating whether the generator is empty or not, as well as a fresh generator intended to supplant the original generator in the calling context. This is necessary because checking for emptiness requires invoking the generator to inspect the first element, which mutates the original generator. The returned generator is equivalent to the original generator prior to the mutation, modulo the aforementioned caveat about coroutines.

In general, favor using generator-done?.

Examples:

> (define g (make-generator))
> (generator-done? g)
#f
> (define-values (is-empty? g) (generator-empty? g))
> is-empty?
#t
> (generator-done? g)
#f
> (g)
> (generator-done? g)
#t

procedure
(generator-peek g) →
any/c generator?
g : generator?

"Peek" at the first value in the generator without modifying it. Of course, inspecting the first element in a generator must necessarily modify it. To preserve the illusion that no mutation has taken place, a generator equivalent to the original one prior to mutation is returned along with the peeked-at value. This returned generator is expected to be used in place of the original one in the calling context as it will be functionally equivalent to the original one, modulo the aforementioned caveat about coroutines. Additionally, peeking does not protect against invocation side-effects. If invoking g results in a side-effect, that would still happen if you peek at it. But it won’t happen a second time since the replacement generator only includes the return value from the original invocation, and not the side effect.

Examples:

> (define g (make-generator 1 2 3))
> (define-values (v g) (generator-peek g))
> v
1
> (g)
1
> (g)
2
> (g)
3

4 Utilities🔗ℹ

procedure
(generator-map f g) → generator?
f : (-> any/c any/c)
g : generator?

Analogous to map, returns a fresh generator whose values are the elements of g transformed under f.

Examples:

> (define g (make-generator 1 2 3))
> (define g (generator-map add1 g))
> (g)
2
> (g)
3
> (g)
4

procedure
(generator-filter f g) → generator?
f : (-> any/c boolean?)
g : generator?

Analogous to filter, returns a fresh generator whose values are the elements of g for which the predicate f is true.

Examples:

> (define g (make-generator 1 2 3 4 5))
> (define g (generator-filter odd? g))
> (g)
1
> (g)
3
> (g)
5

procedure
(generator-fold f g [base #:order order]) → generator?
  f : procedure?
  g : generator?
  base : any/c = undefined
  order : (one-of/c 'abb 'bab) = 'abb

Analogous to fold, returns a fresh generator whose values are the steps in the aggregation of the elements of g under the folding function f.

Examples:

> (define g (make-generator 1 2 3 4))
> (define g (generator-fold + g))
> (g)
1
> (g)
3
> (g)
6
> (g)
10

procedure
(generator-append a b) → generator?
a : generator?
b : generator?

Analogous to append, returns a fresh generator whose values are the elements of a followed by the elements of b.

Examples:

> (define a (make-generator 1 2))
> (define b (make-generator 3 4))
> (define g (generator-append a b))
> (g)
1
> (g)
2
> (g)
3
> (g)
4

procedure
(generator-cycle g [stop]) → generator?
g : generator?
stop : any/c = (void)

Analogous to cycle, returns an infinite generator whose values are the elements of g, repeated when exhausted. If a stop value is provided, the elements are drawn from g until stop is encountered. This utility uses memory proportional to the size of the repeated sequence.

Examples:

> (define g (generator-cycle (make-generator 1 2 3)))
> (g)
1
> (g)
2
> (g)
3
> (g)
1
> (g)
2

procedure
(generator-repeat v) → generator?
v : any/c

Analogous to repeat, returns an infinite generator whose values are v repeated indefinitely.

Examples:

> (define g (generator-repeat 5))
> (g)
5
> (g)
5
> (g)
5

procedure
(generator-zip g ...) → generator?
  g : generator?
procedure
(generator-zip-with f g ...) → generator?
  f : procedure?
  g : generator?

Analogous to zip-with, generator-zip-with returns a fresh generator whose values are the elements of the input generators combined using the function f. f must accept a number of arguments equal to the number of provided generators. generator-zip simply combines the generator values using list. The generation stops when one of the input generators runs out of values.

Examples:

> (define a (make-generator 1 2))
> (define b (make-generator 'a 'b))
> (define c (make-generator 'A 'B))
> (define g (generator-zip a b c))
> (g)
'(1 a A)
> (g)
'(2 b B)
> (define a (make-generator 1 2))
> (define b (make-generator 1 2))
> (define c (make-generator 1 2))
> (define g (generator-zip-with + a b c))
> (g)
3
> (g)
6

procedure
(generator-interleave g ...) → generator?
g : generator?

Returns a fresh generator whose values are the elements of the input generators taken in turn, one at a time. The generation stops when one of the input generators runs out of values.

Examples:

> (define g (generator-interleave (make-generator 1 2 3) (make-generator 4 5 6)))
> (g)
1
> (g)
4
> (g)
2
> (g)
5
> (g)
3
> (g)
6

procedure
(generator-join g) → generator?
g : generator?

Returns a fresh generator whose values are the elements of g "flattened" by one level.

Examples:

> (define g (make-generator (list 1) (list 2) (list 3)))
> (define g (generator-join g))
> (g)
1
> (g)
2
> (g)
3

procedure
(generator-flatten g) → generator?
g : generator?

Returns a fresh generator whose values are the "flattened" elements of g. This is equivalent to repeatedly applying generator-join until the values are no longer sequences.

Examples:

> (define g (make-generator (list (list (list 1))) (list (list (list 2))) (list (list (list 3)))))
> (define g (generator-flatten g))
> (g)
1
> (g)
2
> (g)
3

procedure
(yield-from g) → any
g : generator?

Yield all values from a provided generator. This should only be used inside a generator.

Examples:

> (define g (generator () (yield-from (make-generator 1 2 3))))
> (g)
1
> (g)
2
> (g)
3

5 Transformers🔗ℹ

procedure
(generate seq [return]) → generator?
seq : sequence?
return : any/c = (void)

Returns a generator that generates seq. See ->generator for some considerations here.

To go in the "other direction" and transform a generator into a sequence, use in-producer.

Examples:

> (define g (generate (range 5 10)))
> (g)
5
> (g)
6
> (g)
7
> (define g (generate "apple"))
> (g)
#\a
> (g)
#\p
> (g)
#\p

procedure
(in-producer g [stop] v ...) → sequence?
  g : generator?
  stop : any/c = undefined
  v : any/c

Transform a generator into a sequence. Similar to in-producer, but returns a data/collection sequence? rather than a built-in sequence?.

To go in the "other direction" and transform a sequence into a generator, use generate.

Examples:

> (define g (make-generator 1 2 3))
> (->list (in-producer g (void)))
'(1 2 3)

6 Interface🔗ℹ

value
gen:generator : any/c

A generic interface for generators that encompasses built-in generators but also enables providing generator semantics in custom types.

Examples:

> (struct api-reader (source)
    #:transparent
    #:property prop:procedure
    (λ (self)
      ((api-reader-source self)))
    #:methods gen:generator
    [(define/generic -generator-state generator-state)
     (define (generator-state st)
       (-generator-state (api-reader-source source)))])
> (define g (api-reader (make-generator 1 2 3)))
> (g)
1
> (->list (in-producer g (void)))
'(2 3)

To implement this interface for custom types, the following method needs to be implemented:

procedure
(generator-state v)
→ [symbol? (one-of/c 'fresh 'suspended 'running 'done)]
v : generator?

Describes the state of the generator. The implementation should mirror generator-state.

procedure
(generator? v) → boolean?
v : any/c

Predicate to check if a value is a generator. Like generator? but also recognizes instances of gen:generator.

Examples:

> (generator? 3)
#f
> (generator? (generator () (void)))
#t
> (generator? (generator-cons 1 (generator-null)))
#t

1	Constructors
2	Syntax
3	Predicates
4	Utilities
5	Transformers
6	Interface