Trouble defining hash/isequal for an interval type

General Usage
, ,
1

I tried to practice on this topic, but evidently I still lack a lot of knowledge to be profitable.
I would like to be able to merge the two dictionaries so that, for example, merge(da,db) ==db
That is, having da and db keys equivalent, the second overwrites the first.
Where am I wrong and/or what is missing?

julia> h=hash(13)
0xa9497f3bd292fe31

julia> Base.hash(a::Interval, h::UInt) = xor(Int(a.lo*10+a.hi), h)

julia> import Base.==

julia> ==(a::Interval, b::Interval) = a.lo <= b.lo <=a.hi || b.lo <= a.lo <=b.hi
== (generic function with 187 methods)

julia> Base.isequal(a::Interval, b::Interval) = a.lo <= b.lo <=a.hi || b.lo <= a.lo <=b.hi

julia> a=Interval(0,2)
[0, 2]

julia> b=Interval(2,4)
[2, 4]

julia> b==a
true

julia> a==b
true

julia> isequal(a,b)
true

julia> isequal(b,a)
true

julia> da=Dict(a=>'a')
Dict{Interval{Float64}, Char} with 1 entry:
  [0, 2] => 'a'

julia> db=Dict(b=>'b')
Dict{Interval{Float64}, Char} with 1 entry:
  [2, 4] => 'b'

julia> da[a]
'a': ASCII/Unicode U+0061 (category Ll: Letter, lowercase)

julia> da[b]
ERROR: KeyError: key [2, 4] not found
Stacktrace:
 [1] getindex(h::Dict{Interval{Float64}, Char}, key::Interval{Float64})
   @ Base .\dict.jl:484
 [2] top-level scope
   @ c:\Users\sprmn\.julia\environments\v1.9.0\IntervalArit1.jl:62
2

It is a bit unclear to me what your goal is exactly. a and b are obviously different intervals, they just happen to have identical length. You (re)define hash, == and isequal for this type but you violate the constraint that hash(a) == hash(b) gives the same result as isequal(a, b). See the docstring of hash:

Compute an integer hash code such that `isequal(x,y)` implies `hash(x)==hash(y)`. The
optional second argument `h` is another hash code to be mixed with the result.

This also explains why your Dict da does find not a compatible entry with da[b].

3 Likes
3

In addition to the problem identified by @abraemer above (your isequal and hash functions are inconsistent), this is not a valid definition for == because it is not transitive.

4 Likes
4

This. The first thing you need to do is figure out what your equivalence classes are. Then implement checking if two intervals are in the same equivalence class for isequal. Finally implement hash that gives the same value for any two instances in the same equivalence class.

For intervals I presume you’d want to check that the endpoints of the interval are isequal. You could do other things though, like check that the first endpoint is equal or that the midpoint is equal. Those are kind of odd choices but they are valid equivalence classes.

3 Likes
5

What I was trying to do was to use (clumsily, I understand from your, @stevengj and @StefanKarpinski’s answers) an idea seen in an ‘other post’ of which I don’t remember the link in which the hash() and ==() functions were redefined for a new User Type.
The aim was to use a “special dictionary” to solve this problem.
The idea was to emulate the groupby function (to create equivalence classes and put them together as requested by the OP (at least as I understood it), via the mergewith!(combine, d1,d2, … .)).

6

I don’t get what the equivalence classes of intervals are supposed to be. Can you explain that?

1 Like
7

No, of course. In the way I had defined the relation is not of equivalence as it has no transitive property (as pointed out by @stevengj).
I just tried to explain (I use Google Translate to write in English :)) what I had improperly tried to do.
I finally realized that I couldn’t do what I wanted using the Dict structure.

Below is an example, following your instructions

julia> using IntervalArithmetic

julia> import Base: hash,==, isequal

julia> hash(a::Interval) = hash(a.lo-a.hi)
hash (generic function with 102 methods)

julia> ==(a::Interval, b::Interval) = a.lo-a.hi == b.lo - b.hi
== (generic function with 188 methods)

julia> isequal(a::Interval, b::Interval) = isequal(a.lo-a.hi, b.lo - b.hi)
isequal (generic function with 29 methods)

julia> a=Interval(0,2)
[0, 2]

julia> b=Interval(2,4)
[2, 4]

julia> c=Interval(-3,-1)
[-3, -1]

julia> da=Dict(a=>"a")
Dict{Interval{Float64}, String} with 1 entry:
  [0, 2] => "a"

julia> dc=Dict(c=>'c')
Dict{Interval{Float64}, Char} with 1 entry:
  [-3, -1] => 'c'

julia> db=Dict(b=>'b')
Dict{Interval{Float64}, Char} with 1 entry:
  [2, 4] => 'b'
julia> mergewith((x...)->join(x,'-'), da,db,dc)        
Dict{Interval{Float64}, Any} with 1 entry:
  [0, 2] => "a-b-c"
8

Yes, that looks correct—it considers all intervals with the same length to be equal.

1 Like