Schemeのequal?の実装について調べたメモ

R7RSでは、equal?に循環オブジェクトを入力した場合でも必ず終了することが要求されていて、その実装方針について調べていた。
探している答えそのものな内容の論文が見つかった。
“Efficient Nondestructive Equality Checking for Trees and Graphs"という論文でunifon-findを使って循環オブジェクトを効率的に処理しようというものだった。

以下すごく雑なメモ
1、2章、読んでない
3章、pairやvectorを比較するとき、それらをunion-findを用いて、同じ集合にまとめて、次に同じ比較をするときや、不要な比較のケースをはぶいてしまおうという内容。
4章、サイズが小さく、循環構造を含まないものを比較するときに、union-findの部分が足をひっぱるので、union-findなしでk回比較して、終わらなかったらunion-findを使おうという内容
5章、4章の方針の場合、サイズが大きいものを比較する場合、結局union-findの分遅くなるので、各頂点ごとにunion-findありのものとなしのものを併用していくという内容。
6章、4章と5章を融合させるという内容。つまり、5章の方針の前にunion-findなしでk回比較させるという内容。