Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How/why does set() in {frozenset()} work?

Even though sets are unhashable, membership check in other set works:

>>> set() in {frozenset()}
True

I expected TypeError: unhashable type: 'set', consistent with other behaviours in Python:

>>> set() in {}  # doesn't work when checking in dict
TypeError: unhashable type: 'set'
>>> {} in {frozenset()}  # looking up some other unhashable type doesn't work
TypeError: unhashable type: 'dict'

So, how is set membership in other set implemented?

like image 901
wim Avatar asked Feb 13 '18 17:02

wim


People also ask

Why is a Frozenset () different from a regular set?

Frozen set is just an immutable version of a Python set object. While elements of a set can be modified at any time, elements of the frozen set remain the same after creation. Due to this, frozen sets can be used as keys in Dictionary or as elements of another set.

What is the diff between set and Frozenset?

Frozenset is similar to set in Python, except that frozensets are immutable, which implies that once generated, elements from the frozenset cannot be added or removed. This function accepts any iterable object as input and transforms it into an immutable object.

Is set immutable in Python?

Set Items. Items of a set in python are immutable (unchangeable), do not duplicate values, and unordered. Thus, items in a set do not appear in a stipulated manner, i.e., they can appear in a different order every time it is used. Due to this, set items cannot be referred to by key or index.

How do you use frozen set?

Frozen sets are a native data type in Python that have the qualities of sets — including class methods — but are immutable like tuples. To use a frozen set, call the function frozenset() and pass an iterable as the argument. If you pass a set to the function, it will return the same set, which is now immutable.


2 Answers

set_contains is implemented like this:

static int
set_contains(PySetObject *so, PyObject *key)
{
    PyObject *tmpkey;
    int rv;

    rv = set_contains_key(so, key);
    if (rv < 0) {
        if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
            return -1;
        PyErr_Clear();
        tmpkey = make_new_set(&PyFrozenSet_Type, key);
        if (tmpkey == NULL)
            return -1;
        rv = set_contains_key(so, tmpkey);
        Py_DECREF(tmpkey);
    }
    return rv;
}

So this will delegate directly to set_contains_key which will essentially hash the object and then look up the element using its hash.

If the object is unhashable, set_contains_key returns -1, so we get inside that if. Here, we check explicitly whether the passed key object is a set (or an instance of a set subtype) and whether we previously got a type error. This would suggest that we tried a containment check with a set but that failed because it is unhashable.

In that exact situation, we now create a new frozenset from that set and attempt the containment check using set_contains_key again. And since frozensets are properly hashable, we are able to find our result that way.

This explains why the following examples will work properly even though the set itself is not hashable:

>>> set() in {frozenset()}
True
>>> set(('a')) in { frozenset(('a')) }
True
like image 172
poke Avatar answered Oct 01 '22 05:10

poke


The last line of the documentation for sets discusses this:

Note, the elem argument to the __contains__(), remove(), and discard() methods may be a set. To support searching for an equivalent frozenset, a temporary one is created from elem.

like image 41
Patrick Haugh Avatar answered Oct 01 '22 06:10

Patrick Haugh