Applying a function recursively

H

hetchkay

Hi,
I want to apply a "convert" function on an object as follows:
If the object is of MyType type, invoke the passed in function.
If the object is a dictionary, apply on the keys and values of the
dictionary recursively.
If the object is a set, list or tuple, apply on each element
recursively.
Else, leave the object as is.

I wrote the following code:
def convert(obj, func):
if isinstance(obj, MyType):
return func(obj)
elif isinstance(obj, dict):
return dict((convert(key, func), convert(value, func)) for key,
value in obj.iteritems())
elif isinstance(obj, (list, tuple, set)):
return obj.__class__(convert(x, func) for x in obj)
else:
return obj

Is there a better way to do this?
Is there any way I can make this code faster?

Regards,
Krishnan

C

Chris Rebert

Hi,
I want to apply a "convert" function on an object as follows:
If the object is of MyType type, invoke the passed in function.
If the object is a dictionary, apply on the keys and values of the
dictionary recursively.
If the object is a set, list or tuple, apply on each element
recursively.
Else, leave the object as is.

I wrote the following code:
def convert(obj, func):
Â  if isinstance(obj, MyType):
Â  Â  Â return func(obj)
Â  elif isinstance(obj, dict):
Â  Â  Â return dict((convert(key, func), convert(value, func)) for key,
value in obj.iteritems())
Â  elif isinstance(obj, (list, tuple, set)):
Â  Â  Â return obj.__class__(convert(x, func) for x in obj)
Â  else:
Â  Â  Â return obj

Is there a better way to do this?

None comes to mind.
Is there any way I can make this code faster?

Possibly, but it involves ignoring subclasses, and may not actually be
calls vs. cost of if-elif-else chain). It would be along the lines of:

def convert_mytype(obj, func):
return func(obj)

def convert_dict(obj, func):
return dict((convert(key, func), convert(value, func)) for key,
value in obj.iteritems())

def dont_convert(obj, func):
return obj

TYPE2FUNC = {MyType : convert_mytype, dict : convert_dict, ... }

def convert(obj, func):
return TYPE2FUNC.get(type(obj), dont_convert)(obj, func)

As they say though, premature optimization is the root of all evil.

Cheers,
Chris

H

hetchkay

I suspect, if you can be explicit about the goal you're aiming for with
this code, a better design can be found that doesn't require all those
polymorphism-breaking type checks.
It is difficult to explain what I am trying to do, but let me try. I
am mapping data from one hierarchy into another. The mapping rules are
quite complex. I developed a system such that the rules could be
defined as "expressions" of the source hierarchy i.e a particular
entry in the target hierarchy could be represented as an expression of
entries in the source hierarchy. Suppose a point is stored in x, y
coordinates in the source hierarchy, and in polar coordinates in the
target hierarchy, I could write (forget for the moment what sourcePt
is):
pointMapping = {
sourcePt.key : dict(
angle = Atan(sourcePt.value['y']/sourcePt.value['x']),
),
}
The above dictionary is delay-evaluated. sourcePt is an instance of a
class that facilitates the delayed evaluation. Sqrt, Atan etc. are
wrappers to the math functions to facilitate delayed evaluation. When
I encounter a point object, I could 'evaluate' the above mapping for
the point object to get the target dictonary.
The actual requirements are much more involved than this. The
motivation of the design was to enable application developers (who are
not experts in python) to be able to write the mappings. The mappings
You could consider this to be some sort of DSL. However, because of
the number of rules involved, I am trying to be as close to Python
expressions as possible. If the target setting is to be a tuple, for
example, I want to be able to write the tuple directly as "( expr1,
expr2 )", rather than, say, "Tuple(expr1, expr2)".
There is also a requirement to validate the mapping on load so that
run-time errors are minimized.
The system we are developing is quite reusable and we have been able
to use it for three different mappings so far. At this point, I am
trying to profile the code and noticed that a non-trivial amount of
time is being spent in the particular function I mentioned in this

Regards,
Krishnan

R

Roy Smith

[complicated description elided]
You could consider this to be some sort of DSL. However, because of
the number of rules involved, I am trying to be as close to Python
expressions as possible. If the target setting is to be a tuple, for
example, I want to be able to write the tuple directly as "( expr1,
expr2 )", rather than, say, "Tuple(expr1, expr2)".
There is also a requirement to validate the mapping on load so that
run-time errors are minimized.

I assume by DSL you mean Domain Specific Language? Having worked with a
number of DSLs, my emphatic recommendation is DON'T DO IT!

What you will end up with is a language which is almost, but not quite,
like some other existing language. That means the people who use it
will need to learn something new. If you make it "as close to Python as
possible", all that will happen is people will assume it's Python, and
constantly be surprised when things don't work the same way.

Whatever features of "real Python" you left out, people will invariably
be clamoring for. Eventually, you will be forced to duct-tape them into
the language. You will end up bogged down forever in language
maintenance, adding features, fixing bugs, writing documentation,
providing tech support, etc.

Think of all the ecosystem stuff which grows up around a real language.
Debuggers. Profilers. Language-aware editors (or plugins to emacs,
eclipse, etc). Add-in libraries to do a zillion things you never
thought you would want to do. Hoards of really smart and enthusiastic
people on mailing lists, newsgroups, Stack Overflow, etc willing to help
out with problems. Books. Professional training courses. You will end
up with replicating all that, or doing without.

It sounds like what you really want to do is just use Python as your
scripting language. The lazy evaluation features you desire can be
handled by writing some library code.