SICP問題3.18

SICP

循環が含まれるかを決める手続き

(define (endless-loop-list? l)
  (define cl '()) ; checked-list
  (define (sub-rcsv x)
    (cond ((not (pair? x)) #f)
          ((memq x cl) #t)
          (else
           (set! cl (cons x cl))
           (sub-rcsv (cdr x)))))
  (sub-rcsv l))

テスト
3.13のmake-cycleを使って無限ループするリストを作成してテストする

(define z (make-cycle (list 'a 'b 'c)))
; z
(define l3 (list 'a 'b 'c))
; l3
(define x (cons 'a '()))
; x
(define y (cons 'b x))
; y
(define l4 (cons y x))
; l4
(define x (cons 'a '()))
; x
(define y (cons x x))
; y
(define l7 (cons y y))
; l7
(endless-loop-list? z)
; #t
(endless-loop-list? l3)
; #f
(endless-loop-list? l4)
; #f
(endless-loop-list? l7)
; #f
(endless-loop-list? '())
; #f
(endless-loop-list? (cons 'a '()))
; #f
(endless-loop-list? (cons 'a 'b))
; #f

OK