<< 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
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)))
)
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.
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:
7 ^ | (1 1 2 3) | | | | 1 2 (1 1) (1 2) | | | | 3 4 5 (1 1) | | 6 7