Generator Utilities
1 Primitives
generator-null
generator-cons
make-generator
generator-done?
generator-empty?
generator-peek
2 Utilities
generator-map
generator-filter
generator-fold
generator-append
generator-cycle
generator-repeat
generator-zip
generator-zip-with
generator-interleave
generator-join
generator-flatten
yield-from
generate
3 Interface
gen:  generator
generator-state
generator?
in-producer
7.8

Generator Utilities

Siddhartha Kasivajhula

 (require generator-util) package: generator-util

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.

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 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.

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

2 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

procedure

(generate seq [return])  generator?

  seq : sequence?
  return : any/c = (void)
Returns a generator that generates seq. This is an alias for ->generator.

Examples:
> (define g (generate (range 5 10)))
> (g)

5

> (g)

6

> (g)

7

> (define g (generate "apple"))
> (g)

#\a

> (g)

#\p

> (g)

#\p

3 Interface

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 (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:

procedure

(in-producer g [stop] v ...)  sequence?

  g : generator?
  stop : any/c = undefined
  v : any/c
Similar to in-producer, but returns 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)