views:

173

answers:

4

I've been trying to think of a way to traverse a hierarchical structure, like a linked list, using a list expression, but haven't come up with anything that seems to work.

Basically, I want to convert this code:

p = self.parent
names = []
while p:
  names.append(p.name)
  p = p.parent
print ".".join(names)

into a one-liner like:

print ".".join( [o.name for o in <???>] )

I'm not sure how to do the traversal in the ??? part, though, in a generic way (if its even possible). I have several structures with similar .parent type attributes, and don't want to have write a yielding function for each.

Edit:

I can't use the __iter__ methods of the object itself because its already used for iterating over the values contained within the object itself. Most other answers, except for liori's, hardcode the attribute name, which is what I want to avoid.

Here's my adaptation based upon liori's answer:

import operator
def walk(attr, start):
  if callable(attr):
    getter = attr
  else:
    getter = operator.attrgetter(attr)

  o = getter(start)
  while o:
    yield o
    o = getter(o)
+1  A: 

List comprehension works with objects that are iterators (have the next() method). You need to define an iterator for your structure in order to be able to iterate it this way.

kgiannakakis
+6  A: 

The closest thing I can think of is to create a parent generator:

# Generate a node's parents, heading towards ancestors
def gen_parents(node):
   node = node.parent
   while node:
      yield node
      node = node.parent

# Now you can do this
parents = [x.name for x in gen_parents(node)]
print '.'.join(parents)
Triptych
+1  A: 

Your LinkedList needs to be iterable for it to work properly.

Here's a good resource on it. (PDF warning) It is very in depth on both iterators and generators.

Once you do that, you'll be able to just do this:

print ".".join( [o.name for o in self] )
Evan Fosmark
+2  A: 

If you want your solution to be general, use a general techique. This is a fixed-point like generator:

def fixedpoint(f, start, stop):
    while start != stop:
        yield start
        start = f(start)

It will return a generator yielding start, f(start), f(f(start)), f(f(f(start))), ..., as long as neither of these values are equal to stop.

Usage:

print ".".join(x.name for x in fixedpoint(lambda p:p.parent, self, None))

My personal helpers library has similar fixedpoint-like function for years... it is pretty useful for quick hacks.

liori
yes! this is the sort of thing i was looking for. I updated my answer with my adaptation.
Richard Levasseur