[Python-Dev] Add a frozendict builtin type

[Steven D'Aprano]

M.-A. Lemburg wrote:
> Victor Stinner wrote:
>>> See also the PEP 351.
>> I read the PEP and the email explaining why it was rejected.
>>
>> Just to be clear: the PEP 351 tries to freeze an object, try to
>> convert a mutable or immutable object to an immutable object. Whereas
>> my frozendict proposition doesn't convert anything: it just raises a
>> TypeError if you use a mutable key or value.
>>
>> For example, frozendict({'list': ['a', 'b', 'c']}) doesn't create
>> frozendict({'list': ('a', 'b', 'c')}) but raises a TypeError.
> 
> I fail to see the use case you're trying to address with this
> kind of frozendict().
> 
> The purpose of frozenset() is to be able to use a set as dictionary
> key (and to some extent allow for optimizations and safe
> iteration). Your implementation can be used as dictionary key as well,
> but why would you want to do that in the first place ?

Because you have a mapping, and want to use a dict for speedy, convenient 
lookups. Sometimes your mapping involves the key being a string, or an int, or 
a tuple, or a set, and Python makes it easy to use that in a dict. Sometimes 
the key is itself a mapping, and Python makes it very difficult.

Just google on "python frozendict" or "python immutabledict" and you will find 
that this keeps coming up time and time again, e.g.:

http://www.cs.toronto.edu/~tijmen/programming/immutableDictionaries.html
http://code.activestate.com/recipes/498072-implementing-an-immutable-dictionary/
http://code.activestate.com/recipes/414283-frozen-dictionaries/
http://bob.pythonmac.org/archives/2005/03/04/frozendict/
http://python.6.n6.nabble.com/frozendict-td4377791.html
http://www.velocityreviews.com/forums/t648910-does-python3-offer-a-frozendict.html
http://stackoverflow.com/questions/2703599/what-would-be-a-frozen-dict



> If you're thinking about disallowing changes to the dictionary
> structure, e.g. in order to safely iterate over its keys or items,
> "freezing" the keys is enough.
> 
> Requiring the value objects not to change is too much of a restriction
> to make the type useful in practice, IMHO.

It's no more of a limitation than the limitation that strings can't change.

Frozendicts must freeze the value as well as the key. Consider the toy 
example, mapping food combinations to calories:


d = { {appetizer => fried fish, main => double burger, drink => cola}: 5000,
       {appetizer => None,       main => green salad,   drink => tea}:  200,
     }

(syntax is only for illustration purposes)

Clearly the hash has to take the keys and values into account, which means 
that both the keys and values have to be frozen.

(Values may be mutable objects, but then the frozendict can't be hashed -- 
just like tuples can't be hashed if any item in them is mutable.)



-- 
Steven