Skip to content

A frozenset can be a member

Level: 201 · for Python programmers

One line: Python has two set types for one reason: a set can change after it is stored, so it cannot be hashed, so it cannot be a member of a set or a key of a dict; frozenset is the same set with every changing method removed, and in exchange it can be all of those things.

Why a second type

A set or a dict finds a member by its hash. If a member could change after it was filed, its hash would change with it, and the container would look in the wrong slot and fail to find it: the failure Defining __eq__ deletes __hash__ shows for a custom class. Python prevents it for sets by refusing to hash a set at all. frozenset is the other half of that bargain: no add, remove, update or |= in place, and therefore a hash that depends only on the members.

What that buys is exactly what mathematics does with sets all the time: sets whose members are sets. The set of all subsets of {1, 2, 3} has eight members, each of them a set, and in Python it can only be written with frozensets. An unordered pair used as a dict key is the everyday version: frozenset({'a', 'b'}) and frozenset({'b', 'a'}) are one key.

The output

Verified output of a_frozenset_can_be_a_member_py.py — regenerated by tools/run_examples.py, never hand-typed.

1. A SET CANNOT BE A MEMBER; A FROZENSET CAN
   {{1, 2}, {3}}                      -> TypeError
   {frozenset({1, 2}), frozenset({3})} -> {{3}, {1, 2}}
   every subset of {1, 2, 3}, as a set of frozensets: 8 members
     {{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}
   The set of all subsets needs sets as members, and so needs frozenset.

2. SAME MEMBERS, SAME HASH, WHATEVER THE ORDER
   frozenset([1, 2, 3]) == frozenset([3, 2, 1])            True
   hash(frozenset([1, 2, 3])) == hash(frozenset([3, 2, 1])) True
   frozenset({1, 2}) == {1, 2}                           True
   counting unordered pairs with frozenset keys:
     {1, 2}   seen 3 times
     {1, 3}   seen 2 times
   A pair and its reverse are one key: that is what an unordered pair is.

3. WHAT IT COSTS: NOTHING THAT CHANGES IT
   f.add(3)             -> AttributeError
   f.union([3])         -> {1, 2, 3}   a new frozenset; f is still {1, 2}
   f.copy() is f        -> True   no copy needed for something that cannot change
   t = frozenset({1}); u = t; t |= {2}  ->  t = {1, 2}, u = {1}, t is u: False
   |= on a frozenset builds a new object and rebinds t; u still sees the old one.
   type(frozenset({1}) | {2}) = frozenset,  type({2} | frozenset({1})) = set   the left operand decides

4. THE ONE PLACE PYTHON FREEZES A SET FOR YOU
   {1, 2} in sets                 -> True
   sets.remove({3})               -> leaves {{1, 2}}
   set membership, remove and discard accept a set argument and look it up
   as if it were frozen, although {1, 2} itself is unhashable.
   d = {frozenset({1, 2}): 'pair'};  d[{1, 2}]  -> TypeError
   d[frozenset({2, 1})]           -> 'pair'
   A dict does not do the conversion: freeze the key yourself.

What the run shows

Section 1 is the reason for the type: {{1, 2}, {3}} raises TypeError, and the same thing with frozensets works, including the eight-member set of all subsets.

Section 2 is why a frozenset is a good key: equal frozensets hash equal whatever order they were built in, and a frozenset equals a set with the same members. Counting unordered pairs with frozenset keys merges each pair with its reverse.

Section 3 is the cost. There is no add; union returns a new frozenset and leaves the old one alone; copy() returns the same object, since there is nothing to protect. And t |= {2} works, but not in place: with no __ior__, Python falls back to t = t | {2}, builds a new object and rebinds t, so another name for the old frozenset still sees {1}. That is the rule of += is not +, on a set. When a set and a frozenset are combined, the left operand decides the type of the result.

Section 4 is the surprise. {1, 2} in sets works although {1, 2} is unhashable: set membership, remove and discard quietly treat a set argument as if it were frozen. A dict does not: d[{1, 2}] raises TypeError, and the key has to be frozen by hand.

The Rust view

Rust has no frozenset, because it does not need one. Mutability belongs to the binding, let against let mut, not to the type, so one HashSet type serves both; and the borrow checker never hands out a &mut to an element stored in a set, so an ordinary member cannot change while it is filed. The exception is interior mutability: Cell and RefCell are not Hash, but they are Ord, so a BTreeSet<Cell<i32>> compiles, a member can be changed through &, and the set then fails to find a value it still holds. The compiler allows it; Clippy's mutable_key_type lint warns. What Rust does refuse is HashSet<HashSet<T>>: HashSet does not implement Hash. The ordered BTreeSet does, so a set of sets is written with BTreeSet as the element type, and collecting into a BTreeSet is Rust's "freeze" step. See the Rust library's sets of sets ↗.

If you are coming from ABAP

ABAP has no frozenset and no read-only table type; read-only is a property of how a table is reached, not of the table. A set of sets is built by freezing each inner set into something that can be a key, for example a canonical sorted string, and storing that in a HASHED table WITH UNIQUE KEY, which is what frozenset does for you. Changing a key field of a line already in a sorted or hashed table is refused at runtime, the ABAP form of "a member must not change while it is filed". See the ABAP library's sets of sets, and freezing a set ↗. (Not machine-checked — CI cannot run ABAP.)

Try it

  1. Search your code for dict keys built as sorted tuples of an unordered pair, tuple(sorted((a, b))), and decide whether frozenset((a, b)) says what you mean more directly. Check what happens when a == b.
  2. Find a set of sets you had to build as a list of sets, and rebuild it as a set of frozensets. Count the duplicates that disappear.
  3. Look for x in some_set where x might be a set, and for d[x] where d is a dict keyed by frozensets: the first works, the second raises.
  4. Take a frozenset held under two names and apply |= through one of them. Print both names and is.

Practice

Eight lines, and the lookup that works for a set but not for a dict. Write down what each prints.

  1. len({frozenset({1, 2}), frozenset({2, 1})})
  2. frozenset({1, 2}) == {2, 1}
  3. {1, 2} in {frozenset({1, 2})}
  4. {frozenset({1, 2}): 'x'}[{1, 2}]
  5. type(frozenset({1}) & {1, 2}).__name__
  6. type({1, 2} & frozenset({1})).__name__
  7. len({frozenset(), frozenset(set())})
  8. frozenset('abca') == frozenset('cab')

Then: say why line 3 is True when {1, 2} cannot be hashed, and how to make line 4 work.

Answers

Verified output of a_frozenset_can_be_a_member_kata_py.py — regenerated by tools/run_examples.py, never hand-typed.

1. len({frozenset({1, 2}), frozenset({2, 1})}) 1
2. frozenset({1, 2}) == {2, 1}                True
3. {1, 2} in {frozenset({1, 2})}              True
4. {frozenset({1, 2}): 'x'}[{1, 2}]           TypeError
5. type(frozenset({1}) & {1, 2}).__name__     'frozenset'
6. type({1, 2} & frozenset({1})).__name__     'set'
7. len({frozenset(), frozenset(set())})       1
8. frozenset('abca') == frozenset('cab')      True

Line 3 works because set membership converts a set argument to a temporary frozenset before hashing it; a dict lookup does no such conversion, so line 4 raises until the key is written frozenset({1, 2}). Line 7 is 1: both are the empty frozenset, and equal members make one member.

See also