SICP問題3.19

SICP

一定量のスペースしか使わないアルゴリズムで3.18を再試行せよ
という問題ですが、再帰じゃなくて反復使って実装するだけ??と思ったら、違うっぽい。
平々毎々 (Hey hey, My my) | アルゴリズムパズル（リンクリスト）に答えるに出ているような、2つのポインタを違う速度で進めていくことで循環を検知するアルゴリズムで実装する話らしい。
ということで実装してみる

(define (endless-loop-list2? l)
  (define (end-list? x)
    (or (null? x)
        (null? (cdr x))))
  (define (check-sub p1 p2)
    (cond ((eq? p1 p2) #t)
          ((end-list? p2) #f)
          (else
           (check-sub (cdr p1) (cdr (cdr p2))))))
  (if (and (not (null? l)) (pair? (cdr l)) (pair? (cdr (cdr l))))
      (check-sub (cdr l) (cdr (cdr l)))
      #f))

テストは3.18と同じのを使って行う

(endless-loop-list2? z)
; #t
(endless-loop-list2? '())
; #f
(endless-loop-list2? (cons 'a '()))
; #f
(endless-loop-list2? (cons 'a 'b))
; #f
(endless-loop-list2? l3)
; #f
(endless-loop-list2? l4)
; #f
(endless-loop-list2? l7)
; #f

OK