2006/04/07

昼休みの明けの妥協案。けっきょくカウンタみたいなものを使うことにした。あと、car部が巡回リストを含む場合はチェックできない(これをなんとかしようと考えてたら、もうこんな時間!)。あくまでも、「cdrを追っていくようなプロシージャが停止しないリスト」かどうかを調べるってことで(つまり、今朝の z みたいなものは引っかからない)。
(define (cdr-cycle? x)
(if (not (pair? (cdr x)))
#f
(let R ((x x) (y (cdr x)) (c 0))
(cond ((null? y) #f)
((eq? x y) #t)
((< 0 c) (R (cdr x) y (- c 1)))
(else (R x (cdr y) (+ c 1)))))))
gosh> x
(0 . #0=(1 2 . #0#))
gosh> (cdr-cycle? x)
#t
gosh> y
(0 0 . #0=(1 2 . #0#))
gosh> (cdr-cycle? y)
#t
gosh> z
((0 . #0=(1 2 . #0#)) . 4)
gosh> (cdr-cycle? z)
#f

No comments :