SICP 2.35: Counting the Leaves of a Tree

From SICP section 2.2.3 Sequences as Conventional Interfaces

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.