The text suggests that one should use a structure to keep track of pairs that have already been encountered. Notice that there is a let statement defining encountered around the internal definition of a helper function, so that this list is recreated every time count-pairs is invoked, and so that the helper has access to all encountered pairs at any point of execution.
(define (count-pairs x)
(let ((encountered '()))
(define (helper x)
(if (or (not (pair? x)) (memq x encountered))
0
(begin
(set! encountered (cons x encountered))
(+ (helper (car x))
(helper (cdr x))
1))))
(helper x)))
<< Previous exercise (3.16) | Index | Next exercise (3.18) >>
Posting my attempt as an alternative that does not use `set!`
(define (count-pairs x)
(define (collect-pairs x seen)
(if (or (not (pair? x)) (memq x seen))
seen
(let ((seen-car (collect-pairs (car x) (cons x seen))))
(collect-pairs (cdr x) seen-car))))
(length (collect-pairs x '())))
A slightly different way of doing it. Note that unlike the above solution this one continues to traverse pairs it's already seen and so will never return if there's a loop.
(define (count-pairs x) (let ((counted '())) (define (uncounted? x) (if (memq x counted) 0 (begin (set! counted (cons x counted)) 1))) (define (count x) (if (not (pair? x)) 0 (+ (count (car x)) (count (cdr x)) (uncounted? x)))) (count x)))