Why are tuples immutable?

[Antoon Pardon]

Op 2004-12-21, Jeff Shannon schreef <jeff at ccvcorp.com>:
> Antoon Pardon wrote:
>
>>Op 2004-12-17, Jeff Shannon schreef <jeff at ccvcorp.com>:
>>  
>>
>>>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.
>>>    
>>>
>>
>>Maybe that is what I want.
>>  
>>
>
> Then use a class instance, rather than a list.  It's too valuable 
> elsewhere to have lists that compare by value rather than identity.

That doesn't answer your original objections. Using a class instance
instead of a list, will not make it any less strange to have two
instance be unequal when all components are equal.

>>That doesn't change the fact that conceptually a programmer can use
>>them that way. So do you think that if a programmer uses a list
>>as a heap or a sorted list he should limit his object to immutable
>>objects. Are you saying that programmers shouldn't sort mutable
>>objects.
>>  
>>
>
> I'm saying that your analogy of list/heap *values* to dictionary *keys* 
> is a bogus analogy.  Dictionary *values* have no restrictions against 
> mutation, just as list/heap values have no restrictions.

Yes a heapqueue has restricions. A heapqueue has an invariant among
its elements and that invariant can be violated if you mutate them.

The same when a list is sorted. The list then has an invariant and
that invariant can be violated by mutating the elements.

> I'm also saying that a sorted/heaped list can be easily fixed by 
> examining the items in it.  A broken hash table *cannot* be fixed that 
> way. 

Yes it can. You can go over the keys and see if the hash puts them in
the same buckets as they are already in and move them if they are not.

>>>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. 
>>>    
>>>
>>
>>Is it? I don't see why an items method should fail to provide all (key,
>>value) pairs even when keys were mutated.
>>  
>>
>
> How does the dict know which value is associated with which key? 

Because there is a link between the key and the value. The problem
with a mutated key in a dictionary is not that the link between the
key and the value is severed, but that the key hashes now to a different
bucket. But if you just go over the buckets and iterate over the keys
within and there associated values, you will encouter your mutated
key with its value.

> I need to be able to access sequence-keyed dictionaries with literals, 
> which means that the keys need to compare by value, not ID.  Thus, I 
> need to have sequences that compare (and hash) by value.  These 
> conditions *cannot* be met by a mutable list.

Which condition can't be met by a mutable list? The only ones I see
above is comparison and hashable by value. A list can be compared
and hashed by value.

> I can have the quality of 
> hash value not changing when mutated, or I can have the quality of 
> hashing by value, but I *cannot* have both.

So? You don't need the first.

> Thus, even if you make 
> lists hash by ID, I *still* need to have an immutable tuple type so that 
> I can get hash-by-value. 

No you don't. The same algorithm that works for hashing tuples will
work just as fine for hashing lists.

> Given that lists simply cannot replace every usage of tuples as 
> dictionary keys,

Yes they can. I wouldn't advise it but they can.

> the question becomes only one of which is more 
> important -- that lists compare to each other by value, or that lists 
> are usable as dictionary keys.  Given the ease of using compare-by-ID 
> class instances instead of lists, and the general usefulness of having 
> lists compare by value, I think that Python made the right choice.

And what choice would that be? Python has no problems with lists as
dictionary keys. Subclass list to provide a __hash__ method and the
result is a list that is usable as a dictionary key.

-- 
Antoon Pardon