[plt-scheme] a semi-trivial tree-traversal problem

From: Danny Yoo (dyoo at hkn.eecs.berkeley.edu)
Date: Wed Nov 2 14:39:14 EST 2005

On Wed, 2 Nov 2005, Joe Marshall wrote:

> There's an interesting problem that arises when you mix call-by-value
> with call-by-need (as happens when you use streams).  The solution that
> Danny Yoo posted will flatten the tree into a stream, but it isn't as
> lazy as he hoped.  The entire tree is traversed on the first call.  The
> concatenation is the only part that is done lazily.
> Since this is covered in the streams chapter of SICP, I'll be mysterious
> and omit the details of where the problem is and how to fix it.
> (Other than this one problem, I like the streams approach much better
> than the ones using continuations.)

Hi Joe,

Ah, thanks for catching me on that!  I've added the necessary
stream-delays to make sure that the traversal is handled lazily too:

(module flatten-as-stream mzscheme
  (require (lib "40.ss" "srfi")) ;; streams library
  (provide flatten)

  ;; stream-append: stream stream -> stream
  (define (stream-append stream1 stream2)
     (if (stream-null? stream1)
         (stream-cons (stream-car stream1)
                      (stream-append (stream-cdr stream1) stream2)))))

  ;; flatten: (union list datum) -> stream
  (define (flatten datum)
     (cond ((list? datum)
            (if (null? datum)
                (stream-append (flatten (car datum))
                               (flatten (cdr datum)))))
            (stream-cons datum stream-null))))))

Posted on the users mailing list.