# Trouble defining hash/isequal for an interval type

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

``````

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

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

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

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, âŚ .)).

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

1 Like

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"
``````

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

1 Like