## Saturday, February 26, 2011

### SICP 2.30 - 2.31: Mapping over trees

From SICP section 2.2.2 Hierarchical Structures

In section 2.2.1 we saw how to build an abstraction called map that allows us to apply a transformation to each element of a list and return a list of results. The next two exercises show us how to do the same with trees. For example, we're given the scale-tree procedure, which takes a numeric factor and a tree whose leaves are numbers as its arguments. This procedure returns a tree of the same shape, but each number is multiplied by the factor.

We're given two implementations of scale-tree. The first traverses the tree in the same manner as used in count-leaves earlier in the text. In this case, when we encounter a leaf node we multiply it by the factor.
(define (scale-tree tree factor)   (cond ((null? tree) null)         ((not (pair? tree)) (* tree factor))         (else (cons (scale-tree (car tree) factor)                     (scale-tree (cdr tree) factor)))))

The second implementation uses map and treats the tree structure as a sequence of sub-trees. We map over the sequence, and use lambda to define a procedure that scales each sub-tree. We multiply by the factor when a leaf node is reached.
(define (scale-tree tree factor)   (map (lambda (sub-tree)          (if (pair? sub-tree)              (scale-tree sub-tree factor)              (* sub-tree factor)))        tree))

Either implementation above will behave as follows:
(scale-tree (list 1 (list 2 (list 3 4) 5) (list 6 7))            10)(10 (20 (30 40) 50) (60 70))

Exercise 2.30 asks us to define a procedure called square-tree that's directly analogous to the square-list procedure from exercise 2.21. It needs to behave as follows:
(square-tree  (list 1        (list 2 (list 3 4) 5)        (list 6 7)))(1 (4 (9 16) 25) (36 49))

We're asked to define both a direct implementation (without using any higher-order procedures) and one that uses map. If you use the two implementations of scale-tree above, these can be defined nearly by direct substitution. The only real difference is that instead of multiplying a leaf node by a given factor, you square it.
; direct implementation(define (square-tree tree)   (cond ((null? tree) null)         ((not (pair? tree)) (* tree tree))         (else (cons (square-tree (car tree))                     (square-tree (cdr tree)))))); using map and recursion(define (square-tree tree)   (map (lambda (sub-tree)          (if (pair? sub-tree)              (square-tree sub-tree)              (* sub-tree sub-tree)))        tree))

Use the test case given above to verify that each of these implementations gives you the same result.
> (square-tree  (list 1        (list 2 (list 3 4) 5)        (list 6 7)))(1 (4 (9 16) 25) (36 49))

Exercise 2.31 asks us to abstract our answer to exercise 2.30 to produce a tree-map procedure that could be used to define square-tree as:
(define (square-tree tree)    (tree-map square tree))

As you can see from the square-tree definition above, tree-map should take a procedure and a tree and apply the function to each element of the tree structure. The following solution is modeled after the direct solution of exercise 2.30 above.
; exercise 2.31 tree-map(define (tree-map proc tree)   (cond ((null? tree) null)          ((not (pair? tree)) (proc tree))          (else (cons (tree-map proc (car tree))                      (tree-map proc (cdr tree))))))(define (square x)   (* x x))(define (square-tree tree)   (tree-map square tree))

Once again, use the provided test case to verify that the new implementation gives you the correct result.
> (square-tree  (list 1        (list 2 (list 3 4) 5)        (list 6 7)))(1 (4 (9 16) 25) (36 49))

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.