問題3.19
; listがループしていなければ、絶対に交わることの無い二つのイテレータによって解決する。 ; イテーレータxが2進む間にイテレータyは1進む。 (define (include-loop-2? x) (define (iter x y toggle) (if (not (pair? x)) #f (if (eq? x y) #t (iter (cdr x) (if toggle (cdr y) y) (not toggle))))) (if (not (pair? x)) (error "Argument of cycle? must be a pair") (iter (cdr x) x #t))) ; ループが存在しなければ、絶対に交わることは無いが、ループが存在すれば、必ず交わる。 ; しかし、リスト構造によっては、交わるまで時間がかかる。 ; xを一つ前のも保存しておいて比べていくようにすれば、最長の時間が半分になる。と思う。