Why are tuples immutable?

Antoon Pardon apardon at forel.vub.ac.be
Tue Dec 21 11:25:50 CET 2004


Op 2004-12-17, Jeff Shannon schreef <jeff at ccvcorp.com>:
> 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.

I have both, I just have a different == than the one you have in mind.
Nothing forces me to have two lists as equal just because there elements
happen to be equal.

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

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

Nonsense.

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

That is just your limited imagination. When I would use lists as keys in
such a way, I wouldn't care what value the key itself had. The value in
the dictionary would be associted with the list itself, not with the
value the list has at any one particular moment. Just as when you
want to know who the owner is of a particular car, you only care about
the identity of the car (its serialnumber) not its milage, color,
how much gas is in the tank etc...

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

No they don't. Just as I don't expect algorithms to handle sensible
when they expect a sorted list, but get an unsorted one because
the programmer was not carefull enough and mutated an element.

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

It is more among the lines as telling programmers not to mutate
objects in a sorted list, while future running code may expect it to
still be sorted.

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

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.

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

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

No it doesn't. [3,7,13] is just as hashable as (3,7,13). You will
find no mathematical argument why one would be hashable and the
other not.

> and Python doesn't try to pretend that it can hash mutable types.  

It doesn't has to pretend.

-- 
Antoon Pardon



More information about the Python-list mailing list