Finding the type of indexing supported by an object?

[Derek Peschel]

Here are two functions.

def invert_dict_to_lists(dict):
lists = {}
for key in dict:
value = dict[key]
if not value in lists:
lists[value] = [key]
else:
lists[value].append(key)
return lists

def invert_list_to_lists(list):
lists = {}
for key in range(len(list)):
value = list[key]
if not value in lists:
lists[value] = [key]
else:
lists[value].append(key)
return lists

They are the same except for the expression in "for key in ...". Can they
be combined into one function? How can I determine if the argument is
like a list (with numeric indices that are not stored in the list) or a dict
(with arbitrary keys that are stored)? I said "object" in the subject,
but I want to support Python primitive types, class instances, extension
module types (array, dictproxy, dbm, gdbm, etc.), and any future types.

I've thought about looking for keys(), looking for the special method names
that allow you to override indexing behavior, and looking at the class or
type of the object. I could be wrong, but I don't think any of those
strategies will work with all arguments.

Thanks,

-- Derek

 

[Fredrik Lundh]

I've thought about looking for keys(), looking for the special method names
that allow you to override indexing behavior, and looking at the class or
type of the object. I could be wrong, but I don't think any of those
strategies will work with all arguments.

the behaviour of obj[arg] is determined by the __getitem__ method, and
that method can do whatever it wants.

</F>

 

[Peter Otten]

Here are two functions.

def invert_dict_to_lists(dict):
lists = {}
for key in dict:
value = dict[key]
if not value in lists:
lists[value] = [key]
else:
lists[value].append(key)
return lists

def invert_list_to_lists(list):
lists = {}
for key in range(len(list)):
value = list[key]
if not value in lists:
lists[value] = [key]
else:
lists[value].append(key)
return lists

They are the same except for the expression in "for key in ...". Can they
be combined into one function? How can I determine if the argument is
like a list (with numeric indices that are not stored in the list) or a
dict
(with arbitrary keys that are stored)? I said "object" in the subject,
but I want to support Python primitive types, class instances, extension
module types (array, dictproxy, dbm, gdbm, etc.), and any future types.

I've thought about looking for keys(), looking for the special method
names that allow you to override indexing behavior, and looking at the
class or
type of the object. I could be wrong, but I don't think any of those
strategies will work with all arguments.

Instead of the (unreliable) introspection approach you could let the client
code decide:
.... result = {}
.... for k, v in pairs:
.... if v in result:
.... result[v].append(k)
.... else:
.... result[v] = [k]
.... return result
....

invert(dict(a=1, b=2, c=1).iteritems()) {1: ['a', 'c'], 2: ['b']}
invert(enumerate([1,1,2,3]))

{1: [0, 1], 2: [2], 3: [3]}

Peter

 

[Alex Martelli]

Here are two functions.

def invert_dict_to_lists(dict):
lists = {}
for key in dict:
value = dict[key]
if not value in lists:
lists[value] = [key]
else:
lists[value].append(key)
return lists

def invert_list_to_lists(list):
lists = {}
for key in range(len(list)):
value = list[key]
if not value in lists:
lists[value] = [key]
else:
lists[value].append(key)
return lists

They are the same except for the expression in "for key in ...". Can they
be combined into one function? How can I determine if the argument is

They can easily be refactored, if that's what you mean:

def _invert_internal(container, keys):
lists = {}
for key in keys:
value = container[key]
if not value in lists:
lists[value] = [key]
else:
lists[value].append(key)
return lists

def invert_dict_to_lists(adict):
return _invert_internals(adict, adict)

def invert_list_to_lists(alist):
return _invert_internals(alist, xrange(len(alist)))

I've also performed a few other minor enhancements (never name things
dict or list because that hides the builtin types, use xrange vs range).
I have not changed the 4 lines in the if/else though I don't like them
(if not.../else is a very confusing construct -- at a minimum I'd
rephrase it as if/else swapping the bodies of the two clauses).

If you want to add a generic form accepting either lists or dicts you
need a try/except statement inside it, e.g.:

def invert_generic(container):
try:
container['zap']
except TypeError:
keys = xrange(len(container))
except KeyError:
keys = container
else:
keys = container
return _invert_internal(container, keys)

Of course there are all sort of fragilities here -- e.g., something like
invert_dict_to_lists({23:[45]}) will crash and burn. But that's quite
separate from the issue of distinguishing a dict from a list, which is
what the generic function is doing, showing how to handle exceptions for
the purpose. Of course, there's no way to use a "totally" generic
container, because there are no real limits to the keys it may accept
(including infinite sets thereof, computing values in __getitem__).


Alex

 

[Derek Peschel]

They can easily be refactored, if that's what you mean:

No, that isn't what I mean. I wanted _one_ function that works with a wide
variety of objects -- anything that has a finite number of keys you can
iterate over, with each key mapping to a finite number of values, and the
key iteration and value lookup referentially transparent. This hypothetical
function would have to do some checking of the argument type, but hopefully
as little as possible. It should work with object types invented after it
was written.

Reading everyone's replies, especially yours and Fredrik Lundh's, I realized
I've been thinking of the whole problem in Smalltalk (or possibly Ruby)
terms. Smalltalk and Ruby use inheritance to describe some properties of
objects. Python has many primitive types that aren't related to eaach other.
I thought that testing for methods might get the properties I wanted, but
you two pointed out that the method writer has too much latitude. Do you
think the generic-function idea is still useful?

At the moment I only need to invert dicts and lists. Is subclassing dict
and list considred good style? (I see I can't add methods to dict and list
directly.)

I've also performed a few other minor enhancements (never name things
dict or list because that hides the builtin types, use xrange vs range).

OK, I'll remember those points. The argument names are a style I got
from my Ruby code, and possibly not a good idea there either.

I have not changed the 4 lines in the if/else though I don't like them
(if not.../else is a very confusing construct -- at a minimum I'd
rephrase it as if/else swapping the bodies of the two clauses).

It used if/else originally. Then I swapped the parts of the conditional
to make the inversion function match another function (that takes a key,
old value, and new value, and makes the change in a sequence and in its
inverted form). To me the swapped version made some sense in the second
function, because of the layout of the function as a whole, but you have
a point that if not/else is rarely (never?) clear.

If you want to add a generic form accepting either lists or dicts you
need a try/except statement inside it, e.g.:

Is that a reliable way to get the properties I wanted?

RADLogic Pty. Ltd. added a two-way dict package to the Cheese Shop. It
requires that the mapping be one-to-one, which won't work for me. It sub-
classes dict, and requires that keys and values be hashable.

-- Derek

 

[Derek Peschel]

Instead of the (unreliable) introspection approach you could let the client
code decide:

See my reply to Alex Martelli's post, where I explain my original desire
for one function that works with a wide variety of present and future
object types. Your solution accomplishes that, but only by forcing the
caller to convert the argument to a list of pairs. If the caller knows the
type it's going to pass down, that's easy. If the caller doesn't know,
your approach doesn't seem any easier than mine.

In practice, with my needs of inverting dicts and lists, your solution might
not be a bad one.

-- Derek

 

[Fredrik Lundh]

At the moment I only need to invert dicts and lists. Is subclassing dict
and list considred good style?

if it makes sense for your application, sure.

however, it might be more convenient to just use a simple type check
(e.g. looking for items) to distinguish between "normal mappings" and
"normal sequences".

try:
items = obj.items()
except AttributeError:
items = enumerate(obj) # assume it's a sequence

</F>