Implementation attached for review.

This is a direct port of the Chez version.
One thing that needs to be improved is the handling of structs, as it currently only checks to see if the struct is opaque and if not it directly compares fields (instead of also checking individual fields for opaqueness).

Marc, I want to open a PR -- but where should I put it?

It has a dependency on random-integer as it needs to randomize to avoid pathological inputs.

so it can't quite go in _system.scm

-- vyzo

On Thu, Sep 14, 2017 at 4:46 PM, Dimitris Vyzovitis <vyzo@hackzen.org> wrote:

Thanks, that explains a lot!

I think it makes sense to port the Chez version, i'll prepare a patch.

-- vyzo

On Thu, Sep 14, 2017 at 4:30 PM, Matthew Flatt <mflatt@cs.utah.edu> wrote:
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