[ruby-talk:12365] Re: Q re looping structures

>===== Original Message From "Christoph Rippel" <[e-mail]> =====
>> From: Benjamin J. Tilly [mailto:[e-mail]]
>[...]
>> >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.
>Actually,
>
>they would not be equal in an almost identical situation
>if you set
>x =[42]
>s = [[42]]; s << s[0]
>and
>
>t = [[42],[42]]
>u = [x,x];
>
>you will get
>
>p (s == t), (t == u), (u != s )  # true,  true, false
>
Why would you expect u to be != to s?

The result looks very reasonable to me.

If s == t and t == u, then transitivity would require
that s == u and in this example that is exactly what
happens!!!
>
>i.e. the whole scheme stinks (I tested with your, mine
>and implemetation and Guys C extension  of id-bag/cache)
>- unfortunately we kept a bit of the level-unaware id-bag
>around so the current version of tangle as the same problem
> - i.e. it will conclude that  "s == t" before realizing
>that "s" is tangled - the good thing is that the corrected
>algorithm is even simpler and it can still handle the
>infamous example;-)

I remain unconvinced that this scheme stinks.

[...]
>> The problem is that this looks like:
>>
>>     a == c == [[[[...], 2], 1], 2], 1]
>>
>> and
>>
>>     b == d == [[[[...], 1], 2], 1], 2]
>
>it is actually a fun problem to construct
>these two arrays
>
In what you cut out I did construct them I thought.
>>
>> 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.
>
>an untangle (if we ever get the no bang version to work)
>could solve this problem but you alright know my opinion
>about this  ...

I strongly disbelieve that there is any answer in this
case that gives an answer you can argue is reasonable.
With breadth-first searches there is a unique answer that
makes sense.  But Ruby's existing behaviour is depth first,
and with depth first the answer that you get depends upon
how far down you go before breaking the recursion.

There are algorithms that give answers in this case.  My
code gave an answer in this case.  But that answer was
accidental in its details.  For instance your order
sensitive cache reverses the answer that my cache gives.
And transitivity is not satisfied.  In other words you
can get:

  a < b == d < c == a

and that is a completely unreasonable result.

I maintain that there is no reasonable way to extend a
depth-first ordering to left-recursive data structures.
I have no proof of this (how do you define "reasonable"?)
but I would be amazed if you can find one.

Cheers,
Ben

-------------------------------------------
The Fastest Browser on Earth now for FREE!!
Download Opera 5 for Windows now! Get it at
http://www.opera.com/download/
-------------------------------------------