Exercise 2.35 asks us to redefine the

`count-leaves`

procedure from section 2.2.2 as an accumulation. Our procedure should take the following form:`(define (count-leaves t)`

(accumulate <??> <??> (map <??> <??>)))

When I encounter a problem like this (implement X in terms of Y), I find that it helps to take a look at both procedures side-by-side to see what they have in common. The

`count-leaves`

procedure just returns 1 when it encounters each leaf node, and recursively combines all those 1s with addition otherwise.`; count-leaves from sicp section 2.2.2`

(define (count-leaves x)

(cond ((null? x) 0)

((not (pair? x)) 1)

(else (+ (count-leaves (car x))

(count-leaves (cdr x))))))

The

`accumulate`

procedure takes an operator, and initial value, and a sequence as its parameters. It then combines all elements of the sequence with the initial value using the operator.`; accumulate from sicp section 2.2.3`

(define (accumulate op initial sequence)

(if (null? sequence)

initial

(op (car sequence)

(accumulate op initial (cdr sequence)))))

The operator and initial value in the case of

`count-leaves`

are pretty easy to guess. They should be + and 0 respectively. For its third argument `accumulate`

is expecting a sequence, and our template is using `map`

. Recall that `map`

takes a function and a list and returns a new list. The new list is simply the result of the function being applied to each element of the old list. What we'd really like to accumulate is a sequence of 1s, one for each leaf in the tree. To implement that we need the help of one more procedure from SICP section 2.2.3.`; enumerate-tree from sicp 2.2.3`

(define (enumerate-tree tree)

(cond ((null? tree) null)

((not (pair? tree)) (list tree))

(else (append (enumerate-tree (car tree))

(enumerate-tree (cdr tree))))))

The

`enumerate-tree`

procedure "flattens out" a tree into a sequence of its leaves. Once we have the tree in the form of a sequence, we just need to define a function for the first argument of `map`

. This function should simply return a 1 for any input. Here's the complete (but very short) solution.`(define (count-leaves t)`

(accumulate + 0 (map (lambda (x) 1)

(enumerate-tree t))))

Test it out with trees of different shapes, just to be sure there are no corner cases missed.

`> (count-leaves (list))`

0

> (count-leaves (list 1 2 3))

3

> (count-leaves (list 1 (list 1 2 3)))

4

> (count-leaves (list (list 1 2) (list 1 2 3) 1))

6

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 came up with another solution without map:

(define (count_leaves tree)

(accumulate (lambda (x y)

(if (list? x)

(+ (count_leaves x) y)

(+ 1 y)))

0

tree))

Post a Comment