[Python-Dev] Add a frozendict builtin type

[Victor Stinner]

Updated patch and more justifications.

New patch:
 - dict doesn't inherit from frozendict anymore
 - frozendict is a subclass of collections.abc.Mutable
 - more tests

>  * frozendict.__hash__ computes hash(frozenset(self.items())) and
> caches the result is its private hash attribute

hash(frozenset(self.items())) is preferred over
hash(sorted(self.items())) because keys and values may be unorderable.
frozenset() is faster than sorted(): O(n) vs O(n*log(n)).

frozendict hash doesn't care of the item order creation:

>>> a=frozendict.fromkeys('ai')
>>> a
frozendict({'a': None, 'i': None})
>>> b=frozendict.fromkeys('ia')
>>> b
frozendict({'i': None, 'a': None})
>>> hash(a) == hash(b)
True
>>> a == b
True
>>> tuple(a.items()) == tuple(b.items())
False

frozendict supports unorderable keys and values:

>>> hash(frozendict({b'abc': 1, 'abc': 2}))
935669091
>>> hash(frozendict({1: b'abc', 2: 'abc'}))
1319859033

>  * Add a frozendict abstract base class to collections?

I realized that Mapping already exists and so the following patch is enough:

+Mapping.register(frozendict)

> 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.

Victor
-------------- next part --------------
A non-text attachment was scrubbed...
Name: frozendict-2.patch
Type: text/x-patch
Size: 29099 bytes
Desc: not available
URL: <http://mail.python.org/pipermail/python-dev/attachments/20120228/c2ed03a7/attachment-0001.bin>