Set of Sets and eql?


(Christoph) #1

Tim Sutherland wrote:

I just realised why :slight_smile:

It’s because we require that a.eql?(b) implies a.hash == b.hash.

Forcing people who define #== to be structural equality to also define #hash
to follow this would be an onerous restriction.

Similarly, defining Set#hash that behaves nicely if eql? is == is tricky
because we don’t have a nice ordering of elements in the set. Need something
like SortedSet but with sort_by to use ==. (Since element#<=> does not have
to match element#==.)

You don’t need an ordering to define a nice Set#eql?
(resp. Set#hash) method. Essentially something like

class Set
def eql?(rhs)
rhsh = @rhs.hash
return false unless @hash.size == rhsh.size
@hash.each_key {|e| return false unless rhs.has_key?(e)}
return true
end

def hash
   # some silly order independent hash ...
   hsh  = @hash.size + 1743
   _hsh = hsh*hsh
   @hash.each_key {|e|
ehsh = e.hash
hsh += ehsh
     _hsh ^= (ehsh >> 13)
   }
   return (hsh && _hsh) + hsh
end

end

would do. The Set class author was certainly aware of this
possibility but (probably) decided against it since he modeled
his Set class more closely around Ruby’s Hash class than
classical mathematical sets. The current Set#<=> implementation
is IMO even more debatable since it is based on the sets size
rather than their actual members (this is akin to the dubious
Complex#<=> definition which which still ticks me off after > 3
years).

/Christoph