sicp-ex-3.17


The text suggests that one should use a structure to keep track of pairs that have already been encountered. Notice that there is a let statement defining encountered around the internal definition of a helper function, so that this list is recreated every time count-pairs is invoked, and so that the helper has access to all encountered pairs at any point of execution.

 (define (count-pairs x) 
   (let ((encountered '())) 
     (define (helper x) 
       (if (or (not (pair? x)) (memq x encountered)) 
         0 
         (begin 
           (set! encountered (cons x encountered)) 
           (+ (helper (car x)) 
              (helper (cdr x)) 
              1)))) 
   (helper x))) 

<< Previous exercise (3.16) | Index | Next exercise (3.18) >>


AThird

A slightly different way of doing it. Note that unlike the above solution this one continues to traverse pairs it's already seen and so will never return if there's a loop.

 (define (count-pairs x) 
   (let ((counted '())) 
     (define (uncounted? x) 
       (if (memq x counted) 
           0 
           (begin 
             (set! counted (cons x counted)) 
             1))) 
      
     (define (count x) 
       (if (not (pair? x)) 
           0 
           (+ (count (car x)) 
              (count (cdr x)) 
              (uncounted? x)))) 
     (count x)))