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.

## 1 comment:

I think a better tree-map procedure would be the one using map:

(define (tree-map proc tree)

(map (lambda (branch)

(if (pair? branch)

(tree-map proc x)

(proc x)))

tree))

Post a Comment