<div dir="ltr"><div><div>Thanks, that explains a lot!<br><br></div>I think it makes sense to port the Chez version, i'll prepare a patch.<br><br></div>-- vyzo<br></div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Sep 14, 2017 at 4:30 PM, Matthew Flatt <span dir="ltr"><<a href="mailto:mflatt@cs.utah.edu" target="_blank">mflatt@cs.utah.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">At Thu, 14 Sep 2017 16:21:29 +0300, Dimitris Vyzovitis wrote:<br>
> > Have you looked at how other implementations of Scheme do this?<br>
><br>
> I looked at chibi which has a native C impl, and racket which is insanely<br>
> complex.<br>
> No definitive answer yet on how to resolve the edge case properly.<br>
<br>
</span>Here's a paper about Chez Scheme's implementation:<br>
<br>
 Efficient nondestructive equality checking for trees and graphs.<br>
 Adams & Dybvig, ICFP'08<br>
 <a href="http://www.cs.indiana.edu/~dyb/pubs/equal.pdf" rel="noreferrer" target="_blank">http://www.cs.indiana.edu/~<wbr>dyb/pubs/equal.pdf</a><br>
<br>
I think the union-find aspect is probably what you're looking for.<br>
<br>
Here's the current implementation:<br>
<br>
 <a href="https://github.com/cisco/ChezScheme/blob/master/s/5_1.ss#L31" rel="noreferrer" target="_blank">https://github.com/cisco/<wbr>ChezScheme/blob/master/s/5_1.<wbr>ss#L31</a><br>
<br>
Probably less interesting/useful, but Racket-on-Chez currently has its<br>
own `equal?` to support chaperones and impersonators, and it has the<br>
same union-find part:<br>
<br>
  <a href="https://github.com/racket/racket7/blob/master/racket/src/cs/core/equal.ss" rel="noreferrer" target="_blank">https://github.com/racket/<wbr>racket7/blob/master/racket/<wbr>src/cs/core/equal.ss</a><br>
<br>
</blockquote></div><br></div>