Pushing to a set of structs

General Usage
1

I define my struct as immutable, but it contains a mutable type. Hence when I try to add two of the “same” elements to a set, it adds it (as it should?)

struct Hand
    cards::Vector{Int}
end

DAG = Set{Hand}()
root = Hand([])
push!(DAG, root)
push!(DAG, Hand([]))

However, this is the case even when I define a custom == (as I naively thought this would fix it):

import Base: ==
==(hand1::Hand, hand2::Hand) = all(.==(hand1.cards, hand2.cards))

How do sets work in terms of knowing whether to add something or if it already exists? How can I put that into my struct?

2

Your instinct to extend Base.== is good. It is typically a good idea to read the docstring of functions that you implement to ensure you fulfill the contract (otherwise things like push! that rely on it might end up not fulfilling their contract either). ?== has a section headed Implementation:

Implementation
  ≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡

  New numeric types should implement this function for two arguments 
  of the new type, and handle comparison to other types via promotion 
  rules where possible.

  isequal falls back to ==, so new methods of == will be used by the 
  Dict type to compare keys. If your type will be used as a dictionary 
  key, it should therefore also implement hash.

  If some type defines ==, isequal, and isless then it should also 
  implement < to ensure consistency of comparisons.

From the second bullet point, you should also implement hash(hand::Hand). But dictionaries (and therefore sets) rely on stable hash values and will start to misbehave if you mutate a hand that is in a dictionary and its hash value changes. If you want to support this mutation (which your choice of Vector instead of Tuple or static vector seems to indicate) then you may be stuck with a simple Vector{Hand} with O(n) ∈ checks.

1 Like
3

Thanks for the concise reply, I had worried that there was something else I needed to implement to get the set to work properly so I studied the code for Set but not ==. I’ll look into other solutions given that I do indeed want the cards to be mutable. Of course there will be ways around this but for my current implementation inplace functions would be really nice to support.

4

As it turns out, implementing hash such that it does not hash the type, and hence every identical Hand is identically hashed is exactly the behaviour I wanted. This could be dangerous if the hands were mutated, but this is not the case as, when using sets, the Hands are added to a set and forgotten about for all intents and purposes.