sicp 3.18, 3.19

問題 3.18 です。「ループしてるか調べましょう」って問題ですね。
基本戦略は 3.17 と同じです。
リスト構造を下っていき、調べたことのある pair を見つけたら「ループあり」です。

問題なのは 3.19 の方です。

問題 3.19
定量のスペースしか使わないアルゴリズムを使って問題 3.18 を再試行せよ. (非常に賢明な考え方が必要だ.)

(非常に賢明な考え方が必要だ.)
これは読者に対するお茶目な挑戦状だと思います。僕は思いつかなかったので google で検索して先人の方々の解答を参考にさせていただきました。

基本戦略は以下のようになります。

  • ポインタを2つ用意する(short-step と long-step)
  • リストの cdr を short-step に代入していく(一歩ずつリストを下っていく)
  • リストの cddr を long-step に代入していく(二歩ずつリストを下っていく)
  • short-step と long-step が等しければループあり
  • short-step か long-step が空リストに当たればループなし

short-step と long-step の差は一歩分ずつ大きくなっていくので、
step 差分は必ず循環部分の pair の数の整数倍になるため、
無限ループに陥るなんてこともありません。

でもこれ、問題があります。
cdr, cddr でリストを下っていくので、枝分かれしてるリストのループは発見できません。
問題の内容としてはそこまで追求しなくてよいって事になっていますが。
(id:yatsuta さんにご指摘していただきました。ありがとうございます。)

で、ここまで書いておいてなんですが、
肝心のコードが実は書けてませんでした。
勉強会に持って行ったコードはもうでたらめでした。お恥ずかしい。
ホワイトボードに書き出さなくてよかったー。