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
Jump to: navigation, search

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

Personal tools