sicp-ex-2.35

For those who are confused about how the above is working consider the following example:

Having the following tree:

 (define tree (list 1 2 (list 3 4) (list 5 (list 6 7)))) 
 (count-leaves-recursive tree) ;; => 7 

The map call in the function would flatten the tree into a list of the top level nodes with each one containing the count of its children nodes, if the node in it self is not a tree then 1 would be returned from the iterator passed to the map call.

Yielding (list 1 1 2 3) Which would be passed to the accumulator and a simple summation would be made.

The following illustrates the mapping on the tree, numbers would map to one and lists would map to its sum:

                            7
                            ^
                            |
(1              1              2                     3)
 |              |              |                     |
 1              2             (1 1)              (1    2)
                               | |                |    |
                               3 4                5  (1 1)
                                                      | |
                                                      6 7

I couldn't figure out a way of doing this with map without relying on the previously-defined enumerate-tree. enumerate-tree is used a lot in the chapter so it's probably what's intended.

  
 ;; Accumulates the result of the first and the already-accumulated 
 ;; rest. 
 (define (accumulate op initial sequence) 
   (if (null? sequence) 
       initial 
       (op (car sequence) 
           (accumulate op initial (cdr sequence))))) 
  
 (accumulate + 0 (list 1 2 3 4 5)) 
 (accumulate cons nil (list 2 3 4 5 6)) 
  
 ;; Pulls out all the leaves of the tree, returns as a flat list. 
 (define (enumerate-tree tree) 
   (cond ((null? tree) nil) 
         ((not (pair? tree)) (list tree)) 
         (else (append (enumerate-tree (car tree)) 
                       (enumerate-tree (cdr tree)))))) 
  
  
 (define (count-leaves t) 
   (accumulate + 
               0 
               (map (lambda (x) 1)  
                    (enumerate-tree t)))) 
  
 ;; Usage 
 (define tree (list 1 2 3 (list 4 5 (list 6 7)))) 
 (count-leaves tree)  ;; => 7 
  

If we remove the constraint (aka hint) of using map, we can do it without enumerate-tree, but we have to make a recursive call to count-leaves if the current node is another subtree, since accumulate can't descend into the subtrees.

  
 (define (count-leaves-without-map t) 
   (accumulate (lambda (node count-thus-far) 
                 (+ count-thus-far 
                    (cond ((null? node) 0) 
                          ((not (pair? node)) 1) 
                          (else 
                           (count-leaves-without-map node))))) 
               0 
               t)) 
  
 ;; Usage 
 (count-leaves-without-map tree) ;; => 7