Michael D. Adams and R. Kent Dybvig.
Efficient
nondestructive equality checking for trees and graphs,
*Proceedings of the 13th ACM SIGPLAN International Conference on
Functional Programming*,
179-188,
September, 2008
(bibtex).

The Revised^{6} Report on Scheme changed the semantics of equal?
so that it is now required to terminate even on cyclic inputs. While
there are a number of methods for implementing this by using DFA
equivalence or union-find algorithms, these methods may impose
unacceptably large overheads for small acyclic inputs in which they are
not actually needed.

This paper presents an implementation of equal? that performs well on a wide range of inputs both large and small, cyclic and acyclic by incurring most of the overhead only when necessary. The algorithm is presented as a sequence of incremental improvements to the straightforward implementation of equal? that works only for acyclic inputs. The final result is an implementation that guarantees termination while never being more than a small factor slower than whichever of the acyclic or union-find algorithms would have been fastest.