13 Generators
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.
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: | ||
| ||
> (gen) | ||
1 | ||
> (gen) | ||
2 | ||
> (gen) | ||
generator-end1811 |
(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: | ||||
| ||||
> (gen) | ||||
3 | ||||
> (gen) | ||||
5 | ||||
> (gen) | ||||
generator-end1811 |
| ||||||||||||||||||||||||||||
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: | ||
| ||
> (gen) | ||
1 | ||
> (gen) | ||
3 | ||
> (gen) | ||
generator-end1811 |
(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: | ||
| ||
> (gen) | ||
2 | ||
> (gen) | ||
4 | ||
> (gen) | ||
generator-end1811 |
(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: | ||
| ||
| ||
> (gen) | ||
(2 4 6) | ||
> (gen) | ||
(4 6) | ||
> (gen) | ||
generator-end1811 |
(generator-remove-duplicates src [same?]) → (gen-> a) |
src : (gen-> a) |
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: | ||
| ||
> (gen) | ||
1 | ||
> (gen) | ||
2 | ||
> (gen) | ||
3 | ||
> (gen) | ||
generator-end1811 |
(generator-for-each fn gen1 gen2 ) → 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?]) |
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 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-end1811 |
(generator-debug message src) → (gen-> a) |
message : string? |
src : (gen-> a) |
Creates a generator that calls debug on each value generated.
Examples: | ||
| ||
> (gen) | ||
message 1 | ||
1 | ||
> (gen) | ||
message 2 | ||
2 | ||
> (gen) | ||
message generator-end1811 | ||
generator-end1811 |