Dictionary keys (again) (was Re: lambda)

[Antoon Pardon]

Op 2005-01-19, Nick Coghlan schreef <ncoghlan at iinet.net.au>:
> 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:

As you said yourself, people use shortcuts when they express themselves.
With 'mutable key' I mean a mutable object that is used as a key.
That doesn't contradict that the key itself can't change because
it is inaccessible.

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

That is usually the case when promisses are broken. To mention something
different, I guess a number of equally entertaining bug hunts can be
caused by the fact that the value in the dictionary is changed.

> Which solution is the best default behaviour?

IMO a dictionary establisches a relationship between values. The most
general implementation that protects this relationship from external
tampering is copying the key and value for use in the dictionary.

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

But python does guess in the case of the value. If I want to establish a
relationship between "foo" and [3, 5, 8] then I can be in big trouble
if that list gets mutated in something else.

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

But they don't have to be immutable within the dictionary itself, that
is just an implementation detail. The only thing that matters is that
the dictionary can reproduce the relationship. How that is done is
immaterial. 

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

No they don't, that is just the most easy implementation. If some
implementation would constantly change the internal objects but 
consulting the dictionary wouldn't show any different effect then
that would be fine too. And even in this case a mutation
from the outside would probably cause havoc because it would ruin
the sanity of the internal structure.

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

Well that would be a good thing IMO. Good enough in any case for me to
spend some time analyzing the requirements. Whether I'll actually
implement something depends on how much time I have and how often I
need it.

-- 
Antoon Pardon