Dictionary keys (again) (was Re: lambda)

[Nick Coghlan]

Antoon Pardon wrote:
> A rule of thumb is context sensitive. If circumstances change,
> so do the rules of thumb. Principles have a broader field
> of application.
> 
> IMO there is nothing principally wrong with using a mutable object
> as a dictionary key. But avoiding doing so is a good rule of
> thumb if you have a python-like implementation of a dictionary.

For a 'mutable key' to make sense, the following:

lst = []
dct = {l: "Hi!"}
print dct[[]]
print dct[lst]
lst.append(1)
print dct[[1]]
print dct[lst]

Should print:
Hi
Hi
Hi
Hi

That's completely impractical though - for any sane implementation, at least one 
of the above print statements will throw a KeyError.

Your example of a 'safe_dict' that copies mutable keys means that the final 
print statement is the one that fails.

My suggestion of an "identity_dict" means that both of the same-value based 
lookups would fail.

Notice that both of these approaches take a mutable key and make it immutable 
(either by holding the sole reference to a copy, or retrieving an immutable 
property of the mutable object).

There's also your solution of "I promise not to mutate the key while it is in 
the dictionary". Workable, but opens the door to some entertaining bug hunts 
when the promise is broken.

Which solution is the best default behaviour?

Well, the Zen of Python states "In the face of ambiguity, refuse the temptation 
to guess".

So that's the policy the builtin dict follows - it doesn't try to guess when to 
make a copy, or whether or not to use identity based semantics in the face of 
mutability. Instead, it raises an exception at key entry time, asking the 
programmer to clarify their intent.

The principle is *certainly* that hash tables should contain immutable keys. 
Your own 'safe_dict' example implicitly concedes this point by making copies 
'when required'. 'When required' for what? When required to preserve 
immutability, perhaps?

In short, sane hash tables require immutable keys, and how mutable keys acquire 
the requisite immutability is going to be application dependent.

Provision of a safe_dict or identity_dict would merely allow a programmer to 
state their intent at the time the container is created, rather than having to 
state it whenever keys are generated or referenced.

Cheers,
Nick.

-- 
Nick Coghlan   |   ncoghlan at email.com   |   Brisbane, Australia
---------------------------------------------------------------
             http://boredomandlaziness.skystorm.net