SICP Exercise 2.31: Tree Map

Abstract your answer to exercise 2.30 to produce a procedure tree-map with the property that square-tree could be defined as

(define (square-tree tree) (tree-map square tree))

To do this, let's look at the two map-based procedures, scale-tree and square-tree:

(define (scale-tree tree factor)
  (map (lambda (sub-tree)
         (if (pair? sub-tree)
             (scale-tree sub-tree factor)
             (* sub-tree factor)))
       tree))

(define (square-tree tree)
  (map (lambda (sub-tree)
         (if (pair? sub-tree)
             (square-tree sub-tree)
             (square sub-tree)))
       tree))

They're pretty similar. Sure, scale-tree takes an extra parameter, and they apply different operations when a non-pair element is being mapped, but the general pattern is the same. I.e.:

(define (doSomethingToA-tree tree possiblyWithSomeParameters)
  (map (lambda (sub-tree)
         (if (pair? sub-tree)
             (doSomethingToA sub-tree possiblyWithSomeParameters)
             (applyOperationTo sub-tree possiblyWithSomeParameters)))
       tree))

If we encapsulate the operation to apply to non-pair elements and the optional parameters into a procedure then we'd be able to generalize this process as follows:

(define (tree-map proc tree)
  (map (lambda (sub-tree)
         (if (pair? sub-tree)
             (tree-map proc sub-tree)
             (proc sub-tree)))
       tree))

Then we can define both scale-tree and square-tree in terms of tree-map:

(define (scale-tree tree factor)
  (tree-map (lambda (x) (* x factor)) tree))

(define (square-tree tree)
  (tree-map square tree))

And then put them to the test:

> (scale-tree (list 1 (list 2 (list 3 4) 5) (list 6 7))
              10)
'(10 (20 (30 40) 50) (60 70))
> (scale-tree (list 1
                    2
                    (list 3 (list 4 5) 6)
                    (list 7 (list 8 (list 9)) 10 (list 11))
                    (list 12))
              2)
'(2 4 (6 (8 10) 12) (14 (16 (18)) 20 (22)) (24))
> (square-tree
    (list 1
          (list 2 (list 3 4) 5)
          (list 6 7)))
'(1 (4 (9 16) 25) (36 49))
> (square-tree
    (list 1
          2
          (list 3 (list 4 5) 6)
          (list 7 (list 8 (list 9)) 10 (list 11))
          (list 12)))
'(1 4 (9 (16 25) 36) (49 (64 (81)) 100 (121)) (144))