What makes an element eligible for a set membership test in Python? [duplicate]

Question

I would like to understand which items can be tested for set membership in Python. In general, set membership testing works like list membership testing in Python.

>>> 1 in {1,2,3}
True
>>> 0 in {1,2,3}
False
>>> 

However, sets are different from lists in that they cannot contain unhashable objects, for example nested sets.

List, okay:

>>> [1,2,{1,2}]
[1, 2, {1, 2}]
>>> 

Set, does not work because unhashable:

>>> {1,2,{1,2}}
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'set'
>>> 

Now, even if sets cannot be members of other sets, we can use them in membership tests. Such a check does not result in an error.

>>> {1} in {1,2,3}
False
>>> {1,2} in {1,2,3}
False
>>> set() in {1,2,3}
False
>>> 

However, if I try to do the same test where the element being tested is a dict, I get an error which suggests that the element being tested cannot be unhashable.

>>> {'a':1} in {1,2}
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'dict'
>>> {} in {1,2}
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'dict'
>>> 

That cannot be the whole story, because a set can be tested for membership in another set even if it is itself unhashable, giving a result rather than an error.

So the question is: What makes an element eligible for a set membership test in Python?

Answer 1

You cannot test membership of non-hashable elements in a set . Example -

>>> [1,2] in {1,2}
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
>>> {1:2} in {1,2}
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'dict'

The only non-hashable object that can be used for containment checking is set. As given in the documentation -

Note, the elem argument to the __contains__(), remove(), and discard() methods may be a set. To support searching for an equivalent frozenset, the elem set is temporarily mutated during the search and then restored. During the search, the elem set should not be read or mutated since it does not have a meaningful value.

To support searching for frozensets with same elements as a set, a set is temporarily mutated to frozenset() and compared. Example -

>>> set([1,2]) in {1,2,frozenset([1,2])}
True

Answer 2

The confusion comes because when you say 'if set in set', I think python is casting the left hand set to a frozenset and then testing that. E.g.

>>> f = frozenset({1})
>>> f
frozenset([1])
>>> x = {f, 2, 3}
>>> {1} in x
True

However, there is no equivalent to frozenset for a dict, so it cannot convert the dict to an immutable object for the membership test, and thus it fails.

I don't know the 'rule' that's followed here - whether there's some general method that can be overrideen to provide the immutable-conversion or if this behaviour is hardcoded to the specific case of set in set.