From: Christoph Rippel <crippel@...>
Date: 2001-03-10T04:29:38+09:00
Subject: [ruby-talk:12353] Re: Q re looping structures

> -----Original Message-----
> From: Mathieu Bouchard [mailto:matju@sympatico.ca]
> Sent: Friday, March 09, 2001 08:28 AM
> To: ruby-talk ML; ts
> Cc: ruby-talk ML
> Subject: [ruby-talk:12336] Re: Q re looping structures
> 
> 
> 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.
> 
> 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.
Well,

we had a scheme which used id-bags/comparison cache
(in general see the Array-bug thread [ruby-talk:11288] Array bugs?
- Ben's comparison cache ``[ruby-talk:11739] Comparison Caching'' 
has the the most readable version). 
The problem with this scheme that it has  trouble to figure
out that looping structures like 

cl("a",100) == cl("a",101) 
with
def cl( a, n) #clone_loop
	base=loop= [a.clone]
	(n-1).times { tmp = [a.clone]; loop << tmp; loop = tmp }
       # close the loop
       loop << base
       return base
end

are equal - you accumulate  100*101 id-pairs before the algorithm
decides that they are equal.

We are working an untangle scheme which could be used as a basis 
for a more suffiticated equality notion - for example with
(a better un_cutter not at ftp yet you get ) 
a=[[42]];a<<a[0] 
b = [[42],[42]]
a.untangle!   
b.untangle!
p a     	## =>  [[42],[42]]
p b     	## => [[42],[42]]
p (a == b ) 	# true
 
# and 
loop6 = cl( [42], 7)
loop7 = cl (42], 6)

p loop6,loop7
#[[42], [[42], [[42], [[42], [[42], [[42], [[42], [...]]]]]]]]
#[[42], [[42], [[42], [[42], [[42], [[42], [...]]]]]]]


loop6.untangle!; loop7.untangle!
p loop6,loop7
#[[42], [[42], [[42], [[42], [[42], [[42], [[42], [[42]]]]]]]]]
#[[42], [[42], [[42], [[42], [[42], [[42], [[42]]]]]]]]

#so you could conclude that the original loop6, loop7
#are not equal since now you have
p loop6 != loop7 # => true


However I am apposed to such dubious equality notions  
RCO - aka recursive container object violate basic 
properties of any reasonable container class axioms 
(most users are not aware of this and a type exception 
would hammer this into their brains - in functional 
programming your compiler will immediately complain
if he/she sees something like this).

If you want to use a graph like interpretation (RCO's 
are actually not graphs - even in their most liberal
interpretation) you probably know what you are doing
and you change the equal operator if you want to.

Another good reason to not allow a  "graph like 
interpretation" that it would be way too expensive
for normal use ..


Christoph

[...]