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

On Tue, 1 Nov 2005, David Richards wrote:

> Given a nested list (a tree) of numbers, return the number that
> causes the sum of all preceding (depth-first search) numbers to be
> greater than a specified value.
>
> For example:
>
> (define L '((3 3) 2 4) )
>
> ; (search-width L 7)  -->  2
>
> ... because 3 + 3 + 2 is greater than 7.
>
> One solution is to flatten the list, and then walk down the list
> accumulating a total and terminating appropriately.


Hi David,

We might be able to use streams to flatten only as much as we need.  PLT
Scheme comes with a streams library in SRFI 40:

    http://srfi.schemers.org/srfi-40/srfi-40.html

Here's rough code that may do the trick:

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


  (define (stream-append stream1 stream2)
    (if (stream-null? stream1)
        stream2
        (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-null
               (stream-append (flatten (car datum))
                              (flatten (cdr datum)))))
          (else
           (stream-cons datum stream-null)))))
;;;;;;

The approach here flattens only as much as we want, and using it with
search-width then becomes really nice.  (I should reread SICP and review
streams again, just to see if there's something else I'm missing about
this.)


Hope this helps!