sicp exercise 3.17

; Exercise 3.17.  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.)


;; The idea is to traverse the node and save the traversed node in a sequence.


(define (count-pairs struct)
  (let (( seq '()))
    (define (count x)
      (if (or (not (pair? x)) (memq x seq))
          0
          (let ((temp (list '())))
            (set-car! temp x)
            (set-cdr! temp seq)
            (set! seq temp)
            (+ 1 (count (car x)) (count (cdr x))))))
      (count struct)))


(define p (cons (cons '1 '2) (cons '3 '4)))
(display p) (newline)

; this should return 3
(display (count-pairs p)) (newline)

; make a loop
(set-cdr! (cdr p) p)
(display p) (newline)

; this should also return 3 even though there is loop in the structure
(display (count-pairs p)) (newline)