2.21.8.2 Generators and co–routines

It is possible to model generators and co–routines using streams. Consider the task, due to Carl Hewitt, of determining if two trees have the same sequence of leaves:

(same-fringe? = '(1 (2 3)) '((1 2) 3))  => #t

(same-fringe? = '(1 2 3) '(1 (3 2)))    => #f

The simplest solution is to flatten both trees into lists and compare them element–by–element:

(define (flatten tree)
  (cond [(null? tree) '()]
        [(pair? (car tree))
         (append (flatten (car tree))
                 (flatten (cdr tree)))]
        [else (cons (car tree)
                    (flatten (cdr tree)))]))

(define (same-fringe? eql? tree1 tree2)
  (let loop ([t1 (flatten tree1)]
             [t2 (flatten tree2)])
    (cond [(and (null? t1) (null? t2)) #t]
          [(or (null? t1) (null? t2)) #f]
          [(not (eql? (car t1) (car t2))) #f]
          [else (loop (cdr t1) (cdr t2))])))

That works, but requires time to flatten both trees and space to store the flattened versions; if the trees are large, that can be a lot of time and space, and if the fringes differ, much of that time and space is wasted.

Hewitt used a generator to flatten the trees one element at a time, storing only the current elements of the trees and the machines needed to continue flattening them, so same-fringe? could stop early if the trees differ. Dorai Sitaram presents both the generator solution and a co–routine solution, which both involve tricky calls to call-with-current-continuation and careful coding to keep them synchronized.

An alternate solution flattens the two trees to streams instead of lists, which accomplishes the same savings of time and space, and involves code that looks little different than the list solution presented above:

(define-stream (flatten tree)
  (cond [(null? tree) stream-null]
        [(pair? (car tree))
         (stream-append
           (flatten (car tree))
           (flatten (cdr tree)))]
        [else (stream-cons
                (car tree)
                (flatten (cdr tree)))]))

(define (same-fringe? eql? tree1 tree2)
  (let loop ([t1 (flatten tree1)]
             [t2 (flatten tree2)])
    (cond [(and (stream-null? t1)
                (stream-null? t2)) #t]
          [(or  (stream-null? t1)
                (stream-null? t2)) #f]
          [(not (eql? (stream-car t1)
                      (stream-car t2))) #f]
          [else (loop (stream-cdr t1)
                      (stream-cdr t2))])))

Note that streams, a data structure, replace generators or co–routines, which are control structures, providing a fine example of how lazy streams enhance modularity.