Idiomatic Python: Propagating yields or flattening sequences?

Question

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

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?

Answer 1

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

Answer 2

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

Answer 3

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.