12 Generators

(require (planet untyped/unlib/generator))

There is no doubt that lists are useful structures for representing many kinds of data, and that folds and maps are a quick, convenient way of performing arbitrary bits of list manipulation.

The main problem with the list/fold/map approach is the number of temporary lists generated in the process, which can take up a large amount of memory.

Generators are a half-way-house between lists and streams that aim to reduce memory overhead when large data sources are involved.

A generator is a stream-like accessor that can be repeatedly called to return new values from its source. A special "generator-end" value is returned to indicate that the source has been exhausted.

This module provides convenient ways of:

• producing generators from lists;

• combining generators to form other generators (c.f. fold, map and so on);

• accumulating results from generators (e.g. back into lists).

Many of the procedures defined in this module have rather unwieldy names. "gen.ss" exports versions of these procedures with shorter names: see Generators (short names) for more information.

generator-end : symbol?

A unique symbol that indicates a generator has finished producing values.

(generator-end? item) → boolean?

item : any

Predicate that recognizes generator-end.

(gen-> value-contract) → flat-contract?

value-contract : flat-contract?

Syntax that expands into a contract that is satisfied by generator procedures that produce values that satisfy value-contract or generator-end?.

(list->generator lis) → (gen-> a)

lis : (listof a)

Creates a generator that generates the values in lis.

Examples:

> (define gen       (list->generator '(1 2)))

> (gen)

1

> (gen)

2

> (gen)

generator-end1342

(range->generator start [end step]) → (gen-> integer?)

start : integer?

end : (U integer? #f) = #f

step : integer? = 1

Creates a generator that generates the values in the range of integers from start (inclusive) to end (exclusive), incrementing each time by step.

The generator stops when the current value passes end in the direction determined by step. end itself is considered a terminating value.

Examples:

> (define gen       (range->generator 1 5 2))

> (gen)

1

> (gen)

3

> (gen)

generator-end1342

(in-generator gen) → (sequence? arg)

gen : (gen-> arg)

Returns a sequence covering the values of a generator.

Examples:

> (define gen       (range->generator 1 5 2))

> (for/list ([val (in-generator gen)])               val)

(1 3)

(generator-map fn gen1 gen2 ...) → (gen-> ans)

fn : (arg1 arg2 ... -> ans)

gen1 : (gen-> arg1)

gen2 : (gen-> arg2)

The generator equivalent of map. Creates a generator that returns:

  (apply fn (list (gen1) (gen2) ...))

The new generator ends as soon as any of gen1 gen2 ... end.

Examples:

> (define gen       (generator-map +                      (list->generator '(1 2))                      (list->generator '(2 3))))

> (gen)

3

> (gen)

5

> (gen)

generator-end1342

(generator-fold-map   fn             initial-seed             gen1             gen2 ...)   →   seed

fn : (arg1 arg2 ... seed -> seed)

initial-seed : seed

gen1 : (gen-> arg1)

gen2 : (gen-> arg2)

A generator equivalent of fold. The new generator returns the values of seed for each application of fn, stopping when any of the source generators stop.

Examples:

> (define gen       (generator-fold-map + 0 (list->generator '(1 2))))

> (gen)

1

> (gen)

3

> (gen)

generator-end1342

(generator-filter pred src) → (gen-> arg)

pred : (arg -> boolean?)

src : (gen-> arg)

Creates a generator that generates the values from src for which pred returns non-#f.

Examples:

> (define gen       (generator-filter even? (list->generator '(1 2 3 4 5))))

> (gen)

2

> (gen)

4

> (gen)

generator-end1342

(generator-filter-map fn src) → (gen-> ans)

fn : (arg -> (U ans #f))

src : (gen-> arg)

Creates a generator that generates the non-#f values of (fn (src)).

Examples:

> (define (test val)       (memq val '(2 4 6)))

> (define gen       (generator-filter-map test (list->generator '(1 2 3 4 5))))

> (gen)

(2 4 6)

> (gen)

(4 6)

> (gen)

generator-end1342

(generator-remove-duplicates src [same?]) → (gen-> a)

src : (gen-> a)

same? : (a a -> boolean?) = equal?

Creates a generator that filters out values from src that occur more than once in succession. The optional argument same? is used to test equality.

Examples:

> (define gen       (generator-remove-duplicates (list->generator '(1 2 2 3 3 3))))

> (gen)

1

> (gen)

2

> (gen)

3

> (gen)

generator-end1342

(generator-for-each fn gen1 gen2 ...) → void?

fn : (arg1 arg2 ... -> void)

gen1 : (gen-> arg1)

gen2 : (gen-> arg2)

Repeatedly applies fn for its side-effects to values form source generators gen1 gen2 ... until one or more sources is exhausted.

Example:

> (generator-for-each display (list->generator '(1 2 3)))

123

(generator-fold fn initial-seed gen1 gen2 ...) → seed

fn : (arg1 arg2 ... seed -> seed)

initial-seed : seed

gen1 : (gen-> arg1)

gen2 : (gen-> arg2)

Like generator-fold-map but only the result of the final application of fn is returned.

Example:

> (generator-fold + 0 (list->generator '(1 2 3)))

6

(generator->list src) → (listof a)

src : (gen-> a)

A convenience form of generator-fold that collects the generated values into a list (in the order generated).

Example:

> (generator->list (list->generator '(1 2 3)))

(1 2 3)

(generator->hash   src             item->key            [ item->val             initial-hash])   →   (hashof b c)

src : (gen-> a)

item->key : (a -> b)

item->val : (a -> c) = (lambda (a) a)

initial-hash : (hashof b c) = (make-hash)

Similar to generator->list but collects the generated values into a hash table. item->key an item->val control how generated items are turned into keys and values in the hash. initial-hash lets you specify the (mutable) hash table to use for the collection (useful for switching to a hash table that uses eq? as a comparison function).

Example:

> (hash-map (generator->hash (list->generator '(2 4 6)) (lambda (x) (/ x 2)))               (lambda (key val)                 (list key val)))

((2 4) (1 2) (3 6))

(generator-project mask src [same?])

→ (gen-> (list any ... (listof (listof any))))

mask : (listof boolean)

src : (gen-> (listof any))

same? : [(any any -> boolean)] = eq?

Does the equivalent of a projection (from relational algebra) on the values returned by src. #t values in mask correspond (by position) to "key" values in values from src, while #f values correspond to "nonkey" values.

src is polled once and the members returned are partitioned into keys and nonkeys and stored. src is then polled repeatedly until it returns a list where the keys differ from those stored. At this point, the generator emits a list of the matching keys and a list of the lists of nonkeys:

  (list key ... (listof (list nonkey ...)))

The optional same? argument is the predicate used to check key equality.

generator-project is useful (in conjunction with generator-map, map and match-lambda) for iterating over sets of related results returned by database queries.

Examples:

> (define src       (list->generator (list (list "0" "0" "0" "0")                              (list "0" "0" "0" "1")                              123                              (list "0" "1" "0" "0")                              (list "0" "1" "0" "1")                              456)))

> (define gen (generator-project (list #t #t #f #f) src equal?))

> (gen)

("0" "0" (("0" "0") ("0" "1")))

> (gen)

123

> (gen)

("0" "1" (("0" "0") ("0" "1")))

> (gen)

456

> (gen)

generator-end1342

(generator-debug message src) → (gen-> a)

message : string?

src : (gen-> a)

Creates a generator that calls debug on each value generated.

Examples:

> (define gen       (generator-debug "message" (list->generator '(1 2))))

> (gen)

message 1

1

> (gen)

message 2

2

> (gen)

message generator-end1342

generator-end1342