Why are tuples immutable?

[Jeff Shannon]

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'
>>.>>> d[[1,2]]
>>????
>>.>>> key.append(3)
>>.>>> d[key]
>>???
>>.>>>
>>
>>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.
>>    
>>
>
>How about:
>
>  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:

    def process_dict(d):
        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....

Double ugh.

>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 
*will* happen. 

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 
>>dict keys.
>>    
>>
>
>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.)

Jeff Shannon
Technician/Programmer
Credit International