Generator Utilities

7.7

top ← prev up next →

Generator Utilities

Siddhartha Kasivajhula

Primitives and utilities for working with generators.

This module provides general-purpose utilities to achieve standard sequence-style transformations with generators without losing the laziness and constant-memory guarantees that generators provide.

These utilities are not suitable for use in all cases. In particular, they are not suitable for use with coroutines – i.e. in cases where there is bidirectional communication with a generator. Some of the utilities below wrap underlying generators with intermediary ones, and values sent to them are not conveyed to the underlying generators.

1 Primitives

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, at least for the moment.

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 g)
'(2 3)

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.

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

2 Utilities

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

Analogous to map, yields 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, yields 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, yields 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, yields 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-zip g ...) → generator?
  g : generator?
procedure
(generator-zip-with f g ...) → generator?
  f : procedure?
  g : generator?

Analogous to zip-with, generator-zip-with yields 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.

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-join g) → generator?
g : generator?

Yields 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?

Yields 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

3 Interface

value
gen:generator : any/c

A generic interface for generators, that wraps 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 g)
(list (generator #<procedure:generator>))

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

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

Similar to in-producer, but yields a data/collection sequence? rather than a built-in sequence?.

Examples:

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

top ← prev up next →