Walking deeply nested lists
donn.ingle at gmail.com
Sat Aug 28 05:21:09 CEST 2010
This is all about walking trees, recursion and generators. None of which
fit my brain at all!
From an XML tree (an SVG file) I build a bunch of Tag objects.
[I use lxml, but I am combining multiple svg files into a 'forest' of
trees, so I can't use the lxml walking methods because they all stop at
the 'end' of a branch where there is actually a 'link' over to another
Each Tag has a flatwalk() method. The return from that is a list which
can be deeply nested. As an example, something like this:
L=[1, [2, 3, [4, [5, 6], 7], 8], [9, 10] ]
(The numbers in the example would actually be Tag Instances.)
I'm trying to write a generator around such lists so that I can 'walk' them:
for parent, child in mystery_generator(L):
print level, item
Right now, I am running a 'flatten' function on the entire list (which I
don't savvy, I found it online) and then I iterate over that flattened
list. This doesn't feel right to me. (Code at end.)
The Objects that represent the svg tags use that flatwalk() method to
build the nested list, I'd far prefer flatwalk() to be directly useable
in something like this way:
for container, child in some_tag.flatwalk():
print container, child
The flatwalk() function is (and this is another puzzle see *) kind of
recursive. "For each of my children, tell that child to go flatwalk()".
(Code at end.)
I am not sure how to turn such a thing into a generator.
I keep wondering how os.walk() does its thing. My hierarchy of Tag
objects can be thought of as directories (tags:g, symbol, svg), files
(path, circle, etc.) and soft-links (use tags).
* If an Instance calls a method on *another* Instance of the *same*
class, is this still recursion? And how does this 'stack up'? I mean,
literally, on the stack. Does each instance get its own stack, or does
all the push, call, pop stuff happen in one main stack?
(I worry about recursion depth limits because svg trees can get quite deep.)
The walking code so far:
## Found code.
output = 
stack = 
top = stack.pop()
if isinstance(top, list):
## My walker
def test_walk(e): #lxml Element comes in
obj = ebag_get(e)['obj'] #get a tag object
#No current solution to get 'parent' in this iterator
#ie. for parent, child in ...
for tag in ll:
Here's one of my Tag objects:
def __init__(self, elem):
self.elem = elem
self.children = 
for child in self.children:
l.append( child.flatwalk() ) #recur(ish)ion here
class G( Brancher ): #Object for <g> tags.
More information about the Python-list