At Thu, 14 Sep 2017 16:21:29 +0300, Dimitris Vyzovitis wrote:
> > Have you looked at how other implementations of Scheme do this?
>
> I looked at chibi which has a native C impl, and racket which is insanely
> complex.
> No definitive answer yet on how to resolve the edge case properly.

Here's a paper about Chez Scheme's implementation:

 Efficient nondestructive equality checking for trees and graphs.
 Adams & Dybvig, ICFP'08
 http://www.cs.indiana.edu/~dyb/pubs/equal.pdf

I think the union-find aspect is probably what you're looking for.

Here's the current implementation:

 https://github.com/cisco/ChezScheme/blob/master/s/5_1.ss#L31

Probably less interesting/useful, but Racket-on-Chez currently has its
own `equal?` to support chaperones and impersonators, and it has the
same union-find part:

  https://github.com/racket/racket7/blob/master/racket/src/cs/core/equal.ss