Note: this wiki is now retired and will no longer be updated!
The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.
SICP exercise 2.35
Redefine count-leaves from section 2.2.2 of the text as an accumulation:
(define (count-leaves t) (accumulate <??> <??> (map <??> <??>)))
Here's the original count-leaves from section 2.2.2 of the text:
(define (count-leaves x) (cond ((null? x) 0) ((not (pair? x)) 1) (else (+ (count-leaves (car x)) (count-leaves (cdr x))))))
Here's a new implementation using accumulate. In this definition, map finds sub-trees and applies count-leaves to them recursively, creating a list of the total number of leaves in each sub-tree. The accumulate op simply sums up the list of sub-tree totals.
(define (accumulate op initial sequence) (if (null? sequence) initial (op (car sequence) (accumulate op initial (cdr sequence))))) (define (count-leaves t) (accumulate (lambda (leaves total) (+ leaves total)) 0 (map (lambda (sub-tree) (if (pair? sub-tree) (count-leaves sub-tree) 1)) t)))
(define x (cons (list 1 2) (list 3 4))) (count-leaves x)
(count-leaves (list x x))
(define y (list 1 (list 1 (list 2 3) (list (list 3 4) 2)))) y
(1 (1 (2 3) ((3 4) 2)))