Walking deeply nested lists
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!
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
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