sicp-ex-2.35

Using recursion, it's possible to do it with map and without enumerate-tree the following way.

 (define (count-leaves-recursive t) 
   (accumulate 
    + 
    0 
    (map (lambda (node) 
           (if (pair? node) 
               (count-leaves-recursive node) 
               1)) 
         t))) 
  
 ;; Usage 
 (count-leaves-recursive tree) ;; => 7 

The previous solution counts the empty list as a leaf:

 (count-leaves-recursive (quote (1 () () (() ()) () () 2))) 
 ;; Value: 8 

This can easily be remedied by using more conditions:

 (define (count-leaves-recursive t) 
   (accumulate + 0 
     (map 
       (lambda (t) 
         (cond ((null? t) 0) 
               ((pair? t) (count-leaves-recursive t)) 
               (else 1))) 
       t))) 
  
 ;; which gives 
 (count-leaves-recursive '(1 2 () () (3 () ()))) 
 ;; Value: 3 

For those who are confused about how the above works, consider the following example:

Given 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 child nodes. If the current node itself is not a tree, then 1 would be returned from the iterator passed to the map call.

This yields

 (list 1 1 2 3) 

which would be passed to the accumulator for a simple summation.

The following illustrates the mapping on the tree. Numbers will map to 1 and lists will map to their sum:

                              = 7 total 
                                ↑ 
      ┌────────────┬────────────┴──┬──────────────────┐ 
     (1            1               2                  3)      ; (+ 1 1 2 3) 
      ↓            ↓          ┌────┴────┐        ┌────┴────┐  ;  ┌─────┘ │ 
    + 1          + 1         (1         1)      (1         2) ; (+ 1 1) (+ 1 2) 
    = 1          = 2          ↓         ↓        ↓     ┌───┴───┐      ;  ┌───┘ 
                            + 1       + 1      + 1    (1       1)     ; (+ 1 1) 
                            = 3       = 4      = 5     ↓       ↓ 
                                                     + 1     + 1 
                                                     = 6     = 7 

My solution is a "tomato-tomato" of above.

Identity-mapping and using recursion in proc.

 (define (count-leaves t) 
   (define proc 
     (lambda (x y) 
       (if (pair? x) 
           (+ (count-leaves x) y) 
           (+ 1 y)))) 
   (define init_val 0) 
   (define seq (map (lambda (a) a) t)) 
   (accumulate proc init_val seq)) 

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 
  

A different version of the procedure uses enumerate-tree, just like jz, but with a slight difference

 (define (count-leaves t) 
   (accumulate (lambda (x y) (+ (length x) y)) 
               0 
               (map enumerate-tree t))) 

 (define (count-leaves t) 
   (accumulate (lambda (x y) (+ 1 y)) 
               0 
               (map (lambda (x) x) 
                    (enumerate-tree t)))) 

  
  
 (define (count-leaves t) 
   (accumulate + 
               0 
               (map (lambda(x) 1) 
                    (enumerate-tree t)))) 
  

Procedure using anonymous recursion and append.

  
 (define (count-leaves t) 
   (accumulate 
    + 
    0 
    (map (lambda (x) 1) 
         (((lambda (x) 
             (x x)) 
           (lambda (func) 
             (lambda (e) 
               (if (null? (cdr e)) 
                   (if (pair? (car e)) 
                       ((func func) (car e)) 
                       (cons (car e) '())) 
                   (if (pair? (car e)) 
                       (append ((func func) (car e)) 
                               ((func func) (cdr e))) 
                       (cons (car e) 
                             ((func func) (cdr e)))))))) 
          t)))) 

I struggled for a while, and then somehow made it work with an "almost useless" map:

  
 (define (count-leaves t) 
   (accumulate (lambda (t accumulated) 
                 (+ accumulated 
                    (if (pair? t) 
                        (count-leaves t) 
                        1))) 
               0 
               (map identity t))) 
  

It is quite similar to jz's answer though.