Why are tuples immutable?

[Antoon Pardon]

Op 2004-12-21, Jeff Shannon schreef <jeff at ccvcorp.com>:
> Antoon Pardon wrote:
>
>>Op 2004-12-21, Nick Coghlan schreef <ncoghlan at iinet.net.au>:
>>  
>>
>>>Antoon Pardon wrote:
>>>    
>>>
>>>>Why then doesn't python think the same about sorted lists. When I have a
>>>>sorted list and do operations on it that depend on it being sorted,
>>>>I can mess things up just as easily by mutating an element in that
>>>>sorted list as I can mess things up by mutating a dictionary key.
>>>>      
>>>>
>>>Incorrect, and this appears to be the point where our major disagreement lies.
>>>
>>>Mutate a value in a sorted list and you can fix that easily, just by calling its 
>>>sort() method again (and, in fact, mutate and resort is a fairly common idiom 
>>>for small datasets). 'sorted' and 'heapified' are list properties that are 
>>>easily broken by direct manipulation, but are also easily restored by once again 
>>>'sorting' or 'heapifying'.
>>>    
>>>
>>
>>That is an implemantation detail. Likewise a dictionary is probably not
>>always in a sane state when a new key is inserted. The fact remains that
>>in a sorted list or a heap, mutating an element arbitrarily can mess up
>>things greatly.
>>  
>>
>
> These comparisons to sorted lists and heaps are a red herring.  The 
> analogous situation to those is dictionary *values*, not dictionary keys 
> -- in essence, the "keys" of a list (whether sorted or not) are integers. 

No it is not a red herring. The analogy is not in the fact that sorted
lists have keys, but that sorted lists and heapqueues have an invariant
just like dictionary keys and that this invariant can be violated by
mutating the objects just as the dictionary invariant can be violated
by mutating a key. That sorted lists have keys too is just an
insignificant coincidense here.

>>>Change the hash value of an item used as a key in a dictionary, and *the 
>>>internal state of the dictionary is likely to broken in a manner you probably 
>>>cannot fix*. The only reason the 'probably' is there is because you should be 
>>>able to 'fix it' by changing the hash value back to what it was originally.
>>>    
>>>
>>
>>I could argue that this is then a failing of dictionary that doesn't
>>provide a method to clean up after a key is mutated.
>>  
>>
>
> So show us a dictionary (i.e. hash table) implementation that can do 
> this.

Why should I, Do you doubt that it is possible?

> You'll need to be able to derive the old hash from the new hash, 
> of course, so that you can correctly associate the values already stored 
> under that key.  And you'll have to be able to do that without referring 
> to the pre-modified object again, because dicts can't track every Python 
> operation that might modify a key object.  And it needs to deal properly 
> with equivalent-but-different-ID list literals, because using literals 
> (and not references stored elsewhere) is an important and common dict 
> key usage.
>
> If you can show me how you plan to accomplish this, I'll accept that 
> you're right on this.  Until then...

I don't have to accomplish all that in order to be able to clean up
a mutated dictionary key. All I need to do is go over the keys, see
if they hash to the same bucket as they are in now and otherwise
put them in the new bucket. Sure that would be costly, but so would
allowing arbitrary mutation in a sorted list and resorting everytime
or in a heapqueue and reheapifying.

>>>Waitasec - wouldn't it be easier if dictionaries just made it a rule that the 
>>>hash value wasn't allowed to change? Hang on, that's exactly what they do.
>>>    
>>>
>>
>>No it is not.
>>  
>>
>
> Seems to me that the docs are pretty clear on that.  It's true that 
> dictionaries can't enforce that the hash value never change over the 
> entire life of an object, because dicts can only take enforcement 
> actions when the dict itself is referenced -- but that's *why* it's 
> documented.

>>And yes I know what to do if I want to use mutable keys as objects. I'm
>>just argueing against those who think that should be somehow forbidden.
>>  
>>
>
> We're not arguing that it should be arbitrarily forbidden.  We're 
> arguing that doing anything else makes it impossible to behave 
> sensibly.

How does having stable keys in a mutable objects makes it impossible
to behave sensible for dictionaries?

> So prove us wrong,

I don't have to prove you wrong. If you want to argue something,
you have to provide reasoning that shows you right.

> by implementing something that behaves 
> sensibly in the face of mutating keys (which compare by value, as lists 
> do, rather than by identity).

You are confusing two things with each other. That is 1) a mutable object
that is a key and 2) a mutating key. Even if an object is mutable it can
be stable for some duration and thus unmutating. There is IMO nothing
wrong with using such mutable objects as dictionary keys or in other
structures that require an invariant. Requiring that such objects be
immutable and thus can't even mutate during periods they are not so
used, creates an unnecessary burden.

-- 
Antoon Pardon