6.001 Recitation #7                                        Fall 1997
Prof. Albert R. Meyer

                    5-minute-problem #8: Pruning A Tree
                      (posed in email Wed, 10/1/97)

The PRUNE procedure recursively removes all the empty (i.e., null)
subtrees of a tree, leaving either an empty tree or a tree with no empty
subtrees.  For example,


>> (define test-tree '(1 (2 3 ()) (4) ()))

>> (prune test-tree)
;Value 3: (1 (2 3) (4))

>> (define tree2 '(((())) (3 (())) 4))

>> (prune tree2)
;Value 4: ((3) 4)

>> (prune '(((())) ()))
;Value: ()

Give a simple definition of PRUNE and explain your definition -- for
example by noting any "useful facts" on which your definition is based.
There is at least one simple definition using the list operations FILTER
and MAP, but you are not required to use these.

NOTE: MAP is built into MIT Scheme.  FILTER is not, so you'll have to
define it if you use it:

(define (filter pred lst)
  (cond ((null? lst) '())
	((pred (car lst))
	 (cons (car lst) (filter pred (cdr lst))))
	(else (filter pred (cdr lst)))))



                          SOLUTION (presented 10/03)


(define (not-null? x)
  (not (null? x)))

(define (prune-juice tree)
  (filter not-null?
          (map
           (lambda (el)
             (if (pair? el)
                 (prune-juice el)
                 el))
           tree)))


It is in fact, very slightly buggy.  We correctly convinced ourselves that
PRUNE-JUICE would work on a tree which which had subtrees, or was nil, but we
forgot to consider a tree which was itself a non-null leaf.  If we tried
                             (prune-juice 3)
then Scheme would report an error, instead of leaving the leaf 3 alone.
(What error does Scheme report?)

The problem is that the predicate of the IF (whether a subtree is an
element to be left alone, or a pair to be recursively pruned) is not
applied to the initial tree, only to its subtrees.  The fix is to move the
test to the beginning:

(define (prune tree)
  (if (pair? tree)
      (filter not-null?
              (map prune tree))
      tree))