Idiomatic Python: Распространение или выравнивание последовательностей?

Question

Я пишу ширину глубину первого дерева функцию обхода, и то, что я хочу сделать это:

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

Идея заключается в том, чтобы в конечном итоге с (плоской) последовательности узлов в дереве ,

Подход № 1: (распространяющиеся выходы)

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

подход # 2: (уплощение последовательности)

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

Первый подход кажется более чистым, но я чувствую себя странно, явно yield ИНГ каждый узел в поддереве на каждом уровне.

Второй подход немногословен и немного грязный, но это соответствует тому, что я хотел бы написать в Haskell:

traverse node = node : concatMap traverse (children node) 

Так что мой вопрос: Что лучше? Или я пропустил лучший третий вариант?

Answer 1

[UPDATE] См PEP-380, этот выход все синтаксис доступен начиная с Python 3.3 в yield from:

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

Answer 2

Я бы с первым. Через пару раз вы получите распространение урожайности. :-)

Answer 3

Это вопрос мнения, поэтому все ответы будут только оценочными суждениями. Насколько я могу судить, нет никакого элегантного третьего пути.

Мое мнение таково, что первый способ побеждает руки. Это проще и понятнее - Python - это не Haskell, хотя он может делать некоторые функциональные вещи, и часто функциональный подход просто не выглядит таким аккуратным.

Answer 4

обход с положением узла:

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)