15 hours ago

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)

Subscribe to:
Post Comments (Atom)

## No comments:

Post a Comment