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

For those who are confused about how the above works, consider the following example:

Given the following tree:

(define tree (list 1 2 (list 3 4) (list 5 (list 6 7)))) (count-leaves-recursive tree) ;; => 7

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 child nodes. If the current node itself is not a tree, then `1` would be returned from the iterator passed to the `map` call.

This yields

```
(list 1 1 2 3)
```

which would be passed to the accumulator for a simple summation.

The following illustrates the mapping on the tree. Numbers will map to `1` and lists will map to their sum:

= 7 total ↑ ┌────────────┬────────────┴──┬──────────────────┐ (1 1 2 3) ; (+ 1 1 2 3) ↓ ↓ ┌────┴────┐ ┌────┴────┐ ; ┌─────┘ │ + 1 + 1 (1 1) (1 2) ; (+ 1 1) (+ 1 2) = 1 = 2 ↓ ↓ ↓ ┌───┴───┐ ; ┌───┘ + 1 + 1 + 1 (1 1) ; (+ 1 1) = 3 = 4 = 5 ↓ ↓ + 1 + 1 = 6 = 7

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

A different version of the procedure uses `enumerate-tree`, just like jz, but with a slight difference

```
(define (count-leaves t)
(accumulate (lambda (x y) (+ (length x) y))
0
(map enumerate-tree t)))
```

Procedure using anonymous recursion and `append`.

```
(define (count-leaves t)
(accumulate
+
0
(map (lambda (x) 1)
(((lambda (x)
(x x))
(lambda (func)
(lambda (e)
(if (null? (cdr e))
(if (pair? (car e))
((func func) (car e))
(cons (car e) '()))
(if (pair? (car e))
(append ((func func) (car e))
((func func) (cdr e)))
(cons (car e)
((func func) (cdr e))))))))
t))))
```

A bit weird implementation but it works.

Here the key struggle to understand this implementation is `(((lambda (x) (x x)) ...`. Actually let `(lambda (func) ...` be `L`. Then it does `((L L) t)`. Then it becomes `((lambda (e) ...) t)` with `func` being `L`. Then it recurse into `t`. If we ''assume `((L L) t)` by induction'' can do same as `enumerate-tree`, then `((func func) t)` can also do that. Then the rest should be easy to understand and be proved right based on induction (Notice `(if (null? (cdr e))` can also be same as `enumerate-tree`).

I struggled for a while, and then somehow made it work with an "almost useless" map:

```
(define (count-leaves t)
(accumulate (lambda (t accumulated)
(+ accumulated
(if (pair? t)
(count-leaves t)
1)))
0
(map identity t)))
```

It is quite similar to jz's answer though.

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

The previous solution counts the empty list as a leaf:

This can easily be remedied by using more conditions: