Antoon Pardon wrote:
Op 2004-12-17, Jeff Shannon schreef <[EMAIL PROTECTED]>:
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
-- http://mail.python.org/mailman/listinfo/python-list
