# weima learns to program

my attempt to do the exercises in sicp.

## Monday, November 16, 2009

### 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)