1 ;; Exercise 3.18. Write a procedure that examines a list and determines whether it contains a cycle, that is, whether a program that tried to find the end of the list by taking successive cdrs would go into an infinite loop. Exercise 3.13 constructed such lists.
5 (define (not-all-unique? l)
6 (cond ((not (pair? l)) #f)
7 ((memq l traversed) #t)
8 (else (set! traversed (cons l traversed))
9 (not-all-unique? (cdr l)))))
12 (define (test-case actual expected)
17 (display "Expected: ")
26 (define (make-cycle x)
27 (set-cdr! (last-pair x) x)
30 (define three '(a b c))
31 (define a-pair (cons '() '()))
32 (define b-pair (cons a-pair a-pair))
33 (define four (cons 'a b-pair))
34 (define seven (cons b-pair b-pair))
35 (define circular (make-cycle '(a b c)))
37 (test-case (cycle? three) #f)
38 (test-case (cycle? four) #f)
39 (test-case (cycle? seven) #f)
40 (test-case (cycle? circular) #t)