How to use list as key of dictionary?

[Duncan Booth]

Steven D'Aprano <steve at REMOVE-THIS-cybersource.com.au> wrote:



> Not quite, because that will also convert strings to tuples, which may 
> not be what you want for a general solution.

I take it you didn't actually try the original code then. Converting 
strings to tuples is not something it did.

> That works for all data types I've tried, and it insures that the keys
> it makes from different types are distinguishable:
> 
> e.g. 
> 
> make_dict_key([(1, 2), (3, 4)]) != make_dict_key({1: 2, 3: 4})

Really? It seems to me to be quite easy to get a clash:

>>> make_dict_key([])
(<type 'list'>,)
>>> make_dict_key((list,))
(<type 'list'>,)

> 
> and it is as close to reversible as it is possible to get. However,
> there is one limitation that makes it less than completely general: it
> doesn't handle cycles. If the prospective key K includes a reference
> to itself, Bad Things will happen.
> 
> (I leave fixing that limitation as an exercise for the reader.)
> 

>>> marker=object()
>>> def make_dict_key(K, ids=None):
    try:
        hash(K)
        return K
    except TypeError:
        if ids is None:
            ids = {}
        if id(K) in ids:
            return marker, ids[id(K)]
        ids[id(K)] = len(ids)
        # Not hashable, so can't be used as a dictionary key.
        if isinstance(K, dict):
            return (type(K),) + tuple(
            (key, make_dict_key(value, ids)) for (key, value) in K.iteritems())
        else:
            try:
                return (type(K),) + tuple(make_dict_key(x, ids) for x in K)
            except TypeError:
                # K is not a sequence-like object.
                return (type(K), repr(K))

        
>>> a = [1, 2, 3]
>>> b = [4, 5, 6]
>>> a[1] = b
>>> b[1] = a
>>> c = [1, a, b]
>>> make_dict_key(c)
(<type 'list'>, 1, (<type 'list'>, 1, (<type 'list'>, 4, 
(<object object at 0x00A30468>, 1), 6), 3), (<object object at 0x00A30468>, 2))