[gambit-list] Implementation of equal? for recursive structures

Matthew Flatt mflatt at cs.utah.edu
Thu Sep 14 09:30:42 EDT 2017

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

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

Here's the current implementation:


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:


More information about the Gambit-list mailing list