#lang scribble/doc @(require (file "base.ss")) @title[#:tag "generator"]{Generators} @(define-eval gen-eval (planet untyped/unlib/generator)) @defmodule[(planet untyped/unlib/generator)]{ There is no doubt that lists are useful structures for representing many kinds of data, and that @scheme[fold]@schemeidfont{s} and @scheme[map]@schemeidfont{s} are a quick, convenient way of performing arbitrary bits of list manipulation. The main problem with the @scheme[list]/@scheme[fold]/@scheme[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: @itemize{ @item{producing generators from lists;} @item{combining generators to form other generators (c.f. @scheme[fold], @scheme[map] and so on);} @item{accumulating results from generators (e.g. back into lists).}} Many of the procedures defined in this module have rather unwieldy names. @filepath{gen.ss} exports versions of these procedures with shorter names: see @secref{gen} for more information. @defthing[generator-end symbol?]{ A unique symbol that indicates a generator has finished producing values.} @defproc[(generator-end? [item any]) boolean?]{ Predicate that recognizes @scheme[generator-end].} @defproc[(gen-> [value-contract flat-contract?]) flat-contract?]{ Syntax that expands into a contract that is satisfied by generator procedures that produce values that satisfy @scheme[value-contract] or @scheme[generator-end?].} @defproc[(list->generator [lis (listof a)]) (gen-> a)]{ Creates a generator that generates the values in @scheme[lis]. @examples[ #:eval gen-eval (define gen (list->generator '(1 2))) (gen) (gen) (gen)]} @defproc[(range->generator [start integer?] [end (U integer? #f) #f] [step integer? 1]) (gen-> integer?)]{ Creates a generator that generates the values in the range of integers from @scheme[start] (inclusive) to @scheme[end] (exclusive), incrementing each time by @scheme[step]. The generator stops when the current value passes @scheme[end] in the direction determined by @scheme[step]. @scheme[end] itself is considered a terminating value. @examples[ #:eval gen-eval (define gen (range->generator 1 5 2)) (gen) (gen) (gen)]} @defproc[(generator-map [fn (arg1 arg2 ... -> ans)] [gen1 (gen-> arg1)] [gen2 (gen-> arg2)] ...) (gen-> ans)]{ The generator equivalent of @scheme[map]. Creates a generator that returns: @schemeblock[(apply fn (list (gen1) (gen2) ...))] The new generator ends as soon as any of @scheme[gen1 gen2 ...] end. @examples[ #:eval gen-eval (define gen (generator-map + (list->generator '(1 2)) (list->generator '(2 3)))) (gen) (gen) (gen)]} @defproc[(generator-fold-map [fn (arg1 arg2 ... seed -> seed)] [initial-seed seed] [gen1 (gen-> arg1)] [gen2 (gen-> arg2)] ...) seed]{ A generator equivalent of @scheme[fold]. The new generator returns the values of @scheme[seed] for each application of @scheme[fn], stopping when any of the source generators stop. @examples[ #:eval gen-eval (define gen (generator-fold-map + 0 (list->generator '(1 2)))) (gen) (gen) (gen)]} @defproc[(generator-filter [pred (arg -> boolean?)] [src (gen-> arg)]) (gen-> arg)]{ Creates a generator that generates the values from @scheme[src] for which @scheme[pred] returns non-@scheme[#f]. @examples[ #:eval gen-eval (define gen (generator-filter even? (list->generator '(1 2 3 4 5)))) (gen) (gen) (gen)]} @defproc[(generator-filter-map [fn (arg -> (U ans #f))] [src (gen-> arg)]) (gen-> ans)]{ Creates a generator that generates the non-@scheme[#f] values of @scheme[(fn (src))]. @examples[ #:eval gen-eval (define (test val) (memq val '(2 4 6))) (define gen (generator-filter-map test (list->generator '(1 2 3 4 5)))) (gen) (gen) (gen)]} @defproc[(generator-remove-duplicates [src (gen-> a)] [same? (a a -> boolean?) equal?]) (gen-> a)]{ Creates a generator that filters out values from @scheme[src] that occur more than once in succession. The optional argument @scheme[same?] is used to test equality. @examples[ #:eval gen-eval (define gen (generator-remove-duplicates (list->generator '(1 2 2 3 3 3)))) (gen) (gen) (gen) (gen)]} @defproc[(generator-for-each [fn (arg1 arg2 ... -> void)] [gen1 (gen-> arg1)] [gen2 (gen-> arg2)] ...) void?]{ Repeatedly applies @scheme[fn] for its side-effects to values form source generators @scheme[gen1 gen2 ...] until one or more sources is exhausted. @examples[ #:eval gen-eval (generator-for-each display (list->generator '(1 2 3)))]} @defproc[(generator-fold [fn (arg1 arg2 ... seed -> seed)] [initial-seed seed] [gen1 (gen-> arg1)] [gen2 (gen-> arg2)] ...) seed]{ Like @scheme[generator-fold-map] but only the result of the final application of @scheme[fn] is returned. @examples[ #:eval gen-eval (generator-fold + 0 (list->generator '(1 2 3)))]} @defproc[(generator->list [src (gen-> a)]) (listof a)]{ A convenience form of generator-fold that collects the generated values into a list (in the order generated). @examples[ #:eval gen-eval (generator->list (list->generator '(1 2 3)))]} @defproc[(generator->hash [src (gen-> a)] [item->key (a -> b)] [item->val (a -> c) (lambda (a) a)] [initial-hash (hashof b c) (make-hash)]) (hashof b c)]{ Similar to @scheme[generator->list] but collects the generated values into a hash table. @scheme[item->key] an @scheme[item->val] control how generated items are turned into keys and values in the hash. @scheme[initial-hash] lets you specify the (mutable) hash table to use for the collection (useful for switching to a hash table that uses @scheme[eq?] as a comparison function). @examples[ #:eval gen-eval (hash-map (generator->hash (list->generator '(2 4 6)) (lambda (x) (/ x 2))) (lambda (key val) (list key val)))]} @defproc[(generator-project [mask (listof boolean)] [src (gen-> (listof any))] [same? [(any any -> boolean)] eq?]) (gen-> (list any ... (listof (listof any))))]{ Does the equivalent of a projection (from relational algebra) on the values returned by @scheme[src]. @scheme[#t] values in @scheme[mask] correspond (by position) to "key" values in values from @scheme[src], while @scheme[#f] values correspond to "nonkey" values. @scheme[src] is polled once and the members returned are partitioned into keys and nonkeys and stored. @scheme[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: @schemeblock[(list key ... (listof (list nonkey ...)))] The optional @scheme[same?] argument is the predicate used to check key equality. @scheme[generator-project] is useful (in conjunction with @scheme[generator-map], @scheme[map] and @scheme[match-lambda]) for iterating over sets of related results returned by database queries. @examples[ #:eval gen-eval (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) (gen) (gen) (gen) (gen)]} @defproc[(generator-debug [message string?] [src (gen-> a)]) (gen-> a)]{ Creates a generator that calls @scheme[debug] on each value generated. @examples[ #:eval gen-eval (define gen (generator-debug "message" (list->generator '(1 2)))) (gen) (gen) (gen)]} } @;{end defmodule}