On this page:
generator-end
generator-end?
gen->
list->generator
range->generator
generator-map
generator-fold-map
generator-filter
generator-filter-map
generator-remove-duplicates
generator-for-each
generator-fold
generator->list
generator->hash
generator-project
generator-debug
Version: 4.1.4.1

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

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

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

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

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

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

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

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

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

Examples:

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

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

  generator-end1921