In operator for set of sets

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?

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

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.

2 Likes

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.

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.

1 Like

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.

1 Like