## 2011-10-02

### SICP Exercise 2.35: Counting Leaves Again

Redefine `count-leaves` from section 2.2.2 as an accumulation:
```(define (count-leaves t)
(accumulate <??> <??> (map <??> <??>)))
```
In the "Sequence operations" section the authors define the procedure `enumerate-tree` which flattens a tree into a list that contains only the leaf nodes of the tree. We can use this to simplify our job here - we're only interested in the leaf nodes and this saves us the complexity of writing our own tree-traversal. The length of this list is equal to the number of leaf nodes in the tree...

However, the procedure template we're given above doesn't allow us to do that - we have to `map` across a list and then `accumulate` in some way across the result of the mapped list. So what mapping should we use, and what accumulation?

Well, when we defined `length` in terms of `accumulate` in exercise 2.33, we started with an initial value of 0 and incremented this by 1 for each element in the tree. We could achieve the same effect by using `+` as our `op` for `accumulate`, 0 as the `initial` value, and pass it a `sequence` that's a list with the same number of elements as there are leaf nodes, but with each element having the value 1... And we can produce such a sequence by mapping each element from the list returned by `enumerate-tree` to 1.

Here's my implementation:
```(define (count-leaves t)
(accumulate + 0 (map (lambda (x) 1) (enumerate-tree t))))
```
...and in practice:
```> (define x (cons (list 1 2) (list 3 4)))
> (define y (list 1 (list 2 3) (cons (list 4 5) (list 6 7))))
> (count-leaves x)
4
> (count-leaves (cons x x))
8
> (count-leaves y)
7
> (count-leaves (list x y))
11
```

1. 1. 