Python中的惯用方式：传播生成器或展开序列？

Question

我正在编写一个深度优先遍历函数，想要实现以下功能：

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

这里需要将树中的节点转化为一个（扁平化的）序列。 方法一：（传播yield）

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

方法二：（序列展平）

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

第一种方法看起来更简洁，但是在每个层级显式地yield每个子树中的节点感觉有些奇怪。

第二种方法简洁而略显凌乱，但它与我在Haskell中编写的方式相匹配：

traverse node = node : concatMap traverse (children node)

所以我的问题是：哪个更好？或者我错过了第三个最佳选项吗？

- perimosocordiae

---

列表推导式可以使代码更简洁。 - Rafe Kettler

Rafe：写一个答案并展示给我！ :-) - perimosocordiae

我想看到一个针对这个的列表推导式...最后需要把它展平，对吧？就我而言，“chain”解决方案非常棒。 - user395760

然而，yield方法比chain方法快3倍左右，并且相当易读，所以我会选择它。 - Justin Peel

这不是树的深度优先遍历吗？你不是要求广度优先遍历吗？ - Hugh Bothwell

Answer 1

[更新] 请参考PEP-380，自Python 3.3起，yield all语法可用作yield from：

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

- tokland

---

啊，有时候我觉得我希望 Python 具备的一切都被埋在了某个 PEP 中。我应该开始收集 pep 模块，或者也许只是学会接受 Python 并不是 真正 的函数式语言。 - perimosocordiae

@perimosocordiae：了解GvR对FP的观点，我不会对此抱有太高期望。但毫无疑问，没有Kuchling和Hettinger（以及其他人）在FP方面的工作，Python将是一门更加令人沮丧的语言。 - tokland

Answer 2

我会选择第一个。经过几次后，您将克服繁殖收益的问题。 :-)

- Lennart Regebro

Answer 3

这是一个观点问题，因此所有答案都将是价值判断。就我所知，没有优雅的第三种方法。

我的意见是第一种方法轻松获胜。它更清晰、更易于阅读——Python虽然可以做一些函数式的东西，但它并不是Haskell，而且往往函数式方法看起来并不那么整洁。

- Katriel

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)

- APEFind