Why are tuples immutable?
jeff at ccvcorp.com
Fri Dec 17 14:21:25 EST 2004
Antoon Pardon wrote:
>Op 2004-12-17, Jeff Shannon schreef <jeff at ccvcorp.com>:
>>To take another approach -- given some function that allows lists to
>>(pretend to be) hashable:
>>.>>> key = [1,2]
>>.>>> d[key] = 'foo'
>>As I understand it, it is impossible for there to be a hash function for
>>which both of these cases can return the same object.
> hash = id
If hash equals id, then the first of those cases fails. I'm creating a
new list with the same value but different. If hash *doesn't* equal id,
then the second case fails. It's an either-or proposition; you *cannot*
have both with mutable objects. And the proper definition of a hash
requires that you have both.
Now, even if hash were made to equal id... suppose I then pass that dict
to a function, and I want to get the value that I've stored under
[1,2]. In order to do that, I'd *also* have to pass in the *exact* list
that I used as the key, because *only* that *exact* instance will hash
correctly. Not only that, but if I've got a handful of such values that
I want to retrieve, I'll have to pass in *all* of the lists that I used
to key the dict. Any time I want to use the dict elsewhere, I need to
pass not only the dict itself, but a list of keys to the dict. And then
I need to know the order of the keys in that list. Ugh.
I suppose I could just use keys() to get a complete list of keys from
the dict itself. But still, I'd have to iterate over keys() to try to
find the proper list that matches the value that I need, and then use
the key to reference the dict. That leaves me with code like this:
for key in d.keys():
if key == [1,2]:
value1 = d[key]
if key == [1,3]:
value2 = d[key]
if key == [2,2]:
# and so on....
>You also make the fault that because people ask for the possibility of
>keys being mutable objects, that they want to mutate those object while
>being a key.
If mutable objects can be used as dict keys, then dicts *must* be able
to sensibly handle the keys being mutated underneath of them, because it
Your assumption that it's okay to make keys mutable, just tell
programmers not to do it, is along the same lines as assuming that
memory leaks in C aren't a problem because you've told programmers to
free() all of the memory that they malloc()'d.
>>In order to maintain the logical consistency that if an object is used
>>as a dict key, that same object should reasonably be expected to
>>retrieve the same value, identity-based hashes are necessary. As a
>>result, the first option must be disallowed.
>Then why don't we disallow lists of mutable objects to be sorted or
>to be made into a heap. In fact each time we have a structure that
>relies on some invariant among its members we should disallow mutable
>members because with mutable members the invariant can be violated
>without ever rebinding one of the elements.
If we have an object that, *by definition*, has some invariant that can
be violated by having mutable members, then sure. But lists aren't
sorted or heaped by definition.
Note also that, if a list becomes unsorted or unheaped, it's fairly easy
to resort or re-heapify the list. It may take some time, but nothing is
lost. If a dictionary key mutates, then data *is* lost.
>>In either case, if it's ever possible for equality to change while
>>identity doesn't, then somewhere along the lines one of the core
>>requirements, the contract if you will, of a dictionary *must* be
>>broken. And while it may be possible to get away with breaking that
>>contract some of the time (by postulating, for example, that if one
>>mutates a dict key then things will break), this will result in more
>>bugs and more confusion over time. There is no way for Python to be
>>able to behave consistently in the face of mutable dict keys, therefore
>>("In the face of ambiguity, refuse the temptation to guess.") Python
>>declines the temptation of making it trivial to use mutable objects as
>As it turns out, python makes no difference in difficulty for making
>either mutable or immutable objects usable as dictionary keys. The
>only difference is that python only made its standard immutable
>types hashable and not its standard mutable objects.
No -- the mathematical definition of 'hashable' fails for mutable types,
and Python doesn't try to pretend that it can hash mutable types.
Python also provides features so that user-defined immutable types can
be hashed properly, and those features can be abused to pretend to hash
user-defined mutable types, but that's not the same as saying that
Python is happy with mutable dictionary keys. (One can abuse __add__()
to do all sorts of things other addition, too, but it would still be a
stretch to say that Python supports using + to do multiplication, it
just doesn't provide it on standard numeric types.)
More information about the Python-list