Thu Mar 26 17:02:12 CET 2009

Sequences, generators and lazy lists

Looking for a standard lazy list implementation that will work well as
an intermediate step to transform generators -> sequences.  The
problem is in these conflicting requirements:

  * 'make-do-sequence needs to lookahead in the sequence: know if
    there's an element before the next is generated.  This needs a
    1-level deep lookahead buffer when translating generators to

  * generators are easily built using prompt/control but can't know
    end-of-sequence beforehand.

Maybe this is best replaced with the lazy list structure in lazy
scheme: it uses delayed constructors, (not delayed tails).  The code
then becomes:

;; Convert generator to lazy list
(define (generator->lazy-list g [done? not])
  (let next ()
      (let ((item (g)))
        (if (done? item) '()
            (cons item (next)))))))

;; Convert lazy list to sequence.
(define (in-lazy-list ll)
   (lambda ()
     (define (ll-car x)   (car (force x)))
     (define (ll-cdr x)   (cdr (force x)))
     (define (ll-more? x) (pair? (force x)))
     (values ll-car ll-cdr ll ll-more? void void))))

;; Composition.
(define (in-generator g [done? not])
  (in-lazy-list (generator->lazy-list g done?)))

The deeper conclusion is this: lazy lists (static) are better behaved
than generators (dynamic).