Re: Will guile support R7RS terminating "equal?" in the presence of cycle?

[Mark H Weaver <mhw@netris.org>]

On 09/08/2012 09:35 PM, Alex Shinn wrote:
> On Sun, Sep 9, 2012 at 2:00 AM, Stefan Israelsson Tampe
> <stefan.itampe@gmail.com>  wrote:
>> You are right! That will only work for one thread!
>>
>> Remain to see how much the overhed there is to linearize the search and
>> use tourtoues - hare, should be much less overhead then using a map to
>> mark the objects though!
>
> See http://srfi.schemers.org/srfi-85/srfi-85.html
> for a common implementation approach.
>
> The basic idea there is just to run equal? normally,
> but keep a counter of how many objects have been
> compared.  If the count gets too high, there is a
> decent chance you have a cycle, and only then do
> you switch to a more expensive approach.
>
> You could of course use a modified hare and tortoise
> with the same goal of just detecting when a cycle
> has occurred and switching algorithms.  You only
> need to do this on one of the data structures, since
> if either is non-cyclic equal? will terminate naturally.
> This would be slightly more overhead than a counter,
> and probably require heap allocation to keep the
> search path in memory, but it removes the need to
> choose a good limit.  Small cycles will still be detected
> right away, and very long straight lists won't switch
> to the expensive algorithm.

Another option is to use the method described in "Efficient 
Nondestructive Equality Checking for Trees and Graphs" by Adams and Dybvig.

http://www.cs.indiana.edu/~dyb/pubs/equal.pdf

     Mark