Идиоматический Питон: Распространение урожаев или выравнивание последовательностей?

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 каждый узел в поддереве на каждом уровне.

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

traverse node = node : concatMap traverse (children node)

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

Answer 1

[ОБНОВЛЕНИЕ] См. 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)