SICP Exercise 2.30: Square Trees

Define a procedure square-tree analogous to the square-list procedure of exercise 2.21. That is, square-list should behave as follows:

> (square-tree
    (list 1
          (list 2 (list 3 4) 5)
          (list 6 7)))
(1 (4 (9 16) 25) (36 49))

Define square-tree both directly (i.e., without using any higher-order procedures) and also by using map and recursion.

Now square-list, regardless of version, just iterates through a source list, building a new list of identical length containing the values generated by applying the procedure square to each element of the source list. So we want square-tree to iterate through a source tree, building a new tree of identical structure, but containing the values generated by applying the procedure square to each element of the source tree.

In the section "Mapping over lists", the authors give us a procedure, scale-list which provided us with the basis for our square-list procedure. Similarly in the section "Mapping over trees", the authors give us the analogous procedure, scale-tree, which we can use as the basis of our square-tree procedure. Here's the version that scales a tree directly:

(define (scale-tree tree factor)
  (cond ((null? tree) nil)
        ((not (pair? tree)) (* tree factor))
        (else (cons (scale-tree (car tree) factor)
                    (scale-tree (cdr tree) factor)))))

To produce square-tree we simply need to rename the procedure and its recursive calls, remove factor and replace the scaling of the non-pair elements of the tree with squaring the of the non-pair elements:

(define (square-tree tree)
  (cond ((null? tree) nil)
        ((not (pair? tree)) (square tree))
        (else (cons (square-tree (car tree))
                    (square-tree (cdr tree))))))

Let's check it works:

> (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))

We can do the same for the map-based version. Here's the map-based version of scale-tree:

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

So again, we simply rename the procedure and its recursive calls, remove factor and replace the scaling of the non-pair elements of the tree with squaring the of the non-pair elements:

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

And let's check this one works too:

> (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))