In operator for set of sets

New to Julia
,
1

Screen Shot 2020-11-19 at 10.46.02 PM
Screen Shot 2020-11-19 at 10.46.02 PM822×678 44.5 KB

Can I get some help with explaining this behaviour?

At first it seems that you can find the existence of a set within a set of sets, but after I make a modification to the set I cannot do so?

2

ok so I think the root cause is s.dict.slots is not updated due to the way you deleted an element in the keys of s.dict.

This is not limited to Set of Sets, you can reproduce this behavior even with a Set of Arrays

julia> s = Set([[1,2,3]])
Set{Array{Int64,1}} with 1 element:
  [1, 2, 3]

julia> [1,2,3] ∈ s
true

julia> deleteat!(only(s), 2)
2-element Array{Int64,1}:
 1
 3

julia> s
Set{Array{Int64,1}} with 1 element:
  [1, 3]

julia> [1,2,3] ∈ s
false

julia> [1,3] ∈ s
false
3

The problem is that Set is implemented as a Dict which in turn is backed by a hashtable using a combination of == and ===. After you delete! 3 from comp, the key is mutated to Set([4]), but it’s still stored where the hash function would expect to find Set[3,4].

I think what you want is

for comp in s
    delete!(s,comp)
    push!(s,delete!(comp,3))
end

i.e. remove the unmutated Set from the dictionary first, and replace it with the mutated Set.

This is a case of the more general problem of what happens when dictionary keys are mutable.
https://github.com/JuliaLang/julia/issues/33176

3 Likes
4

I think this is a bug, because the docstring for in says that it compares via isequal for Sets, and isequal(Set([4]), first(s)) is true in the example.

5

There is not really a way around this behavior though: objects stored in a Dict or Set must not be mutated in a way that changes their hash, otherwise all the functions which use it might fail. So rather than a bug, it could simply be a documentation issue.

2 Likes
6

Makes sense :slightly_smiling_face:. I’d still call it a bug (albeit a docs bug), because the semantics one can infer from the docs does not match what actually happens.

2 Likes