List Flatten

[Raymond Hettinger]

"bearophile" <bearophileHUGS at lycos.com> wrote :
> This program works for very deep lists too, without giving Stack
> overflow like the recursive version (and it's faster than the
> recursive version).

Here is a non-recursive version using generators.  It runs in O(n) time and is
memory friendly (consuming space proportional to the depth of the input).  It
has one additional feature, strings are kept whole instead of iterating them
into characters.


>>> def f(n):
    iterstack = [iter(n)]
    while iterstack:
        for elem in iterstack[-1]:
            try:
                it = iter(elem)
            except TypeError:
                pass
            else:
                if not isinstance(elem, basestring):
                    iterstack.append(it)
                    break
            yield elem
        else:
            iterstack.pop()  # remove iterator only when it is exhausted

>>> n = [['ab', 2, [], [3, 5, (2,1), [4]]]]
>>> print list(f(n))
['ab', 2, 3, 5, 2, 1, 4]



Raymond Hettinger