Why are tuples immutable?

[Nick Coghlan]

Jp Calderone wrote:
> On Fri, 17 Dec 2004 11:21:25 -0800, Jeff Shannon <jeff at ccvcorp.com> wrote:
> 
>   The correct characterization is that Python makes user-defined
> mutable classes hashable (arguably correctly so) as the default
> behavior.

However, that is only achieved by using identity based equality by default. If 
you inherit from something which *doesn't* use identity based equality (say, 
list or dict), then the hashability isn't there. So while you're quite correct, 
it doesn't affect the OP's original complaint (not being allowed to use a list 
as a dictionary key).

The Python docs are pretty precise about what the rules are:

"__hash__(self)
     Called for the key object for dictionary operations, and by the built-in 
function hash(). Should return a 32-bit integer usable as a hash value for 
dictionary operations. The only required property is that objects which compare 
equal have the same hash value; it is advised to somehow mix together (e.g., 
using exclusive or) the hash values for the components of the object that also 
play a part in comparison of objects. If a class does not define a __cmp__() 
method it should not define a __hash__() operation either; if it defines 
__cmp__() or __eq__() but not __hash__(), its instances will not be usable as 
dictionary keys. If a class defines mutable objects and implements a __cmp__() 
or __eq__() method, it should not implement __hash__(), since the dictionary 
implementation requires that a key's hash value is immutable (if the object's 
hash value changes, it will be in the wrong hash bucket)."

(from: http://www.python.org/dev/doc/devel/ref/customization.html)


The key points are:
   1. Objects which compare equal must have the same hash value
   2. An object's hash value must never change during it's lifetime

Lists could achieve the former, but not the latter. Tuples can achieve both, by 
virtue of being immutable, with immutable contents. Ditto for sets & frozensets.

If you want to 'freeze' a mutable object for use as a key, the class below 
forces the use of object identity for keying purposes. As I'm sure Jeff would be 
quick to point out, the downside is that keying by different objects with the 
same value *does not work* if their identities are different (or rather, it does 
work - they just get new entries in the dictionary). However, whether that 
actually matters is going to be application dependent.

Py> class KeyByIdentity(object):
...   __slots__ = ["_obj", "_hash_value", "__hash__", "__cmp__"]
...   def __new__(cls, obj):
...     self = object.__new__(cls)
...     self._obj = obj
...     self._hash_value = id(obj)
...     return self
...   def __hash__(self):
...     return self._hash_value
...   def __cmp__(self, other):
...     return cmp(self._hash_value, other._hash_value)
...
Py> d = {}
Py> key_list = []
Py> key_dict = {}
Py> d[KeyByIdentity(key_list)] = "Keyed by a list"
Py> d[KeyByIdentity(key_dict)] = "Keyed by a dict"
Py> print "\n".join([str(x._obj) + ": " + str(y) for x, y in d.items()])
[]: Keyed by a list
{}: Keyed by a dict
Py> key_list.append(3)
Py> key_dict["A"] = 3
Py> print "\n".join([str(x._obj) + ": " + str(y) for x, y in d.items()])
[3]: Keyed by a list
{'A': 3}: Keyed by a dict
Py> key_with_same_id = key_list
Py> d[KeyByIdentity(key_with_same_id)]
'Keyed by a list'
Py> key_with_new_id = list(key_list)
Py> d[KeyByIdentity(key_with_new_id)]
Traceback (most recent call last):
   File "<stdin>", line 1, in ?
KeyError: <__main__.KeyByIdentity object at 0x009DA418>

It would also be trivial to inherit from dict to make an "IdentityDict" which 
automatically used KeyByIdentity on its elements (using id() directly would be 
dangerous, as the dictionary then has no reference keeping the original object 
alive, thus failing to ensure the uniqueness of the keys - since id() only 
guarantees uniqueness with respect to currently existing objects).

Cheers,
Nick.

-- 
Nick Coghlan   |   ncoghlan at email.com   |   Brisbane, Australia
---------------------------------------------------------------
             http://boredomandlaziness.skystorm.net