Idiomatic Python: Propagación de los rendimientos o las secuencias de aplanamiento?

Question

Estoy escribiendo un función de recorrido de árbol primero en profundidad anchura, y lo que yo quiero hacer es esto:

def traverse(node): 
    yield node 
    for n in node.children: 
     yield_all traverse(n) # << if Python had a yield_all statement 

La idea es terminar con una secuencia (plana) de nodos en el árbol .

Enfoque # 1: (rendimientos que se propagan)

def traverse(node): 
    yield node 
    for n in node.children: 
     for m in traverse(n): 
      yield m 

Enfoque # 2: (secuencias de aplanamiento)

def traverse(node): 
    return itertools.chain([node],*(traverse(n) for n in node.children)) 

El primer enfoque parece más limpio, pero me siento raro explícitamente yield ing cada nodo en el subárbol en cada nivel.

El segundo enfoque es terso y un poco sucio, pero coincide con lo que iba a escribir en Haskell:

traverse node = node : concatMap traverse (children node) 

Así que mi pregunta es: ¿Qué es mejor? ¿O me estoy perdiendo una mejor tercera opción?

Answer 1

[ACTUALIZACIÓN] Ver PEP-380, este rendimiento toda la sintaxis comenzando en Python 3.3 como yield from:

def traverse(node): 
    yield node 
    for n in node.children: 
     yield from traverse(n) 

Answer 2

Me quedo con la primera. Obtendrá más de propagar los rendimientos después de un par de veces. :-)

Answer 3

Esta es una pregunta de opiniones, así que todas las respuestas serán solo evaluaciones de valor. Por lo que puedo pensar, no hay una tercera vía elegante.

Mi opinión es que la primera forma gana indiscutiblemente. Es más claro y fácil de leer: Python no es Haskell, a pesar de que puede hacer algunas cosas funcionales, y a menudo el enfoque funcional simplemente no se ve tan limpio.

Answer 4

El desplazamiento con la posición del nodo:

def iter_tree(t, i=0, j=0): 
    yield (i, j), t 
    for j, n in enumerate(t.children): 
     yield from iter_tree(n, i + 1, j) 

for (i, j), n in iter_tree(t): 
    print(i*' ', (i, j), n)