Exercise 2.35 of SICP
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 accumulate can 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 count-leaves. I feel like instead of making the computational process clearer as in square-tree and 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)))