Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #13052 > unrolled thread

Applying a function recursively

Back to article view | Back to comp.lang.python

Contents

  Applying a function recursively hetchkay <hetchkay@gmail.com> - 2011-09-10 00:19 -0700
    Re: Applying a function recursively Chris Rebert <clp2@rebertia.com> - 2011-09-10 00:40 -0700
    Re: Applying a function recursively Ben Finney <ben+python@benfinney.id.au> - 2011-09-10 18:13 +1000
      Re: Applying a function recursively hetchkay <hetchkay@gmail.com> - 2011-09-10 06:28 -0700
        Re: Applying a function recursively Roy Smith <roy@panix.com> - 2011-09-10 10:12 -0400

#13052 — Applying a function recursively

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

[toc] | [next] | [standalone]

#13053

On Sat, Sep 10, 2011 at 12:19 AM, hetchkay <hetchkay@gmail.com> wrote:
> 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
faster in your particular case (it comes down to additional function
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
--
http://rebertia.com

[toc] | [prev] | [next] | [standalone]

#13054

hetchkay <hetchkay@gmail.com> writes:

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

That smells like a bad design. Why are you using the same function for
al of those different behaviours?

That's not merely rhetorical; the design isn't absolutely wrong. But
it's wrong often enough that you need to have a compelling reason to
make such a complex behaviour in a single function.

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.

-- 
 \      “An expert is a man who has made all the mistakes which can be |
  `\                         made in a very narrow field.” —Niels Bohr |
_o__)                                                                  |
Ben Finney

[toc] | [prev] | [next] | [standalone]

#13069

>
> 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(
     radius = Sqrt(sourcePt.value['x']**2 + sourcePt.value['y']**2),
     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
also need to be readable.
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
thread.

Regards,
Krishnan

[toc] | [prev] | [next] | [standalone]

#13072

In article 
<4ee53496-ebec-4ee5-be0c-de344ac586c8@y39g2000prd.googlegroups.com>,
 hetchkay <hetchkay@gmail.com> wrote:

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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web