Flatten (an irregular) list of lists in Python

Question

Yes, I know this subject has been covered before (here, here, here, here), but AFAIK, all solutions save one choke on a list like this:

L = [[[1, 2, 3], [4, 5]], 6]

where the desired output is

[1, 2, 3, 4, 5, 6]

or perhaps even better, an iterator. The only solution I saw that works for an arbitrary nesting is from @Alabaster Codify here:

def flatten(x):
    result = []
    for el in x:
        if hasattr(el, "__iter__") and not isinstance(el, basestring):
            result.extend(flatten(el))
        else:
            result.append(el)
    return result

flatten(L)

So to my question: is this the best model? Did I overlook something? Any problems?

Answer 1

I don't if it is the best -- I suppose that is how you define "best" but that certainly works and the logic is easy to follow.

I'd simply use that if I needed such a function.

Answer 2

My solution:

def flatten(x):
    if hasattr(x, '__iter__'):
        return [a for i in x for a in flatten(i)]
    else:
        return [x]

A little more concise, but pretty much the same. My only complaint is that there's not built-in function iterable.

Answer 3

Using generator functions can make your example a little easier to read and probably boost the performance.

def flatten(l):
    for el in l:
        if isinstance(el, collections.Iterable) and not isinstance(el, basestring):
            for sub in flatten(el):
                yield sub
        else:
            yield el

I used the Iterable ABC added in 2.6.

Answer 4

This version of flatten avoids python's recursion limit (and thus works with arbitrarily-deep nested lists):

def flatten(l, ltypes=collections.Sequence):
    # http://rightfootin.blogspot.com/2006/09/more-on-python-flatten.html
    # http://stackoverflow.com/questions/716477/join-list-of-lists-in-python/716479#716479
    # flatten([[1,2,3],[4,5,6],[7,8,9]]) --> [1, 2, 3, 4, 5, 6, 7, 8, 9]
    ltype = type(l)
    l = list(l)
    i = 0
    while i < len(l):
        while isinstance(l[i], ltypes):
            if not l[i]:
                l.pop(i)
                i -= 1
                break
            else:
                l[i:i + 1] = l[i]
        i += 1
    return ltype(l)

Here is a generator versions of the same thing:

def flatten_gen(l, ltypes=collections.Sequence):       
    ltype = type(l)
    l = list(l)
    i = 0
    while i < len(l):
        while isinstance(l[i], ltypes):
            if not l[i]:
                l.pop(i)
                i -= 1
                break
            else:
                l[i:i + 1] = l[i]
        else:
            yield l[i]
        i += 1

Answer 5

Generator version of @unutbu's non-recursive solution, as requested by @Andrew in a comment:

def genflat(l, ltypes=collections.Sequence):
    l = list(l)
    i = 0
    while i < len(l):
        while isinstance(l[i], ltypes):
            if not l[i]:
                l.pop(i)
                i -= 1
                break
            else:
                l[i:i + 1] = l[i]
        yield l[i]
        i += 1

Slightly simplified version of this generator:

def genflat(l, ltypes=collections.Sequence):
    l = list(l)
    while l:
        while l and isinstance(l[0], ltypes):
            l[0:1] = l[0]
        if l: yield l.pop(0)

Answer 6

If you like recursion, this might be a solution of interest to you:

def f(E):
    if E==[]: 
        return []
    elif type(E) != list: 
        return [E]
    else:
        a = f(E[0])
        b = f(E[1:])
        a.extend(b)
        return a

I actually adapted this from some practice Scheme code that I had written a while back.

Enjoy!