計算機プログラムの構造と解釈 第二版 P152 問題3.19

この問題、前回ナミックさんが問題3.18やってる時に「良い事おもいついた！eq?使えそうじゃね」
とか僕はなんか思いつくとすぐ調子に乗るので、チャチャをいれてたんだが、
問題3.18でそれをやっちゃうと、この問題3.19はやる事がなくなってしまうという
そういうあらすじだったようだ。

ま、そもそもあってんのか間違ってるのか定かではないが。

計算機プログラムの構造と解釈　第二版 P151

　リスト構造での共有を検出する一つの方法は, 2.3.1節で二つの記号が投下かどうかをテストする方法として説明した述語eq?を使うことである. 更に一般には, (eq? x y)はxとyは同じオブジェクトであるか(つまりxとyはポインタとして同じか)をテストする.

って書いてあるし。

つまりだ、

a b c

とかっていうリストをベースにつくった

a b c a b c a b c . . .

みたいな循環リストがあったとしてたら

↓---↓----↓---このaのとこはポインタとして同じはず
a b c a b c a b c . . .

だから
この場合、始めのaの部分のポインタを持ち続けながら、リストを走査して次のaまで、eq?をつづければよいのかな？
って発想。
もちろん途中で、null?がでたら、循環してないので、おわらせる。

追記：
ナミックと話してから、しばらく考えたら、6の字型のループに対応できないことが判明。
下記のようなループ

       ↓---↓----↓---このaのとこはポインタとして同じ
d e f g a b c a b c a b c . . .

これに対応するには、時計でいうところの、分を示す針と、時間を示す針みたいに
分のほうが進みが速いから、やがて時間の針に交わるようなアルゴリズムが必要。
そんで実装もちょっと変更した。

一定量のスペースしかどうのこうの、ってのはイテレーティブにしてやれば、大丈夫じゃね？みたいな。

そういう事で、実装はこんな感じになった。

#!/usr/local/bin/gosh
;; -*- coding: utf-8 -*-

(define nil '())
(define disp display)
(define nl newline)


(define (append! x y)
  (set-cdr! (last-pair x) y)
  x)  


(define (last-pair x)
  (if (null? (cdr x)) 
    x   
    (last-pair (cdr x))))

    
(define (make-cycle x)
  (set-cdr! (last-pair x) x)
  x)  


(define (loop? x)
  (define (loop-i? x y)
    (cond ((null? (cdr x)) #f) 
          ((null? (cddr y)) #f) 
          ((eq? x y) #t) 
          (else
            (loop-i? (cdr x) (cddr y)))))
  (if (null? (cdr x)) #f
    (loop-i? x (cdr x))))




(define normal '(a b c)) 

(define loop (make-cycle '(a b c)))

(define head-loop
  (append! '(d e f) loop))


;; main
(define (main args)
  (disp "(loop? normal): ")
  (print (loop? normal))

  (disp "(loop? loop): ")
  (print (loop? loop))

  (disp "(loop? head-loop): ")
  (print (loop? head-loop))


  0)

実行

(loop? normal): #f
(loop? loop): #t
(loop? head-loop): #t

正解そうな気はするんだけど、んーどうなんだろ？