SICP Exercise 3.17

sicp

Question

Devise a correct version of the count-pairs procedure of Exercise 3.16 that returns the number of distinct pairs in any structure. (Hint: Traverse the structure, maintaining an auxiliary data structure that is used to keep track of which pairs have already been counted.)

Answer

(define (count-pairs-new x)
  (let ((already-added '()))
    (define (dispatch z)
      (if (or (memq z already-added) (not (pair? z)))
          0
          (begin (set! already-added (cons z already-added))
                 (+ (dispatch (car z))
                    (dispatch (cdr z))
                    1))))
    (dispatch x)))