Categories
flatten list nested-lists optimization python

Flatten an irregular list of lists

516

Yes, I know this subject has been covered before (here, here, here, here), but as far as I know, all solutions, except for one, fail 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 found in this question:

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)

Is this the best model? Did I overlook something? Any problems?

6

  • 23

    The fact that there are this many answers and so much action on this question really suggests that this should be a built-in function somewhere, right? It’s especially too bad the compiler.ast was removed from Python 3.0

    Mar 18, 2014 at 13:22

  • 3

    I would say that what Python really needs is unbroken recursion rather than another builtin.

    – clay

    Apr 7, 2015 at 23:27

  • 3

    @Mittenchops: totally disagree, the fact that people working with obviously bad APIs/overly complicated data structures (just a note: lists intended to be homogeneous) doesn’t mean it’s a Python’s fault and we need a builtin for such task

    May 23, 2019 at 9:12


  • 4

    If you can afford adding a package to your project – I suppose the more_itertools.collapse solution will do it best. From this answer: stackoverflow.com/a/40938883/3844376

    – viddik13

    Mar 5, 2020 at 15:57


  • @viddik13: please consider making that an answer for this question, as well. It would absolutely get my upvote. (I agree with Mittenchops.) The fact that it’s not a built-in function is fine (re Azat Ibrakov), but there should be (and, apparently, is!) a library routine for doing this. (Because: not all irregularity is “bad”/”overly complicated”. Sometimes, it’s just… not regular, and that’s OK. IMHO. As long as what it is is well defined, and it can be, and still be irregular (“an arbitrarily nested list (of lists (of lists…)) of integers”, for example, is well defined).)

    – lindes

    Feb 7, 2021 at 19:06

447

Using generator functions can make your example easier to read and improve performance.

Python 2

Using the Iterable ABC added in 2.6:

from collections import Iterable

def flatten(xs):
    for x in xs:
        if isinstance(x, Iterable) and not isinstance(x, basestring):
            for item in flatten(x):
                yield item
        else:
            yield x

Python 3

In Python 3, basestring is no more, but the tuple (str, bytes) gives the same effect. Also, the yield from operator returns an item from a generator one at a time.

from collections.abc import Iterable

def flatten(xs):
    for x in xs:
        if isinstance(x, Iterable) and not isinstance(x, (str, bytes)):
            yield from flatten(x)
        else:
            yield x

12

  • 8

    Of all the suggestions on this page, this is the only one that flattened this list l = ([[chr(i),chr(i-32)] for i in xrange(ord('a'), ord('z')+1)] + range(0,9)) in a snap when i did this list(flatten(l)). All the others, would start working and take forever!

    – JWL

    Jun 7, 2012 at 15:04

  • 8

    This also flattens dictionaries. Maybe you want to use collections.Sequence instead of collections.Iteratable?

    – josch

    Jun 21, 2015 at 12:37

  • 3

    This doesn’t work with things that aren’t lists initially, e.g. for i in flatten(42): print (i). This could be fixed by moving the isinstance-test and the else-clause outside of the for el-loop. (Then you could throw anything at it, and it would make a flattened list out of it)

    – RolKau

    Aug 18, 2015 at 11:17

  • 6

    For Python 3.7, using collections.Iterable is deprecated. Use collections.abc.Iterable instead.

    – dawg

    Sep 30, 2018 at 15:53

  • 5

    Indeed, recursion is never needed. In this specific case using recursion is not the best solution as it will crash on deeply nested lists (depth > 1000). But if you don’t aim at having something safe, then yes recursive function are better as they are way easier to read/write.

    – cglacet

    Mar 11, 2019 at 9:13


62

My solution:

import collections


def flatten(x):
    if isinstance(x, collections.Iterable):
        return [a for i in x for a in flatten(i)]
    else:
        return [x]

A little more concise, but pretty much the same.

6

  • 7

    You can do this without importing anything if you just try: iter(x) to test whether it’s iterable… But I don’t think having to import a stdlib module is a downside worth avoiding.

    – abarnert

    Jul 5, 2013 at 8:03

  • 8

    Worth to note that this solution works only if all the items are of type int

    Dec 7, 2014 at 6:14

  • 3

    Could make it more concise, def flatten(x): return [a for i in x for a in flatten(i)] if isinstance(x, collections.Iterable) else [x] – but readability might be subjective here.

    – Zero

    Jul 25, 2017 at 17:13


  • 5

    this doesn’t work on strings because strings are iterable too. Replace the condition with if isinstance(x, collections.Iterable) and not isinstance(x, basestring)

    – aandis

    Nov 29, 2018 at 11:51

  • replace collections.Iterable with list

    – noobninja

    Jun 17, 2020 at 1:59

46

Generator using recursion and duck typing (updated for Python 3):

def flatten(L):
    for item in L:
        try:
            yield from flatten(item)
        except TypeError:
            yield item

list(flatten([[[1, 2, 3], [4, 5]], 6]))
>>>[1, 2, 3, 4, 5, 6]

4

  • 1

    Thanks, that works nice for Python 3. For 2.x the previous is needed: for i in flatten(item): yield i

    – dansalmo

    Sep 8, 2015 at 14:54


  • list(flatten([[‘X’], ‘Y’])) fails on 2.X variant

    – sten

    Mar 18, 2018 at 23:06

  • @user1019129 see my comment above yours

    – dansalmo

    Mar 20, 2018 at 0:14

  • yes it fails with the cycle.. i think because a string is also an “array”-of-chars

    – sten

    Mar 20, 2018 at 20:16