开发者

Idiomatic Python: Propagating yields or flattening sequences?

开发者 https://www.devze.com 2023-01-30 09:03 出处:网络
I\'m writing a breadth depth-first tree traversal function, and what I want to do is this: def traverse(node):

I'm writing a breadth depth-first tree traversal function, and what I want to do is this:

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

The idea is to end up with a (flat) sequence of nodes in the tree.

Approach #1: (propagating yields)

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

Approach #2: (flattening seque开发者_Python百科nces)

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

The first approach seems more clean, but I feel weird explicitly yielding each node in the subtree at each level.

The second approach is terse and slightly dirty, but it matches what I would write in Haskell:

traverse node = node : concatMap traverse (children node)

So my question is: Which is better? Or am I missing a best 3rd option?


[UPDATE] See PEP-380, this yield all syntax is available starting from Python 3.3 as yield from:

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


I'd go with first. You'll get over propagating yields after a couple of times. :-)


This is an opinions question, so all the answers will just be value judgments. As far as I can think there's no elegant third way, though.

My opinion is that the first way wins hands down. It's clearer and easier to read -- Python isn't Haskell, even though it can do some functional stuff, and often the functional approach just doesn't look as neat.


Traversing with node position:

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)
0

精彩评论

暂无评论...
验证码 换一张
取 消