From: Christoph Rippel <crippel@...>
Date: 2001-03-10T12:16:36+09:00
Subject: [ruby-talk:12366] Re: Q re looping structures

> From: Benjamin J. Tilly [mailto:ben_tilly@operamail.com]
[...]
> Why would you expect u to be != to s?
Because I am moron (you should realize by
know that can't distinguish between +/- ;-)
but I realized this when pressed the send 
button - to late ... 

> 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 remain unconvinced that this scheme stinks.
Because it breaks current code - big time

p ([1,[1]] == [1,[1,[1]])  # => false current ruby

p ([1,[1]] == [1,[1,[1]])  # => true with Ben's id caching

(this is with your script I re-attached to make
sure that there is no confusion ). Actually my
version of id-caching never had this problem
but I still don't like it because a lot of things
in ruby actually depend on the equality notion of
arrays (you use this constantly even when your not
aware of this).
Right now at least the interpreter is crashing - 
if a dubious equality notion is introduced some
scriot will produce garbage because RCO violate 
basic Container axioms (and you know this as well
as I do).

The basic problem is the following - lets say 

a = [1]; a <<a
b = [1]; bm =[1]; b << bm;  bm << b;

then with any id-caching you will get
p  a== b  # => true

From this you cleverly conclude that if set

a[0] = 2; b [0] = 2

then  ``a == b'' right?  - but wrong with
id-caching - admittedly Ruby has a lot of side 
effects but to support something like this is 
just nonsense IMHO.


> >> 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.
I know - I was thinking of [[[..],2],1]

> >>
> 
> 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.

Okay I don't want to introduce such a comparison if both
sides are ``tangled'' but if you untangle the loops you
can compare them as normal arrays - all the axioms
would be satisfied (you have to use a version which is 
non-destructive because the left hand side and right 
side could be ``inter-tangled'' and you don't want to 
destroy your original RCO even so they deserve it;-)
But tangled bases comparison as also side-effect problem 

[...]
Christoph

I only added three ``\'' at the ? to make it work ...
-----------------
$ ruby bad_equal.rb
true
true
-----------------
require 'Ben'
def cl( a, n)
   base=loop= [a.clone]
   (n-1).times { tmp = [a.clone]; loop << tmp; loop = tmp }
   loop << base
   base
end

p (cl("a",1) == cl("a",101))  # all id-cachings have this problem
p ([1,[1]] == [1,[1,[1]]])
-----------------
class Object
  def  eq? (other, cache)
    id == other.id ? \
      true :
      self == other
  end

  def cmp (other, cache)
    id == other.id ? \
      0 :
      self <=> other
  end
end

class SeenCache
  attr :seen

  def initialize
    @seen = Hash.new nil
  end

  def visited? (this, that)
    if @seen[this].nil?
      @seen[this] = [ that ]
    else
      return true if @seen[this].include? that
      @seen[this].push that
    end
    false
  end

end

class Array
  def <=> (other)
    cmp(other, SeenCache.new)
  end

  def cmp (other, cache)
    if (id == other.id or cache.visited? (id, other.id))
      return 0
    else
      other_a = other.to_ary
      min = length < other_a.length ? \ 
        length :
        other_a.length
      for i in 0..(min - 1)
        val = self[i].cmp(other[i], cache)
        return val unless val == 0
      end
      length <=> other_a.length
    end
  end

  def == (other)
    eq? (other, SeenCache.new)
  end

  def eq? (other, cache)
    if (other.kind_of? (Array) and length == other.length)
      if (id != other.id and not cache.visited? (id, other.id))
        for i in 0...(length - 1) do
          return false unless self[i].eq? (other[i], cache)
        end
      end
      return true
    else
      return false
    end
  end

end