When are immutable tuples *essential*? Why can't you just use lists *everywhere* instead?

[Gabriel Genellina]

Heh, heh. I was wondering, if we dig deep enough, wether we'll
end up back at, "just an optimization," as the reason.

Fortran guys could make programs for a long time having arrays as their
ONLY structured type, so having a built in dictionary is not just an
optimization, it's a luxury!

 

[Steve Holden]

So the question becomes: Why do Python dictionaries require keys
to be of an immutable type?

Because otherwise people would expect to be able to use a list to select
a dictionary entry even after they'd modified elements of the list after
creating the dictionary entry. Which they couldn't. So Python doesn't
let them use lists.

regards
Steve

 

[Neil Cerutti]

Because otherwise people would expect to be able to use a list
to select a dictionary entry even after they'd modified
elements of the list after creating the dictionary entry. Which
they couldn't. So Python doesn't let them use lists.

The interpreter explains it: "A list is not a hashable object."
Choosing a hash table instead of some kind of balanced tree seems
to be just an optimization.

 

[Mel Wilson]

The interpreter explains it: "A list is not a hashable object."
Choosing a hash table instead of some kind of balanced tree seems
to be just an optimization.

Even with a balanced tree, if a key in a node changes value, you may
have to re-balance the tree. Nothing in a Python list says that a
dictionary tree would have to be re-balanced if you changed that
particular list.

Mel.

 

[Thomas Nelson]

Even with a balanced tree, if a key in a node changes value, you may
have to re-balance the tree. Nothing in a Python list says that a
dictionary tree would have to be re-balanced if you changed that
particular list.

Mel.

You don't have to look at any implementation. A dictionary maps every
key to exactly one object. If the objects were mutable, you could
change one key to another key, and then which item would the
dictionary pull?
(Imaginary code)
d = {[1,2,3]: 'hat', [1,2,4]: 'sock' }
for key in d:
key.pop()
print d[[1,2]] #does this print hat or sock?

Sets have the same problem. A set can't have duplicates; how could
you enforce this with mutable objects?

Tom

 

[Neil Cerutti]

Even with a balanced tree, if a key in a node changes value,
you may have to re-balance the tree. Nothing in a Python list
says that a dictionary tree would have to be re-balanced if
you changed that particular list.

You don't have to look at any implementation. A dictionary
maps every key to exactly one object. If the objects were
mutable, you could change one key to another key, and then
which item would the dictionary pull?
(Imaginary code)
d = {[1,2,3]: 'hat', [1,2,4]: 'sock' }
for key in d:
key.pop()
print d[[1,2]] #does this print hat or sock?

That would be documented as undefined behavior, and users
exhorted not to do such things.

Python's dictionaries are a proven winner--I'm definitely not an
advocate for changing them. But the general requirement for a
mapping container *isn't* that keys be immutable, but that you
either don't mutate keys, or don't do so without also reording
(rehashing?) the mapping.

 

[Steve Holden]

Even with a balanced tree, if a key in a node changes value,
you may have to re-balance the tree. Nothing in a Python list
says that a dictionary tree would have to be re-balanced if
you changed that particular list.

You don't have to look at any implementation. A dictionary
maps every key to exactly one object. If the objects were
mutable, you could change one key to another key, and then
which item would the dictionary pull?
(Imaginary code)
d = {[1,2,3]: 'hat', [1,2,4]: 'sock' }
for key in d:
key.pop()
print d[[1,2]] #does this print hat or sock?

That would be documented as undefined behavior, and users
exhorted not to do such things.

Python's dictionaries are a proven winner--I'm definitely not an
advocate for changing them. But the general requirement for a
mapping container *isn't* that keys be immutable, but that you
either don't mutate keys, or don't do so without also reording
(rehashing?) the mapping.

And which API do you use to "reord(er?) (rehash) the mapping"?

regards
Steve

 

[Neil Cerutti]

And which API do you use to "reord(er?) (rehash) the mapping"?

A pretty complex an unnecessary one, I'd guess. Since you
would most likely need to remove the changed key from the
mapping, and then reinsert the new one, it's just as well to
leave the whole process entirely up to the user.

Which is how Python currently works.