Dictionary keys (again) (was Re: lambda)

[Just]

In article <mailman.893.1106130899.22381.python-list at python.org>,
 Nick Coghlan <ncoghlan at iinet.net.au> wrote:

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

FWIW, the Cocoa framework on OSX supports mutable objects as keys. 
However, it makes an immutable copy. This is cheap for immutable objects 
-- Cocoa has both a mutable array as well as an immutable array, 
likewise for dicts -- since the "copy" will then simply be the same 
object. Thanks to PyObjC we can explore this from Python:

  Python 2.3 (#1, Sep 13 2003, 00:49:11) 
  [GCC 3.3 20030304 (Apple Computer, Inc. build 1495)] on darwin
  Type "help", "copyright", "credits" or "license" for more information.
  >>> from Foundation import *
  >>> lst = []
  >>> dct = NSMutableDictionary.alloc().init()
  >>> dct
  {}
  >>> dct[lst] = "Hi!"
  >>> dct
  {(1) = "Hi!"; }

(Note that Python lists get wrapped as native Cocoa arrays. '(1)' is 
Cocoa's repr for the wrapped array.)

  >>> dct[lst]
  u'Hi!'
  >>> lst.append(1)
  >>> dct[lst]
  Traceback (most recent call last):
   File "<stdin>", line 1, in ?
   File 
"build/lib.darwin-7.6.0-Power_Macintosh-2.3/objc/_convenience.py", line 
77, in __getitem__objectForKey
  KeyError: [1, 1]
  >>> dct.keys()
  ((1))
  >>> dct[[1]]
  u'Hi!'
  >>> k = dct.keys()[0]
  >>> k
  (1)
  >>> k.append(2)
  Traceback (most recent call last):
   File "<stdin>", line 1, in ?
   File 
"build/lib.darwin-7.6.0-Power_Macintosh-2.3/objc/_convenience.py", line 
205, in <lambda>
  objc.error: NSInternalInconsistencyException - *** -[NSCFArray 
addObject:]: mutating method sent to immutable object
  >>> 

This is not all that different from Python actually, in that Cocoa tries 
very hard to make it impossible to mutate dict keys.

Just