>===== Original Message From Mathieu Bouchard <matju / sympatico.ca> =====
>On Sat, 10 Mar 2001, ts wrote:
>> >>>>> "M" == Mathieu Bouchard <matju / sympatico.ca> writes:
>
>> M> a=[7]; a<<a
>> M> b=[7,[7]]; b[1]<<b
>> M> a==b
>
>> >> -:4:in `==': detected recursive container object (TypeError)
>> M> No, I mean, if we were to say that such structures should be comparable,
>> M> i.e. if the result of a==b should be true or false, which one would you
>> M> pick and why?
>>  You have the response. In this case you can't give a result, this is why
>>  it give an error message.
>>  Perhaps Christoph Rippel can better explain it.
>
>
>
>Ok, I thought it would be possible to answer "true" meaningfully.

It is possible, and I posted code that does it before.

My code for <=> was unortunately not transitive.  That is
it is possible to find a, b, c, and d such that:

   0 == (a <=> c)
   0 == (b <=> d)
   1 == (a <=> b)
  -1 == (c <=> d)

I can test for that, but I have not yet posted that code.

>If the comparison is topological, the answer is obviously "false", but I
>don't think == should compare topology: only values should be compared, so
>that a=[[42]];a<<a[0] and [[42],[42]] stay equal.

This is true.

>OTOH, comparing only values, given any amount of time, the system cannot
>answer "false". And comparing object ids (as a helper) the system can also
>terminate and return true.

Yes.  You need to maintain a cache of what pairs of ids
have been seen together in this comparison, and return
true when you see that you have seen this match.  This
gives an equivalence relation, and it works out to,

  "this == that iff you cannot find any nested lookup
   on these things that can come up with a value on the
   one and either fails or comes up with an unequal
   value on the other."

This definition matches what most people think of as ==.

The case where this fails for <=> looks like this:

    a = [1]
    b = [2]
    a.unshift b
    b.unshift a
    c = [b, 1]
    d = [a, 2]

The problem is that this looks like:

    a == c == [[[[...], 2], 1], 2], 1]

and

    b == d == [[[[...], 1], 2], 1], 2]

and with a depth-first search, there is no meaningful
resolution of what <=> should do.  The best that you can
do is have some test for having mismatched on a left
recursive data structure (right-recursive ones not posing
a problem) and raise an exception.

Cheers,
Ben