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.

No comments: