## **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

From Drewiki

## Problem

Redefine `count-leaves` from section 2.2.2 of the text as an accumulation:

(define (count-leaves t) (accumulate <??> <??> (map <??> <??>)))

## Solution

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)))

Tests:

(define x (cons (list 1 2) (list 3 4))) (count-leaves x)

*Output:*

`
`

4

(count-leaves (list x x))

*Output:*

`
`

8

(define y (list 1 (list 1 (list 2 3) (list (list 3 4) 2)))) y

*Output:*

`
`

(1 (1 (2 3) ((3 4) 2)))

(count-leaves y)

*Output:*

`
`

7