Why is set nesting not implemented in Python?

Question

>>> li = [2, [3, 4]]
>>> 3 in li
False

>>> {2, {3, 4}}
TypeError: unhashable type: 'set'

Why is set nesting (which is used in mathematics) not implemented in Python (2.x and 3.x)?

Answer 1

It is implemented, but you need to use a hashable type instead. frozenset() is that type. The documentation even tells you so:

To represent sets of sets, the inner sets must be frozenset objects.

Demo:

>>> {2, frozenset([3, 4])}
set([frozenset([3, 4]), 2])

This is because a regular set() is mutable, which is incompatible with the requirements of the datastructure used for sets (and dictionaries); these require stable objects that can be re-located when used as a key in a table based on their hash.

The documentation again:

The set type is mutable — the contents can be changed using methods like add() and remove(). Since it is mutable, it has no hash value and cannot be used as either a dictionary key or as an element of another set. The frozenset type is immutable and hashable — its contents cannot be altered after it is created; it can therefore be used as a dictionary key or as an element of another set.

Answer 2

As @Martin Pieters mentioned, it is possible if you use frozenset objects instead of regular sets, because frozenset objects are hashable.

The reason for this is because the normal containers of python (list, dict, set, ...) are mutable, that means they can change in their lifetime (an element might be added to a set). mutable datatypes can't be hashable (since hashable basically means "identifying an immutable object with a unique number(=hash)).

frozenset objects are hashable, which means they can be used in sets, this comes at the cost of not longer being able to change the frozenset after it has been created (no update() method is available for frozenset). This means if you want to change a frozenset that is nested in a set, you have to create a new set from the frozen set, make your changes to that set, remove the old frozenset and convert the new set to a frozenset and add it (this seems convoluted, let me know if this is hard to understand).

The reason why sets can only consist of hashable objects has to do with the fact that every object in a set has to be unique to that set and python checks for that by using the hashes of the objects, since that is a efficient and safe way to do it.