Walking deeply nested lists

donn donn.ingle at gmail.com
Sat Aug 28 13:55:40 CEST 2010

On 28/08/2010 11:17, Carl Banks wrote:
> It's simple. Copy the object to flatten onto your stack. Pop one item
> off the stack. If the item you popped is a list, push each item of
> that list onto the stack. Otherwise yield the value. Loop until stack
> is empty.
Nice. The reversed thing was throwing me, but I think it's so that what 
comes first in a list will thus come first (on the end) of the stack.

> So I'm not suggesting that recursion be avoided (I've probably written
> a dozen recursive functions in the last week), I'm just saying
> sometimes it makes sense to use iteration even for problems recursion
> is tailor-made for.
Thanks for that. In parsing the XML (using lxml) I actually did my own 
stack thing with while loops, to build the entire Tag object 'tree' — 
just because I wanted to see how to do it sans recursion. I still get 
cold shakes when I scroll past that monster!

On the subject of recursion, and looking at my OP object model: the Tag 
objects that model the tags in an SVG file; how would I 'walk' the 
object tree without employing recursion?
I am stuck on the eventual need to call child.flatwalk() and bang! 
there's recursion.

I get the sense that it would be an external walk() function that does 
some stackery-trickery and reuturns/yields the tree/branch — all 
divorced from the actual objects. So, no flatwalk() methods needed at 
all. This kind of bothers me because it's nice to have objects 'know' 
what to do and addressing their siblings and children seems a vital part 
of that.

Look at the case of asking a Tag for its XML source:
Say g is a G() instance: print g.get_xml(), would have to do some string 
churning (specific to a g tag) and then start walking its children and 
ask them to do specific string stuff (in their contexts).
  This means I have short methods in each Tag instance that "know" how 
to represent themselves as XML and they can return that value.
If I divorce the thing, it becomes a large loop with a lot of 
switchy-ifs to engage various blocks of string-fu.

I hope that made sense. I can post my code if that would help.


More information about the Python-list mailing list