問題3-18 (3.3.1 Mutable List Structure)

与えられたリストの中に，サイクルがあるかどうかを返す述語を作る．
アイディアとしては，今まで見たポインタを全て記憶していって，記憶した全てと cdr を逐一比較していくという単純な方法．

(define (has-cycle? l)
  (define (not-include? elem l)
    (not (find (lambda (x) (eq? x elem)) l)))
  (define sight '())
  (define (successive-cdr x)
    (cond ((not (pair? x)) #f)
	  ((not (not-include? x sight)) #t)
	  (else
	   (set! sight (cons x sight))
	   (successive-cdr (cdr x)))))
  (successive-cdr l))

テスト．

(define l '(a b c d e))
(has-cycle? l) ; #t

(define (make-cycle x)
  (set-cdr! (last-pair x) x)
  x)
(make-cycle l)
(has-cycle? l) ; #f