[plt-scheme] a semi-trivial tree-traversal problem
Here is a semi-trivial tree-traversal problem.
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. But that
solution requires that the flatten operation be executed first, on a
tree of indeterminate and potentially massive size. A potentially
wasteful process.
So, here is a potential solution that I hammered out.
(define (search-width L offset)
(call-with-current-continuation
(lambda (return)
(letrec ((_search-width (lambda (L)
(if (list? L)
(if (empty? L)
#f
(let ()
(_search-width (car L))
(_search-width (cdr L))
#f))
(if (> L offset)
(return L)
(let ()
(set! offset (- offset L))
#f))))))
(_search-width L)))))
As far as I can determine, this works. But I have some questions.
First, does this style of programming lead to any 'hidden' problems?
Second, how might we eliminate the 'ugly' call to set! ? And
finally, is there a generally better approach to solving this
problem, either in terms of efficiency, or coding style?
David Richards