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

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)
    (stream-delay
     (if (stream-null? stream1)
         stream2
         (stream-cons (stream-car stream1)
                      (stream-append (stream-cdr stream1) stream2)))))

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