<< Previous exercise (2.34) | Index | Next exercise (2.36) >>

Using recursion, it's possible to do it with map and without enumerate-tree the following way.

(define (count-leaves-recursive t) (accumulate + 0 (map (lambda (node) (if (pair? node) (count-leaves-recursive node) 1)) t))) ;; Usage (count-leaves-recursive tree) ;; => 7

The previous solution counts the empty list as a leaf:

(count-leaves-recursive (quote (1 () () (() ()) () () 2))) ;; Value: 8

This can easily be remedied by using more conditions:

(define (count-leaves-recursive t) (accumulate + 0 (map (lambda (t) (cond ((null? t) 0) ((pair? t) (count-leaves-recursive t)) (else 1))) t))) ;; which gives (count-leaves-recursive '(1 2 () () (3 () ()))) ;; Value: 3

My solution is a "tomato-tomato" of above.

Identity-mapping and using recursion in proc.

```
(define (count-leaves t)
(define proc (lambda (x y) (if (pair? x) (+ (count-leaves x) y)
(+ 1 y))))
(define init_val 0)
(define seq (map (lambda (a) a) t))
(accumulate proc init_val seq))
```

I couldn't figure out a way of doing this with map without relying on the previously-defined enumerate-tree. enumerate-tree is used a lot in the chapter so it's probably what's intended.

;; Accumulates the result of the first and the already-accumulated ;; rest. (define (accumulate op initial sequence) (if (null? sequence) initial (op (car sequence) (accumulate op initial (cdr sequence))))) (accumulate + 0 (list 1 2 3 4 5)) (accumulate cons nil (list 2 3 4 5 6)) ;; Pulls out all the leaves of the tree, returns as a flat list. (define (enumerate-tree tree) (cond ((null? tree) nil) ((not (pair? tree)) (list tree)) (else (append (enumerate-tree (car tree)) (enumerate-tree (cdr tree)))))) (define (count-leaves t) (accumulate + 0 (map (lambda (x) 1) (enumerate-tree t)))) ;; Usage (define tree (list 1 2 3 (list 4 5 (list 6 7)))) (count-leaves tree) ;; => 7

If we remove the constraint (aka hint) of using map, we can do it without enumerate-tree, but we have to make a recursive call to count-leaves if the current node is another subtree, since accumulate can't descend into the subtrees.

(define (count-leaves-without-map t) (accumulate (lambda (node count-thus-far) (+ count-thus-far (cond ((null? node) 0) ((not (pair? node)) 1) (else (count-leaves-without-map node))))) 0 t)) ;; Usage (count-leaves-without-map tree) ;; => 7

For those who are confused about how the above is working consider the following example:

Having the following tree:

The map call in the function would flatten the tree into a list of the top level nodes with each one containing the count of its children nodes, if the node in it self is not a tree then 1 would be returned from the iterator passed to the map call.

Yielding (list 1 1 2 3) Which would be passed to the accumulator and a simple summation would be made.

The following illustrates the mapping on the tree, numbers would map to one and lists would map to its sum: