python - recursiveness - Llamar recursivamente a un método de objeto que devuelve un iterador de sí mismo

recursive programming python

Question

Actualmente estoy escribiendo un proyecto que requiere un código de terceros que utiliza un método que devuelve un iterador de sí mismo, un ejemplo de cómo se vería en mi código:

def generate():
    for x in obj.children():
        for y in x.children():
            for z in y.children():
                yield z.thing

Actualmente, esto simplemente desordena mi código y se vuelve difícil de leer después de 3 niveles. Lo ideal sería que hiciera algo como esto:

x = recursive(obj, method="children", repeat=3).thing

¿Hay una forma integrada de hacerlo en Python?

Answer 1

A partir de python3.3, puede usar el yield from sintaxis para generar una expresión de generador completa.

Entonces, puedes modificar tu función un poco, para tomar un par de parámetros:

def generate(obj, n):
    if n == 1:
        for x in obj.children():
            yield x.thing
    else:
        for x in obj.children():
            yield from generate(x, n - 1)

El yield from expresión producirá la expresión generadora completa de la llamada recursiva.

Llame a su función de esta manera:

x = generate(obj, 3)

Tenga en cuenta que esto le devuelve un generador de x.things .

Según su requisito particular, aquí hay una versión más genérica que usa getattr que funciona con atributos arbitrarios.

def generate(obj, iterable_attr, attr_to_yield, n):
    if n == 1:
        for x in getattr(obj, iterable_attr):
            yield getattr(x, attr_to_yield)
    else:
        for x in getattr(obj, iterable_attr):
            yield from generate(x, iterable_attr, attr_to_yield, n - 1)

Y ahora, llame a su función como:

x = generate(obj, ''children'', ''thing'', 3)

Answer 2

El yield from ejemplo anterior es bueno, pero dudo seriamente que se necesite el parámetro de nivel / profundidad. Una solución más simple / más genérica que funciona para cualquier árbol:

class Node(object):
  def __init__(self, thing, children=None):
    self.thing = thing
    self._children = children
  def children(self):
    return self._children if self._children else []

def generate(node):
  if node.thing:
    yield node.thing
  for child in node.children():
    yield from generate(child)

node = Node(''mr.'', [Node(''derek'', [Node(''curtis'')]), Node(''anderson'')])
print(list(generate(node)))

Devoluciones:

$ python3 test.py
[''mr.'', ''derek'', ''curtis'', ''anderson'']

Tenga en cuenta que esto devolverá el nodo actual antes que cualquiera de sus hijos. (Es decir, se expresa en el camino de la caminata). Si prefieres que se exprese en el camino de regreso, intercambia las declaraciones de if y for . (DFS vs BFS) Pero probablemente no importe en su caso (donde sospecho que un nodo tiene una thing o hijos, nunca ambos).

Answer 3

Si usa Python 2.7, necesita mantener su propia pila de iterables y realizar el bucle:

from operator import methodcaller

def recursive(obj, iterater, yielder, depth):
    iterate = methodcaller(iterater)
    xs = [iterate(obj)]
    while xs:
        try:
            x = xs[-1].next()
            if len(xs) != depth:
                xs.append(iterate(x))
            else:
                yield getattr(x, yielder)
        except StopIteration:
            xs.pop()

Este es un caso especializado de un ichain recursivo más general de la función iterable:

def recursive_ichain(iterable_tree):
    xs = [iter(iterable_tree)]
    while [xs]:
        try:
            x = xs[-1].next()
            if isinstance(x, collections.Iterable):
                xs.append(iter(x))
            else:
                yield x
        except StopIteration:
            xs.pop()

Y algunos objetos de prueba:

class Thing(object):
    def __init__(self, thing):
        self.thing = thing

class Parent(object):
    def __init__(self, *kids):
        self.kids = kids

    def children(self):
        return iter(self.kids)

test_obj = Parent(
    Parent(
        Parent(Thing(''one''), Thing(''two''), Thing(''three'')),
        Parent(Thing(''four'')),
        Parent(Thing(''five''), Thing(''six'')),
    ),
    Parent(
        Parent(Thing(''seven''), Thing(''eight'')),
        Parent(),
        Parent(Thing(''nine''), Thing(''ten'')),
    )
)

Y probarlo:

>>>for t in recursive(test_obj, ''children'', ''thing'', 3):
>>>    print t
one
two
three
four
five
six
seven
eight
nine
ten

Personalmente, me inclinaría a cambiar el yield getattr(x, yielder) para yield x para acceder a los objetos de hoja en sí y acceder explícitamente a la cosa. es decir

for leaf in recursive(test_obj, ''children'', 3):
    print leaf.thing