473,695 Members | 2,095 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Style question on recursive generators

Hello all,

Here I am using some deeply nested, tree-like data structures. In some
situations I need to traverse the tree; the old-style way to do it is
to write a recursive method on the node class, as in:

def walk(self):
"""old-style recursive tree traversal"""
child.do_someth ing
for child in childs:
child.walk()

Of course, "do_somethi ng" can be a configurable method or action on
the node, whose actual implementation doesn't matter for this
discussion. The recursive solution is clean and readable, and that's
why its frequently preferred over the iterative solution, which (a)
requires manual housekeeping (using a stack) to work; and (b) is not
truly 'object oriented', in the sense that it does not delegate node
traversal behavior to the node being traversed.

In my last projects I've been tending towards a greater use of
generators. However, when a generator is used in the situation
described above, the end result does not 'read' as naturally:

def walk(self):
"""generato r-based recursive tree traversal"""
yield child
for child in childs:
for node in child.walk()
yield node

The problem is that I need to 'chain' the yields from the subtrees to
yield back the result to the caller. It does not seem to be as elegant
as the simple recursive version; it's confusing to read, because one
has to figure out what is being yielded in the inner loop, and it's
also error-prone -- it's easy to forget to include the 'yield' in the
inner loop.

I'm now wondering which is better: to keep using old-style recursive
tree traversal code, or to chained-yield generator solution. It's more
of a stylistic decision -- I'm not concerned about raw performance at
this point, but clarity and elegancy of design are more important.

--
Carlos Ribeiro
Consultoria em Projetos
blog: http://rascunhosrotos.blogspot.com
blog: http://pythonnotes.blogspot.com
mail: ca********@gmai l.com
mail: ca********@yaho o.com
Jul 18 '05 #1
19 2287
Carlos Ribeiro wrote:
Hello all,

Here I am using some deeply nested, tree-like data structures. In some
situations I need to traverse the tree; the old-style way to do it is
to write a recursive method on the node class, as in:

def walk(self):
"""old-style recursive tree traversal"""
child.do_someth ing
for child in childs:
child.walk()
[...]
def walk(self):
"""generato r-based recursive tree traversal"""
yield child
for child in childs:
for node in child.walk()
yield node
[...] I'm now wondering which is better: to keep using old-style recursive
tree traversal code, or to chained-yield generator solution. It's more
of a stylistic decision -- I'm not concerned about raw performance at
this point, but clarity and elegancy of design are more important.


You must also consider the code that uses the iteration, at least if you
want to walk the structure for multiple purposes

# In the recursive case
def nodeHandler (node):
node.do_somethi ng ()

root.walk (nodeHandler)

# in the generator case
for node in root.walk ():
node.do_somethi ng ()

And the latter can also be fed into routines that expect an iterator.

Compare also os.path.walk with os.walk.

Daniel
Jul 18 '05 #2
On Mon, 18 Oct 2004 14:11:53 +0200, Daniel Dittmar
<da************ @sap.corp> wrote:
You must also consider the code that uses the iteration, at least if you
want to walk the structure for multiple purposes

<snip>

Compare also os.path.walk with os.walk.

Daniel
--
http://mail.python.org/mailman/listinfo/python-list


Yes, that's a good point, and it's one of the reasons I tend to prefer
the generator now. But anyway, it's just me, or does the 'chained
yield' look ugly to someone else? It may be just a question of getting
used to it, but nevertheless it's bugging me...
--
Carlos Ribeiro
Consultoria em Projetos
blog: http://rascunhosrotos.blogspot.com
blog: http://pythonnotes.blogspot.com
mail: ca********@gmai l.com
mail: ca********@yaho o.com
Jul 18 '05 #3
Carlos Ribeiro <ca********@gma il.com> wrote:
...
Yes, that's a good point, and it's one of the reasons I tend to prefer
the generator now. But anyway, it's just me, or does the 'chained
yield' look ugly to someone else? It may be just a question of getting
used to it, but nevertheless it's bugging me...


I'm not sure why it should look ugly to you. What alternatives would
you consider non-ugly for the common (in any generator) idiom:
for x in y: yield x
?

Perhaps some syntax hack such as a new statement keyword 'yieldall'
where the above idiom could be expressed as
yieldall y
? Or some other syntax hack such as 'yield<<y', or 'yield from y',
ditto? Personally, it would seem to me that such special syntax would
be just one more bit of Python to learn, without substantial benefits,
but that's because I see nothing ugly in today's idiom -- it does just
what it says, plainly and unpretentiously ...
Alex
Jul 18 '05 #4
On Mon, 18 Oct 2004 16:27:43 +0200, Alex Martelli <al*****@yahoo. com> wrote:
Carlos Ribeiro <ca********@gma il.com> wrote:
...
Yes, that's a good point, and it's one of the reasons I tend to prefer
the generator now. But anyway, it's just me, or does the 'chained
yield' look ugly to someone else? It may be just a question of getting
used to it, but nevertheless it's bugging me...


I'm not sure why it should look ugly to you. What alternatives would
you consider non-ugly for the common (in any generator) idiom:
for x in y: yield x
?

Perhaps some syntax hack such as a new statement keyword 'yieldall'
where the above idiom could be expressed as
yieldall y
? Or some other syntax hack such as 'yield<<y', or 'yield from y',
ditto? Personally, it would seem to me that such special syntax would
be just one more bit of Python to learn, without substantial benefits,
but that's because I see nothing ugly in today's idiom -- it does just
what it says, plainly and unpretentiously ...


Generally speaking, new keywords hardly solve any problem; in fact,
they create new problems of their own :-) In this case, my main gripe
is that the code doesn't read as naturally as the simple recursive
version, because of the double for loop. Its also strange because I
often have to stop and think, "what am I yielding now". For deeply
nested recursive cases there is also the feeling that the yield chain
may prove to be a performance dog, but that's should not be the main
point here anyway.

I have a strange idea in the back of my mind that tells me that a
possible solution would be to have any of the nested yields to
immediately return the result to the original caller. In this case, I
would write my code this way:

def walk(self):
"""generato r-based recursive tree traversal"""
yield child
for child in childs:
transfer child.walk()

It's quite weird -- a generator plus a direct flow-of-execution
transfer. It's not a goto, its not a co-routine... It requires a new
keyword ('transfer', in this case), which _is_ a real problem --
something like this can't be lightly proposed. In this case, it's just
a thought experiment, at this point; nothing serious, and far from a
proposal.

--
Carlos Ribeiro
Consultoria em Projetos
blog: http://rascunhosrotos.blogspot.com
blog: http://pythonnotes.blogspot.com
mail: ca********@gmai l.com
mail: ca********@yaho o.com
Jul 18 '05 #5
Carlos Ribeiro wrote:
On Mon, 18 Oct 2004 16:27:43 +0200, Alex Martelli <al*****@yahoo. com> wrote:
Carlos Ribeiro <ca********@gma il.com> wrote:
...
Yes, that's a good point, and it's one of the reasons I tend to prefer
the generator now. But anyway, it's just me, or does the 'chained
yield' look ugly to someone else? It may be just a question of getting
used to it, but nevertheless it's bugging me...


I'm not sure why it should look ugly to you. What alternatives would
you consider non-ugly for the common (in any generator) idiom:
for x in y: yield x
?

Perhaps some syntax hack such as a new statement keyword 'yieldall'
where the above idiom could be expressed as
yieldall y
? Or some other syntax hack such as 'yield<<y', or 'yield from y',
ditto? Personally, it would seem to me that such special syntax would
be just one more bit of Python to learn, without substantial benefits,
but that's because I see nothing ugly in today's idiom -- it does just
what it says, plainly and unpretentiously ...

Generally speaking, new keywords hardly solve any problem; in fact,
they create new problems of their own :-) In this case, my main gripe
is that the code doesn't read as naturally as the simple recursive
version, because of the double for loop. Its also strange because I
often have to stop and think, "what am I yielding now". For deeply
nested recursive cases there is also the feeling that the yield chain
may prove to be a performance dog, but that's should not be the main
point here anyway.

I have a strange idea in the back of my mind that tells me that a
possible solution would be to have any of the nested yields to
immediately return the result to the original caller. In this case, I
would write my code this way:

def walk(self):
"""generato r-based recursive tree traversal"""
yield child
for child in childs:
transfer child.walk()

It's quite weird -- a generator plus a direct flow-of-execution
transfer. It's not a goto, its not a co-routine... It requires a new
keyword ('transfer', in this case), which _is_ a real problem --
something like this can't be lightly proposed. In this case, it's just
a thought experiment, at this point; nothing serious, and far from a
proposal.

I can see why this might seem attractive, but in point of fact it would
do little more than the elimination of tail recursion, and would have
similar disadvantages - it wouldn't be possible to get useful tracebacks
in the event that problems occurred.

If a data structure is recursive then a recursive generator or a
recursive function is often the bext way to handle it, and yielding a
result to another yield statement (at however many levels) surely isn't
problematical enough to remove a desirable regularity from the language
and its implementations .

regards
Steve
--
http://www.holdenweb.com
http://pydish.holdenweb.com
Holden Web LLC +1 800 494 3119
Jul 18 '05 #6
Carlos Ribeiro wrote:
On Mon, 18 Oct 2004 16:27:43 +0200, Alex Martelli <al*****@yahoo. com> wrote:
Carlos Ribeiro <ca********@gma il.com> wrote:
...
Yes, that's a good point, and it's one of the reasons I tend to prefer
the generator now. But anyway, it's just me, or does the 'chained
yield' look ugly to someone else? It may be just a question of getting
used to it, but nevertheless it's bugging me...


I'm not sure why it should look ugly to you. What alternatives would
you consider non-ugly for the common (in any generator) idiom:
for x in y: yield x
?

Perhaps some syntax hack such as a new statement keyword 'yieldall'
where the above idiom could be expressed as
yieldall y
? Or some other syntax hack such as 'yield<<y', or 'yield from y',
ditto? Personally, it would seem to me that such special syntax would
be just one more bit of Python to learn, without substantial benefits,
but that's because I see nothing ugly in today's idiom -- it does just
what it says, plainly and unpretentiously ...

Generally speaking, new keywords hardly solve any problem; in fact,
they create new problems of their own :-) In this case, my main gripe
is that the code doesn't read as naturally as the simple recursive
version, because of the double for loop. Its also strange because I
often have to stop and think, "what am I yielding now". For deeply
nested recursive cases there is also the feeling that the yield chain
may prove to be a performance dog, but that's should not be the main
point here anyway.

I have a strange idea in the back of my mind that tells me that a
possible solution would be to have any of the nested yields to
immediately return the result to the original caller. In this case, I
would write my code this way:

def walk(self):
"""generato r-based recursive tree traversal"""
yield child
for child in childs:
transfer child.walk()

It's quite weird -- a generator plus a direct flow-of-execution
transfer. It's not a goto, its not a co-routine... It requires a new
keyword ('transfer', in this case), which _is_ a real problem --
something like this can't be lightly proposed. In this case, it's just
a thought experiment, at this point; nothing serious, and far from a
proposal.

I can see why this might seem attractive, but in point of fact it would
do little more than the elimination of tail recursion, and would have
similar disadvantages - it wouldn't be possible to get useful tracebacks
in the event that problems occurred.

If a data structure is recursive then a recursive generator or a
recursive function is often the bext way to handle it, and yielding a
result to another yield statement (at however many levels) surely isn't
problematical enough to remove a desirable regularity from the language
and its implementations .

regards
Steve
--
http://www.holdenweb.com
http://pydish.holdenweb.com
Holden Web LLC +1 800 494 3119

Jul 18 '05 #7
Carlos Ribeiro schrieb:
def walk(self):
"""generato r-based recursive tree traversal"""
yield child
for child in childs:
transfer child.walk()

It's quite weird -- a generator plus a direct flow-of-execution
transfer. It's not a goto, its not a co-routine... It requires a new
keyword ('transfer', in this case), which _is_ a real problem --
something like this can't be lightly proposed. In this case, it's just
a thought experiment, at this point; nothing serious, and far from a
proposal.

I know what it feels like. I had to implement the same thing for a
recursive parser once - looks somewhat inefficient to iterate over a
iterator only for yielding the iterator's results...

Maybe you know the itertools module?

http://www.python.org/dev/doc/devel/...functions.html

It has some nice functions that can make this sort of code more readable
(and maybe even more efficient). You may find itertoold.chain especially
useful.

Stefan
Jul 18 '05 #8
On Mon, 18 Oct 2004 17:42:15 +0200, Stefan Behnel
<be*******@dvs1 .informatik.tu-darmstadt.de> wrote:
Carlos Ribeiro schrieb:
def walk(self):
"""generato r-based recursive tree traversal"""
yield child
for child in childs:
transfer child.walk()

It's quite weird -- a generator plus a direct flow-of-execution
transfer. It's not a goto, its not a co-routine... It requires a new
keyword ('transfer', in this case), which _is_ a real problem --
something like this can't be lightly proposed. In this case, it's just
a thought experiment, at this point; nothing serious, and far from a
proposal.

I know what it feels like. I had to implement the same thing for a
recursive parser once - looks somewhat inefficient to iterate over a
iterator only for yielding the iterator's results...

Maybe you know the itertools module?

http://www.python.org/dev/doc/devel/...functions.html

It has some nice functions that can make this sort of code more readable
(and maybe even more efficient). You may find itertoold.chain especially
useful.


Thanks -- that's a really good reference. I think I should read more
of the documentation instead of banging up my own home made solution
:-) Anyway, it does not solve the recursion problem per se, but it
gave me some ideas on own can I rewrite the code. I'll try it later...
--
Carlos Ribeiro
Consultoria em Projetos
blog: http://rascunhosrotos.blogspot.com
blog: http://pythonnotes.blogspot.com
mail: ca********@gmai l.com
mail: ca********@yaho o.com
Jul 18 '05 #9

On 2004 Oct 18, at 16:57, Carlos Ribeiro wrote:
...
def walk(self):
"""generato r-based recursive tree traversal"""
yield child
for child in childs:
Btw, what are this 'child' and 'childs', _globals_? I assume you must
mean something like self and self.children, but as that may become
important in further discussion it would be nice to be more precise in
the example.
transfer child.walk()

It's quite weird -- a generator plus a direct flow-of-execution
transfer. It's not a goto, its not a co-routine... It requires a new
keyword ('transfer', in this case), which _is_ a real problem --


How does the semantics of this differ from those of
for x in child.walk(): yield x
? I don't know what a "direct flow of execution transfer" _is_, since
when the 'transfer' is finished execution had better come back here.
So, I fail to appreciate the difference, if any, between:
for x in y: yield x
and
transfer y
which is just the same thing I had mentioned (under guise of 'yieldall'
in lieu of 'transfer', but that's mere sugar) in the post you're
replying to. And I think that a combination such as
yield from y
besides not requiring a new keyword might be even more readable. I'm
using y as just a placeholder here, it would be "yield from
child.walk()" in your case.

If the issue is strictly one of whether it's worth somehow making
for x in y: yield x
terser (by a new kw, combination of kw, and/or punctuation) I guess we
can discuss that (I just don't see the gain to offset the price of
introducing new syntax and one more language thing to learn for
Pythonistas and newcomers to Python). If you mean something different
for your 'transfer' then maybe you could clarify _what_...
Alex

Jul 18 '05 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

176
8119
by: Thomas Reichelt | last post by:
Moin, short question: is there any language combining the syntax, flexibility and great programming experience of Python with static typing? Is there a project to add static typing to Python? Thank you, -- greetz tom
8
2305
by: Paul Chiusano | last post by:
I've been playing around with generators and have run into a difficulty. Suppose I've defined a Node class like so: class Node: def __init__(self, data=None, left=None, right=None): self.children = self.children.append(left) self.children.append(right) self.data = data
0
1331
by: Carlos Ribeiro | last post by:
Hi, A friend of mine passed me some links about a great concept (not new in fact, only new to me): -- http://www.jpaulmorrison.com/fbp/ -- http://c2.com/cgi/wiki?FlowBasedProgramming I found many of the explanations and examples strangely familiar. The C2 Wiki contains a good discussion that draws parallels between FBP
7
2655
by: aurora | last post by:
I love generator and I use it a lot. Lately I've been writing some recursive generator to traverse tree structures. After taking closer look I have some concern on its performance. Let's take the inorder traversal from http://www.python.org/peps/pep-0255.html as an example. def inorder(t): if t: for x in inorder(t.left):
6
4530
by: Talin | last post by:
I've been using generators to implement backtracking search for a while now. Unfortunately, my code is large and complex enough (doing unification on math expressions) that its hard to post a simple example. So I decided to look for a simpler problem that could be used to demonstrate the technique that I am talking about. I noticed that PEP 255 (Simple Generators) refers to an implementation of the "8 Queens" problem in the lib/test...
7
6127
by: Aloo | last post by:
Dear friends, If we declare a recursive function as 'inline' then does it actually convert to an iterative form during compilation ( the executable code is iterative)? Is it possible ? Please reply.
4
2360
by: Michael | last post by:
Hi, I'm having difficulty finding any previous discussion on this -- I keep finding people either having problems calling os.exec(lepev), or with using python's exec statement. Neither of which I mean here. Just for a moment, let's just take one definition for one of the
86
2714
by: PTY | last post by:
Which is better? lst = while lst: lst.pop() OR while len(lst) 0:
18
4718
by: Just Another Victim of the Ambient Morality | last post by:
Is pyparsing really a recursive descent parser? I ask this because there are grammars it can't parse that my recursive descent parser would parse, should I have written one. For instance: from pyparsing import * grammar = OneOrMore(Word(alphas)) + Literal('end') grammar.parseString('First Second Third end')
0
8635
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
9119
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
0
8994
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
1
8852
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
8830
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
7664
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
0
4582
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
3008
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
3
1977
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.