16 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-end181

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

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

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

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

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

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

Examples:

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

Examples:

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

Examples:

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

(1 2 3)

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

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

generator-end181