サイクルがあるとき、確実な列挙方法

再帰的データ型の包含性の判定、わかった - 檜山正幸のキマイラ飼育記 メモ編 の「すべてのノードをくまなくチェックしたことの確認が難しい。」というハナシ。これも大丈夫だろう。

とりあえず、練習問題としてサイクルがあるツリー（言葉は変だが）のノード列挙問題を考えるとよい。一番アホだが一番確実なのは、訪れたノードを全部記録しておくこと。「一度訪れたノードは二度行かない」という制限付きで、深さ優先再帰的トラバースはできる。

「過去は全部記録方式」のトラバースを、参照（部分構造の共有）がある場合に拡張する。参照先への“ハイパージャンプ”があるが、ハイパージャンプの履歴も記録して“戻るボタン”を有効にする。要するに、なんでもかんでも記録する。

「一度訪れたノードは二度行かない」の代わりに、2つのツリーのノード対に関して、「一度確認したノード対は二度確認はしない」とすれば、模倣の構成ができる。記録されたノード対は、模倣関係の要素となる。具体的に構成された模倣にも使いどころがあるかもしれない。

だんだん模倣の構成が当たり前にできる感じがしてきたぞ。模倣の圏がとてもリアルに見えてきた。包含性判定が主たる応用だが、他にも使える感じがするな。クリーネ／ファインマン総和と拡張ダイクストラ法をガシガシ使って型解析やってみるべ。アルゴリズムをもう少し速くしないとなー。