연습문제 3.17

[xeraph]

; pict. 3.16

(define x (list 'a
'b))
(define z1 (cons x x))

; pict. 3.17
(define z2 (cons (list 'a 'b) (list 'a 'b)))

(define (set-to-wow! x)
(set-car! (car x) 'wow)
x)

; 3.16
(define (count-pairs x)
(if (not (pair? x))
0
(+ (count-pairs (car x))
(count-pairs (cdr x))
1)))

; 3.17
(define (correct-count-pairs x)
(define trace '())
(define (count-pairs x)
(cond ((not (pair? x)) 0)
((memq x trace) 0)
(else
(set! trace (cons x trace))
(+ (count-pairs (car x))
(count-pairs (cdr x))
1))))
(count-pairs x))

(define q1 '(c))
(define q2 (cons q1 q1))
(count-pairs (cons q2 q2))
(correct-count-pairs (cons q2 q2))

cycle 없는 경우에만 제대로 동작합니다.
cycle 존재 여부를 찾는 것은 다음 문제입니다.