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.
和练习 3.17 类似，需要一个额外的变量来记录都访问过哪些数组
(define (circle? lst)
(define (pair-in-list? x lst)
(cond ((null? lst) #f)
((eq? x (car lst)) #t) ;; compare its pointer
(else (pair-in-list? x (cdr lst)))))
(define (circle/rec? l visited)
(cond ((null? l) #f)
((pair-in-list? l visited) #t)
(else
(circle/rec? (cdr l) (cons l visited)))))
(circle/rec? lst '()))
;;; tests begin
(let ((pairs '(1 2 3)))
(begin
(set-cdr! (cddr pairs) (cdr pairs))
(asserteq? (circle? pairs) #t)))
(let ((pairs '(1 2 3)))
(begin
(set-cdr! (cddr pairs) pairs)
(asserteq? (circle? pairs) #t)))
(let ((pairs '(1 2 3)))
(begin
(set-cdr! (cddr pairs) (cddr pairs))
(asserteq? (circle? pairs) #t)))
(define (make-cycle x)
(define (last-pair x)
(if (null? (cdr x))
x
(last-pair (cdr x))))
(set-cdr! (last-pair x) x)
x)
(let ((z (make-cycle (list 'a 'b 'c))))
(asserteq? (circle? z) #t))