1  Exercise 3.19.  Redo exercise 3.18 using an algorithm that takes only a constant amount of space. (This requires a very clever idea.) 
2 
3 
4 ;; 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 
6 (define (cycle? l)
7   (let ((traversed '()))
8     (define (not-all-unique? l)
9       (cond ((not (pair? l)) #f)
10 	    ((memq l traversed) #t)
11 	    (else (set! traversed (cons l traversed))
12 		  (not-all-unique? (cdr l)))))
13     (not-all-unique? l)))
14 
15 (define (test-case actual expected)
16   (newline)
17   (display "Actual:   ")
18   (display actual)
19   (newline)
20   (display "Expected: ")
21   (display expected)
22   (newline))
23 
24 (define (last-pair x)
25   (if (null? (cdr x))
26       x
27       (last-pair (cdr x))))
28 
29 (define (make-cycle x)
30   (set-cdr! (last-pair x) x)
31   x)
32 
33 (define three '(a b c))
34 (define a-pair (cons '() '()))
35 (define b-pair (cons a-pair a-pair))
36 (define four (cons 'a b-pair))
37 (define seven (cons b-pair b-pair))
38 (define circular (make-cycle '(a b c)))
39 
40 (test-case (cycle? three) #f)
41 (test-case (cycle? four) #f)
42 (test-case (cycle? seven) #f)
43 (test-case (cycle? circular) #t)