Exercise 2.35 asks us to redefine the
count-leavesprocedure 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-leavesprocedure 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))))))
accumulateprocedure 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)
(op (car sequence)
(accumulate op initial (cdr sequence)))))
The operator and initial value in the case of
count-leavesare pretty easy to guess. They should be + and 0 respectively. For its third argument
accumulateis expecting a sequence, and our template is using
map. Recall that
maptakes 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))))))
enumerate-treeprocedure "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)
Test it out with trees of different shapes, just to be sure there are no corner cases missed.
> (count-leaves (list))
> (count-leaves (list 1 2 3))
> (count-leaves (list 1 (list 1 2 3)))
> (count-leaves (list (list 1 2) (list 1 2 3) 1))
For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.