python – What would a frozen dict be?

python – What would a frozen dict be?

Python doesnt have a builtin frozendict type. It turns out this wouldnt be useful too often (though it would still probably be useful more often than frozenset is).

The most common reason to want such a type is when memoizing function calls for functions with unknown arguments. The most common solution to store a hashable equivalent of a dict (where the values are hashable) is something like tuple(sorted(kwargs.iteritems())).

This depends on the sorting not being a bit insane. Python cannot positively promise sorting will result in something reasonable here. (But it cant promise much else, so dont sweat it too much.)


You could easily enough make some sort of wrapper that works much like a dict. It might look something like

import collections

class FrozenDict(collections.Mapping):
    Dont forget the docstrings!!

    def __init__(self, *args, **kwargs):
        self._d = dict(*args, **kwargs)
        self._hash = None

    def __iter__(self):
        return iter(self._d)

    def __len__(self):
        return len(self._d)

    def __getitem__(self, key):
        return self._d[key]

    def __hash__(self):
        # It would have been simpler and maybe more obvious to 
        # use hash(tuple(sorted(self._d.iteritems()))) from this discussion
        # so far, but this solution is O(n). I dont know what kind of 
        # n we are going to run into, but sometimes its hard to resist the 
        # urge to optimize when it will gain improved algorithmic performance.
        if self._hash is None:
            hash_ = 0
            for pair in self.items():
                hash_ ^= hash(pair)
            self._hash = hash_
        return self._hash

It should work great:

>>> x = FrozenDict(a=1, b=2)
>>> y = FrozenDict(a=1, b=2)
>>> x is y
False
>>> x == y
True
>>> x == {a: 1, b: 2}
True
>>> d = {x: foo}
>>> d[y]
foo

Curiously, although we have the seldom useful frozenset, theres still no frozen mapping. The idea was rejected in PEP 416 — Add a frozendict builtin type. This idea may be revisited in a later Python release, see PEP 603 — Adding a frozenmap type to collections.

So the Python 2 solution to this:

def foo(config={a: 1}):
    ...

Still seems to be the somewhat lame:

def foo(config=None):
    if config is None:
        config = default_config = {a: 1}
    ...

In Python 3 you have the option of this:

from types import MappingProxyType

default_config = {a: 1}
DEFAULTS = MappingProxyType(default_config)

def foo(config=DEFAULTS):
    ...

Now the default config can be updated dynamically, but remain immutable where you want it to be immutable by passing around the proxy instead.

So changes in the default_config will update DEFAULTS as expected, but you cant write to the mapping proxy object itself.

Admittedly its not really the same thing as an immutable, hashable dict, but it might be a decent substitute for some use cases of a frozendict.

python – What would a frozen dict be?

Assuming the keys and values of the dictionary are themselves immutable (e.g. strings) then:

>>> d
{forever: atones, minks: cards, overhands: warranted, 
 hardhearted: tartly, gradations: snorkeled}
>>> t = tuple((k, d[k]) for k in sorted(d.keys()))
>>> hash(t)
1524953596

Leave a Reply

Your email address will not be published. Required fields are marked *