Why are tuples immutable?

[Antoon Pardon]

Op 2004-12-17, Jeff Shannon schreef <jeff at ccvcorp.com>:
> Adam DePrince wrote:
>
>>And how exactly do you propose to mutate an object without changing its
>>hash value?
>>
>>
>>* Create this mutate-able object type.  
>>* Create two objects that are different with different hash values.
>>* Mutate one so that it is the same as the other.
>>* Compare their hash values.  
>>
>>If the hash values are the same, you lose because you didn't keep your
>>original promise.
>>
>>If the hash values are different then you just broke your object because
>>two objects with the same value must have the same hash value, but yours
>>are different.
>>  
>>
>
> Correct me if I'm wrong, here, but I believe that what you're saying 
> here (and my vague memories of the little bit that I've read about 
> hashes) is that, for a well-behaved hash function, then A == B should 
> imply that hash(A) == hash(B).  (The reverse is *not* true, however -- 
> hash(A) == hash(B) does not necessarily say anything about whether A == B.)
>
> If that is a correct condition for a well-behaved hash function, then it 
> is indeed impossible to have a well-behaved hash function that can be 
> useful in the face of object mutation.  For something like a list, one 
> can only define a poorly-behaved hash-like function.

You are looking at it in a too limited way. You are not forced to
have an == operator that behaves in standard ways. For instance
you can have objects that are only equal if they are the same
and thus can be unequal even if all components are equal.

Even if 

> 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


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.

> For most uses of 
> dicts, it is necessary that the first case be valid -- a dict isn't 
> going to be very useful to me if I have to pass around all of the 
> objects used as keys in order to access it. Equality-based hashes are 
> necessary, so the second case must then be disallowed.

But you should be carefull not to limit people to what you think is
usefull.

> But isn't it a bit nonsensical that, without ever rebinding key, one can 
> do something like
>
> .>>> d[key] = 'foo'
> .>>> frombulate(key)
> .>>> d[key]
> Traceback (most recent call last):
>   File "<interactive input>", line 1, in ?
> KeyError: key
> .>>>

It is just as nonsensical that, without ever rebinding an element, one
can unsort a list, or violate the heap invariant of a list.

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

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

-- 
Antoon Pardon