Exercise 2.35 of SICP

2009-08-20

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

Contents