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