Walking deeply nested lists

donn 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 
tree.]

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

Aim 1
---
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.)

Aim 2
---
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.
def flatten(input):
  output = []
  stack = []
  stack.extend(reversed(input))
  while stack:
   top = stack.pop()
   if isinstance(top, list):
    stack.extend(reversed(top))
   else:
    output.append(top)
  return output

## My walker
def test_walk(e): #lxml Element comes in
  obj = ebag_get(e)['obj'] #get a tag object
  l=obj.flatwalk()
  ll= flatten(l)
  #No current solution to get 'parent' in this iterator
  #ie. for parent, child in ...
  for tag in ll:
   print tag

Here's one of my Tag objects:

class Brancher(object):
   def __init__(self, elem):
     self.elem = elem
     self.children = []

   def flatwalk(self):
     l=[self]
     for child in self.children:
       l.append( child.flatwalk() ) #recur(ish)ion here
     return l

class G( Brancher ): #Object for <g> tags.
   pass

\d



More information about the Python-list mailing list