Set of Sets and eql?

[Tim Sutherland]

I recently discovered the 'set' library after browing www.ruby-doc.org. It's
very useful - I'm using it all the time now. I especially like Set#classify.

One thing that tripped me up:

require 'set'

a = [1, 2].to_set
b = [3, 4].to_set

# Set of Sets
pairs = [a, b].to_set

e = [1, 2].to_set

p(pairs.include?(e)) # -> false
p(a == e) # -> true
p(a.eql?(e)) # -> false

This is with "ruby 1.9.0 (2004-02-28) [i686-linux]".

I've commented on `eql?' before, e.g. Structs used to use reference equality
(before 1.8).

I don't understand why we have eql? and don't just use == in Hashes. If people
occasionally want to use equal? for comparing Hash keys, then why don't we
have
class ReferenceHash < Hash
# Using equal? for comparison.
end

I can't imagine any circumstance where we want to use structural equality
for some types of keys, and equal? for other types. Either you want to use
structural equality for all of them, or equal? for all of them.

Additionally, set.rb defines Set#eql? as
def eql?(o) # :nodoc:
@hash.hash == o.hash
end

@hash is a Hash, and Hash#hash is Kernel#object_id.

This seems like an indirect way to define it (and a problem if Hash#hash was
ever changed to be something else). Why not do

def eql?(o) # :nodoc:
@hash.object_id == o.object_id
end

Or just not define Set#eql? at all and let Kernel#eql? do the same thing.
(Provided that Fixnum#== hasn't been redefined!)

 

[Tim Sutherland]

I don't understand why we have eql? and don't just use == in Hashes. If people
occasionally want to use equal? for comparing Hash keys, then why don't we
have
class ReferenceHash < Hash
# Using equal? for comparison.

# Also using #object_id for #hash.

end

[...]

 

[Tim Sutherland]

I don't understand why we have eql? and don't just use == in Hashes.

[...]

I just realised why

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#==.)

 

[Christoph]

Tim Sutherland wrote:
....

I just realised why

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