Puzzle: Recursive generator without loops/imports

Question

It is generators today. I saw a question today that wanted to find a way to flatten a list recursively without using loops and imports. tobias_k answered it with a following code:

def flatten(test_list):
    if isinstance(test_list, list):
        if len(test_list) == 0:
            return []
        first, rest = test_list[0], test_list[1:]
        return flatten(first) + flatten(rest)
    else:
        return [test_list]

Is there a way of creating a generator (with keeping the rules: no imports,loops)?

NOTE: it is purely educational. i know it is not the best idea, but coulnd't figure out how to do it.

score 4 · Answer 1 · answered Sep 18 '12 at 14:16

4

In Python 3.3 (development version), you can use the yield from construct to avoid explicit loops:

def flatten(x):
    if isinstance(x, list):
        if x:
            first, rest = x[0], x[1:]
            yield from flatten(first)
            yield from flatten(rest)
    else:
        yield x

In current versions, I can't think of a solution that does not use itertools.chain.

answered Sep 18 '12 at 14:16

Fred Foo

355,277
75
744
836

Where `yield from` is implemented as a C loop instead. :-P – Martijn Pieters Sep 18 '12 at 14:18
That doesn't avoid loops, it's just syntactical sugar to make the interpreter do the loop for you, is it not? – Silas Ray Sep 18 '12 at 14:18
@sr2222: of course. So is performing `+` on two lists. Changed "loops" to "explicit loops". – Fred Foo Sep 18 '12 at 14:19
Fair enough. But doesn't that just make the original referenced answer incorrect? – Silas Ray Sep 18 '12 at 14:22
3

As far as I'm concerned, how list concatenation and `yield from` are implemented is completely irrelevant. From a python perspective, there are no loops here ... – mgilson Sep 18 '12 at 14:24
@ larsmans -- maybe someone can figure smth out in 2.x. meanwhile +1 for the nice answer. thanks. – root Sep 18 '12 at 14:28
2

@sr2222: if you interpret the question literally, yes. I was assuming the requirement is "no list comprehensions, no imports, and no loops *in the Python code*". – Fred Foo Sep 18 '12 at 14:29
But then you could just as easily do `yield from flatten(test_list)`. With a language that can potentially hide so much functionality in syntactical shorthand, requirements like those of the OP become almost completely arbitrary if not interpreted literally. If the OP is satisfied with the answer, that's ultimately the point here, but the answer still doesn't explain how, logically, to do this sort of thing without loops. – Silas Ray Sep 18 '12 at 14:36
@sr2222: no, you can't just `yield from flatten(test_list)`, because then you'd still have to implement the original `flatten` somehow. My version is self-contained, using only builtins. – Fred Foo Sep 18 '12 at 14:43
@sr2222: back in the day, compilers did loop unrolling to optimize for speed. If your logic demands no loops all the way down to the bare metal, you'd code a dot product in Python as a list of thousands or millions of multiply and accumulate statements. But I believe calling numpy's dot(a,b) satisfies both the spirit and letter of the requirement, because a compiler could, in theory, unroll the loop, as it could for any sequence of Python instructions. – Dave Sep 18 '12 at 15:00
@Dave True, but generally, the point of these sort of mental exercises is to adapt logical constructs to think about how to perform tasks in a fundamentally different way. Using an implicit looping construct in place of an explicit one does not satisfy that goal. – Silas Ray Sep 18 '12 at 15:09

ecatmur · Accepted Answer · 2012-09-18T16:00:45.813

A generator function is a function that contains at least one yield statement and no return statements that take an expression. When a generator function is invoked it returns a generator iterator, which when iterated (e.g. by a for loop, or explicitly with next) runs through the body of the function, freezing its state and returning control to the caller on each yield statement (and in Python 3.3, yield from statements).

Flow control inside a Python function is always forwards; without hacks like setting the current frames f_lineno (as famously done by the (April Fool's) goto statement), the only way for control to reach an earlier point is to use a loop (for or while). So without a loop or yield from, the maximum number of times a generator iterator can be invoked is bounded by the number of yield statements within the generator function.

Note that it's easy to write a flatten that returns an iterator; taking the original solution and writing return iter(flatten(first) + flatten(rest)) would do. But that wouldn't be a generator iterator, and the function wouldn't be a generator function.

Here's an implementation that abuses f_lineno to give loopless iteration. Unfortunately it has to use import sys:

def current_frame():
    i = None
    def gen():
        yield i.gi_frame.f_back
    i = gen()
    return next(i).f_back

class Loop(object):
    jump = False
    def __call__(self, frame, event, arg):
        if self.jump:
            frame.f_lineno = self.lineno
            self.jump = False
        return None if event == 'call' else self
    def __enter__(self):
        import sys
        sys.settrace(self)
        current_frame().f_back.f_trace = self
        self.lineno = current_frame().f_back.f_lineno
        return self
    def __exit__(self, exc_type, exc_value, traceback):
        if exc_type is None:
            self.jump = True
        else:
            import sys
            sys.settrace(None)
            current_frame().f_back.f_trace = None
            return exc_type is StopIteration

def flatten(x):
    if isinstance(x, list):
        if x:
            first, rest = flatten(x[0]), flatten(x[1:])
            with Loop():
                yield next(first)
            with Loop():
                yield next(rest)
            pass
    else:
        yield x

@ ecatmur -- this is nice. thanks for effort. i will try to absorb this. — root, Sep 18 '12 at 16:03

Puzzle: Recursive generator without loops/imports

2 Answers2