How to use list as key of dictionary?

[Steven D'Aprano]

On Tue, 06 Nov 2007 10:46:48 +0100, Wildemar Wildenburger wrote:

> Davy wrote:
>  > Hi Matimus and Boris,
>  >
>  > Thank you :)
>  >
>  > And a further question about vector above rank 1, how can I use it as
>  > the key of dictionary?
>  >
>  > For example, if I have list like L=[[1,2,3],[4,5,6,7]], Then I do
>  > L_tuple = tuple(L)
>  >>>> L_tuple = ([1,2,3],[4,5,6,7])
>  > But {L_tuple:'hello'} cause an error?
>  >
> Yes, because your key still contains mutable elements. That should not
> surprise you. If it does, please (re-)read
> <URL:http://docs.python.org/tut/node7.html#SECTION007500000000000000000>
> and <URL:http://docs.python.org/lib/typesmapping.html>.
> 
> maybe something like this could help:
> 
> def tupleize(non_tuple):
>      try:
>          return tuple(tupleize(thing) for thing in non_tuple)
>      except TypeError:
>          # non_tuple is not iterable
>          return non_tuple


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

For the specific example given, a list of lists:


list_of_lists = [[1,2,3], [2,3,4], [5,5,5]]
tuple_of_tuples = tuple([tuple(x) for x in list_of_lists])


The above solution might not scale for deeply nested data structures, or 
for arbitrary lists, but it may solve the Original Poster's problem.

An *almost* completely general solution is quite involved (and probably 
overkill for most practical uses):

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


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})

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



-- 
Steven.