Exercise 2.35: Redefine
count-leaves from section 2.2.2 as an accumulation:
(define (count-leaves t) (accumulate <??> <??> (map <??> <??>))) (define (count-leaves x) (cond ((null? x) 0) ((not (pair? x)) 1) (else (+ (count-leaves (car x)) (count-leaves (cdr x))))))
The goal here is for map to create something that
accumulatecan consume to count the number of leaves.
The initial value must be 0 just like in
count-leaves. The hard part is to come up with
fn that will add up the
leaves. If the tree is flatted a simple length function will compute the number of trees.
(define (accumulate fn init-value items) (if (null? items) init-value (fn (car items) (accumulate fn init-value (cdr items))))) (define (enumerate-tree x) (cond ((null? x) '()) ((not (pair? x)) (list x)) (else (append (enumerate-tree (car x)) (enumerate-tree (cdr x)))))) (define (count-leaves t) (accumulate (lambda (x y) (+ 1 y)) 0 (map (lambda (x) x) (enumerate-tree t))))
I am not sure why map is needed in this example. It just serves to confuse. The lambda argument is really a throw away.
I am aware that it is possible to solve this problem using map in a way that recursively calls
I feel like instead of making the computational process clearer as in
even-fibs it becomes more
convoluted and mysterious. Nevertheless I include it bellow for completeness.
(define (count-leaves t) (accumulate + 0 (map (lambda (elem) (if (not (pair? elem)) 1 (count-leaves elem))) t)))
The example I like is:
(define (deep-reverse seq) (map (lambda (e) (if (not (pair? e)) e (deep-reverse e))) (reverse seq)))