Flatten an irregular (arbitrarily nested) list of lists

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

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.

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)

This version of flatten avoids python's recursion limit (and thus works with arbitrarily deep, nested iterables). It is a generator which can handle strings and arbitrary iterables (even infinite ones).

import itertools as IT
import collections

def flatten(iterable, ltypes=collections.Iterable):
    remainder = iter(iterable)
    while True:
        first = next(remainder)
        if isinstance(first, ltypes) and not isinstance(first, (str, bytes)):
            remainder = IT.chain(first, remainder)
        else:
            yield first

Here are some examples demonstrating its use:

print(list(IT.islice(flatten(IT.repeat(1)),10)))
# [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

print(list(IT.islice(flatten(IT.chain(IT.repeat(2,3),
                                       {10,20,30},
                                       'foo bar'.split(),
                                       IT.repeat(1),)),10)))
# [2, 2, 2, 10, 20, 30, 'foo', 'bar', 1, 1]

print(list(flatten([[1,2,[3,4]]])))
# [1, 2, 3, 4]

seq = ([[chr(i),chr(i-32)] for i in range(ord('a'), ord('z')+1)] + list(range(0,9)))
print(list(flatten(seq)))
# ['a', 'A', 'b', 'B', 'c', 'C', 'd', 'D', 'e', 'E', 'f', 'F', 'g', 'G', 'h', 'H',
# 'i', 'I', 'j', 'J', 'k', 'K', 'l', 'L', 'm', 'M', 'n', 'N', 'o', 'O', 'p', 'P',
# 'q', 'Q', 'r', 'R', 's', 'S', 't', 'T', 'u', 'U', 'v', 'V', 'w', 'W', 'x', 'X',
# 'y', 'Y', 'z', 'Z', 0, 1, 2, 3, 4, 5, 6, 7, 8]

Although flatten can handle infinite generators, it can not handle infinite nesting:

def infinitely_nested():
    while True:
        yield IT.chain(infinitely_nested(), IT.repeat(1))

print(list(IT.islice(flatten(infinitely_nested()), 10)))
# hangs

def flatten(xs):
    res = []
    def loop(ys):
        for i in ys:
            if isinstance(i, list):
                loop(i)
            else:
                res.append(i)
    loop(xs)
    return res

Here's another answer that is even more interesting...

import re

def Flatten(TheList):
    a = str(TheList)
    b,_Anon = re.subn(r'[\[,\]]', ' ', a)
    c = b.split()
    d = [int(x) for x in c]

    return(d)

Basically, it converts the nested list to a string, uses a regex to strip out the nested syntax, and then converts the result back to a (flattened) list.

Pandas has a function that does this. It returns an iterator as you mentioned.

In [1]: import pandas
In [2]: pandas.core.common.flatten([[[1, 2, 3], [4, 5]], 6])
Out[2]: <generator object flatten at 0x7f12ade66200>
In [3]: list(pandas.core.common.flatten([[[1, 2, 3], [4, 5]], 6]))
Out[3]: [1, 2, 3, 4, 5, 6]

I prefer simple answers. No generators. No recursion or recursion limits. Just iteration:

def flatten(TheList):
    listIsNested = True

    while listIsNested:                 #outer loop
        keepChecking = False
        Temp = []

        for element in TheList:         #inner loop
            if isinstance(element,list):
                Temp.extend(element)
                keepChecking = True
            else:
                Temp.append(element)

        listIsNested = keepChecking     #determine if outer loop exits
        TheList = Temp[:]

    return TheList

This works with two lists: an inner for loop and an outer while loop.

The inner for loop iterates through the list. If it finds a list element, it (1) uses list.extend() to flatten that part one level of nesting and (2) switches keepChecking to True. keepchecking is used to control the outer while loop. If the outer loop gets set to true, it triggers the inner loop for another pass.

Those passes keep happening until no more nested lists are found. When a pass finally occurs where none are found, keepChecking never gets tripped to true, which means listIsNested stays false and the outer while loop exits.

The flattened list is then returned.

Test-run

flatten([1,2,3,4,[100,200,300,[1000,2000,3000]]])

[1, 2, 3, 4, 100, 200, 300, 1000, 2000, 3000]

When trying to answer such a question you really need to give the limitations of the code you propose as a solution. If it was only about performances I wouldn't mind too much, but most of the codes proposed as solution (including the accepted answer) fail to flatten any list that has a depth greater than 1000.

When I say most of the codes I mean all codes that use any form of recursion (or call a standard library function that is recursive). All these codes fail because for every of the recursive call made, the (call) stack grow by one unit, and the (default) python call stack has a size of 1000.

If you're not too familiar with the call stack, then maybe the following will help (otherwise you can just scroll to the Implementation).

Call stack size and recursive programming (dungeon analogy)

Finding the treasure and exit

Imagine you enter a huge dungeon with numbered rooms, looking for a treasure. You don't know the place but you have some indications on how to find the treasure. Each indication is a riddle (difficulty varies, but you can't predict how hard they will be). You decide to think a little bit about a strategy to save time, you make two observations:

1. It's hard (long) to find the treasure as you'll have to solve (potentially hard) riddles to get there.
2. Once the treasure found, returning to the entrance may be easy, you just have to use the same path in the other direction (though this needs a bit of memory to recall your path).

When entering the dungeon, you notice a small notebook here. You decide to use it to write down every room you exit after solving a riddle (when entering a new room), this way you'll be able to return back to the entrance. That's a genius idea, you won't even spend a cent implementing your strategy.

You enter the dungeon, solving with great success the first 1001 riddles, but here comes something you hadn't planed, you have no space left in the notebook you borrowed. You decide to abandon your quest as you prefer not having the treasure than being lost forever inside the dungeon (that looks smart indeed).

Executing a recursive program

Basically, it's the exact same thing as finding the treasure. The dungeon is the computer's memory, your goal now is not to find a treasure but to compute some function (find f(x) for a given x). The indications simply are sub-routines that will help you solving f(x). Your strategy is the same as the call stack strategy, the notebook is the stack, the rooms are the functions' return addresses:

x = ["over here", "am", "I"]
y = sorted(x) # You're about to enter a room named `sorted`, note down the current room address here so you can return back: 0x4004f4 (that room address looks weird)
# Seems like you went back from your quest using the return address 0x4004f4
# Let's see what you've collected 
print(' '.join(y))

The problem you encountered in the dungeon will be the same here, the call stack has a finite size (here 1000) and therefore, if you enter too many functions without returning back then you'll fill the call stack and have an error that look like "Dear adventurer, I'm very sorry but your notebook is full": RecursionError: maximum recursion depth exceeded. Note that you don't need recursion to fill the call stack, but it's very unlikely that a non-recursive program call 1000 functions without ever returning. It's important to also understand that once you returned from a function, the call stack is freed from the address used (hence the name "stack", return address are pushed in before entering a function and pulled out when returning). In the special case of a simple recursion (a function f that call itself once -- over and over --) you will enter f over and over until the computation is finished (until the treasure is found) and return from f until you go back to the place where you called f in the first place. The call stack will never be freed from anything until the end where it will be freed from all return addresses one after the other.

How to avoid this issue?

That's actually pretty simple: "don't use recursion if you don't know how deep it can go". That's not always true as in some cases, Tail Call recursion can be Optimized (TCO). But in python, this is not the case, and even "well written" recursive function will not optimize stack use. There is an interesting post from Guido about this question: Tail Recursion Elimination.

There is a technique that you can use to make any recursive function iterative, this technique we could call bring your own notebook. For example, in our particular case we simply are exploring a list, entering a room is equivalent to entering a sublist, the question you should ask yourself is how can I get back from a list to its parent list? The answer is not that complex, repeat the following until the stack is empty:

1. push the current list address and index in a stack when entering a new sublist (note that a list address+index is also an address, therefore we just use the exact same technique used by the call stack);
2. every time an item is found, yield it (or add them in a list);
3. once a list is fully explored, go back to the parent list using the stack return address (and index).

Also note that this is equivalent to a DFS in a tree where some nodes are sublists A = [1, 2] and some are simple items: 0, 1, 2, 3, 4 (for L = [0, [1,2], 3, 4]). The tree looks like this:

                    L
                    |
           -------------------
           |     |     |     |
           0   --A--   3     4
               |   |
               1   2

The DFS traversal pre-order is: L, 0, A, 1, 2, 3, 4. Remember, in order to implement an iterative DFS you also "need" a stack. The implementation I proposed before result in having the following states (for the stack and the flat_list):

init.:  stack=[(L, 0)]
**0**:  stack=[(L, 0)],         flat_list=[0]
**A**:  stack=[(L, 1), (A, 0)], flat_list=[0]
**1**:  stack=[(L, 1), (A, 0)], flat_list=[0, 1]
**2**:  stack=[(L, 1), (A, 1)], flat_list=[0, 1, 2]
**3**:  stack=[(L, 2)],         flat_list=[0, 1, 2, 3]
**3**:  stack=[(L, 3)],         flat_list=[0, 1, 2, 3, 4]
return: stack=[],               flat_list=[0, 1, 2, 3, 4]

In this example, the stack maximum size is 2, because the input list (and therefore the tree) have depth 2.

Implementation

For the implementation, in python you can simplify a little bit by using iterators instead of simple lists. References to the (sub)iterators will be used to store sublists return addresses (instead of having both the list address and the index). This is not a big difference but I feel this is more readable (and also a bit faster):

def flatten(iterable):
    return list(items_from(iterable))

def items_from(iterable):
    cursor_stack = [iter(iterable)]
    while cursor_stack:
        sub_iterable = cursor_stack[-1]
        try:
            item = next(sub_iterable)
        except StopIteration:   # post-order
            cursor_stack.pop()
            continue
        if is_list_like(item):  # pre-order
            cursor_stack.append(iter(item))
        elif item is not None:
            yield item          # in-order

def is_list_like(item):
    return isinstance(item, list)

Also, notice that in is_list_like I have isinstance(item, list), which could be changed to handle more input types, here I just wanted to have the simplest version where (iterable) is just a list. But you could also do that:

def is_list_like(item):
    try:
        iter(item)
        return not isinstance(item, str)  # strings are not lists (hmm...) 
    except TypeError:
        return False

This considers strings as "simple items" and therefore flatten_iter([["test", "a"], "b]) will return ["test", "a", "b"] and not ["t", "e", "s", "t", "a", "b"]. Remark that in that case, iter(item) is called twice on each item, let's pretend it's an exercise for the reader to make this cleaner.

Testing and remarks on other implementations

In the end, remember that you can't print a infinitely nested list L using print(L) because internally it will use recursive calls to __repr__ (RecursionError: maximum recursion depth exceeded while getting the repr of an object). For the same reason, solutions to flatten involving str will fail with the same error message.

If you need to test your solution, you can use this function to generate a simple nested list:

def build_deep_list(depth):
    """Returns a list of the form $l_{depth} = [depth-1, l_{depth-1}]$
    with $depth > 1$ and $l_0 = [0]$.
    """
    sub_list = [0]
    for d in range(1, depth):
        sub_list = [d, sub_list]
    return sub_list

Which gives: build_deep_list(5) >>> [4, [3, [2, [1, [0]]]]].

Just use a funcy library: pip install funcy

import funcy


funcy.flatten([[[[1, 1], 1], 2], 3]) # returns generator
funcy.lflatten([[[[1, 1], 1], 2], 3]) # returns list

I am aware that there are already many awesome answers but i wanted to add an answer that uses the functional programming method of solving the question. In this answer i make use of double recursion :

def flatten_list(seq):
    if not seq:
        return []
    elif isinstance(seq[0],list):
        return (flatten_list(seq[0])+flatten_list(seq[1:]))
    else:
        return [seq[0]]+flatten_list(seq[1:])

print(flatten_list([1,2,[3,[4],5],[6,7]]))

output:

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

This is a simple implement of flatten on python2

flatten=lambda l: reduce(lambda x,y:x+y,map(flatten,l),[]) if isinstance(l,list) else [l]

test=[[1,2,3,[3,4,5],[6,7,[8,9,[10,[11,[12,13,14]]]]]],]
print flatten(test)

#output [1, 2, 3, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

No recursion or nested loops. A few lines. Well formatted and easy to read:

def flatten_deep(arr: list):
    """ Flattens arbitrarily-nested list `arr` into single-dimensional. """

    while arr:
        if isinstance(arr[0], list):  # Checks whether first element is a list
            arr = arr[0] + arr[1:]  # If so, flattens that first element one level
        else:
            yield arr.pop(0)  # Otherwise yield as part of the flat array

flatten_deep(L)

From my own code at https://github.com/jorgeorpinel/flatten_nested_lists/blob/master/flatten.py

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!

I'm new to python and come from a lisp background. This is what I came up with (check out the var names for lulz):

def flatten(lst):
    if lst:
        car,*cdr=lst
        if isinstance(car,(list,tuple)):
            if cdr: return flatten(car) + flatten(cdr)
            return flatten(car)
        if cdr: return [car] + flatten(cdr)
        return [car]

Seems to work. Test:

flatten((1,2,3,(4,5,6,(7,8,(((1,2)))))))

returns:

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

From my previous answer, this function flattens most cases I can think of. I believe this works down to python 2.3.

def flatten(item, keepcls=(), keepobj=()):
    if not hasattr(item, '__iter__') or isinstance(item, keepcls) or item in keepobj:
        yield item
    else:
        for i in item:
            for j in flatten(i, keepcls, keepobj + (item,)):
                yield j

Circular lists

>>> list(flatten([1, 2, [...], 3]))
[1, 2, [1, 2, [...], 3], 3]

Depth first lists

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

Nested repeated lists:

>>> list(flatten([[1,2],[1,[1,2]],[1,2]]))
[1, 2, 1, 1, 2, 1, 2]

Lists with dicts (or other objects to not flatten)

>>> list(flatten([1,2, {'a':1, 'b':2}, 'text'], keepcls=(dict, str)))
[1, 2, {'a': 1, 'b': 2}, 'text']

Any iterables

>>> list(flatten((x for x in [1,2, set([3,(4,5),6])])))
[1, 2, 4, 5, 3, 6]

You may want to keep some default classes in keepcls to make calling the function more terse.

def nested_list(depth):
    l = [depth]
    for i in range(depth-1, 0, -1):
        l = [i, l]
    return l

nested_list(10)

[1, [2, [3, [4, [5, [6, [7, [8, [9, [10]]]]]]]]]]

def Flatten(ul):
    fl = []
    for i in ul:
        if type(i) is list:
            fl += Flatten(i)
        else:
            fl += [i]
    return fl

Flatten(nested_list(10))

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Benchmarking

l = nested_list(100)

https://stackoverflow.com/a/2158532

import collections

def flatten(l):
    for el in l:
        if isinstance(el, collections.Iterable) and not isinstance(el, (str, bytes)):
            yield from flatten(el)
        else:
            yield el

%%timeit -n 1000
list(flatten(l))

320 µs ± 14.3 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

%%timeit -n 1000
Flatten(l)

60 µs ± 10.2 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

list(flatten(l)) == Flatten(l)

True

def flatten(item) -> list:
    if not isinstance(item, list): return item
    return reduce(lambda x, y: x + [y] if not isinstance(y, list) else x + [*flatten(y)], item, [])

Two-line reduce function.

I modified the code of the accepted answer and added a keyword max_depth to only flatten up to a specified depth. max_depth=0 means, the list stays as it is. Maybe somebody can use it:

def flatten(l, __depth=0, max_depth=100):

    for el in l:

        if isinstance(el, collections.Iterable) and not isinstance(el, (str, bytes)):

            __depth += 1
            if __depth <= max_depth:
                yield from flatten(el, __depth=__depth, max_depth=max_depth)
            else:
                yield el
            __depth -= 1

        else:

            yield el

Some examples:

# A
l = []
depth = 5
for i in range(depth):
    el = i
    for j in range(i):
        el = [el]
    l.append(el)
# [0, [1], [[2]], [[[3]]], [[[[4]]]]]

for i in range(depth):
    print(list(flatten_gen(l, max_depth=i)))
# [0, [1], [[2]], [[[3]]], [[[[4]]]]]
# [0,  1,   [2],   [[3]],   [[[4]]]]
# [0,  1,    2,     [3],     [[4]]]
# [0,  1,    2,      3,       [4]]
# [0,  1,    2,      3,        4]


# B
l = [[1, 2], [3, 4, [5, 6, [7, [8, [9]]], 10], 12, [13]], 14, [15]]

for i in range(6):
    print(list(flatten_gen(l, max_depth=i)))
# [[1, 2], [3, 4, [5, 6, [7, [8, [9]]], 10], 12, [13]], 14, [15]]
# [ 1, 2,   3, 4, [5, 6, [7, [8, [9]]], 10], 12, [13],  14,  15]
# [ 1, 2,   3, 4,  5, 6, [7, [8, [9]]], 10,  12,  13,   14,  15]
# [ 1, 2,   3, 4,  5, 6,  7, [8, [9]],  10,  12,  13,   14,  15]
# [ 1, 2,   3, 4,  5, 6,  7,  8, [9],   10,  12,  13,   14,  15]
# [ 1, 2,   3, 4,  5, 6,  7,  8,  9,    10,  12,  13,   14,  15]

This solution is based on the python's iteration-utilities library and its function deepflatten

from iteration_utilities import deepflatten
list(deepflatten(test))

A much more efficient version of this answer: https://stackoverflow.com/a/20495215/8887313

If you have control over the creation of the list and are willing to mutate it, then it is much more efficient to use a deque (instead of pop(0) and list contatenation).

import collections

def flatten_and_consume(nested_deque: collections.deque):
    while nested_deque:
        elt = nested_deque.popleft()

        elt_is_sublist = isinstance(elt, collections.deque)
        if elt_is_sublist:
            nested_deque.extendleft(reversed(elt))
        else:
            yield elt

This is how I did it with recursion:

def flatten(x):
    if not any(isinstance(e, list) for e in x):
        return x
    while type(x[-1]) == int:
        x = [x[-1]] + [x[:-1]]
    return flatten(x = x + x.pop(-1))

Or even:

def flatten(x):
    if not any(isinstance(e, list) for e in x):
        return x
    return flatten(x = x + x.pop([isinstance(e, list) for e in x].index(1)))

The think that following would probably work in python 3:

def get_flat_iter(xparent):
    try:
        r = xparent
        if hasattr(xx, '__iter__'):
            iparent = iter(xparent)
            if iparent != xparent:
                r = map(a, xparent)
    finally:
         pass
    return r

irregular_list = [1, [2, [3, 4]]]
flat_list = list(irregular_list)
print(flat_list) # [1, 2, 3, 4]

Most of the answers are using a loop to go through the items. Here I have a variant that is using an EAFP way to do things: try to get an iterator on your input, if it succeeds run your function first on the first element, next on the remainder of this iterator. If you can't get an iterator, or if it's a string or a bytes object: yield the element.

Thanks to the suggestion from A. Kareem, who found out that my code was very slow, due to the fact that the recursion took too long for string and byte objects, here is an improved version of my code.

def flatten(x, it = None):
    try:
        if type(x) in (str, bytes):
            yield x
        else:
            if not it:
                it = iter(x)
            yield from flatten(next(it))
        if type(x) not in (str, bytes):
            yield from flatten(x, it)
    except StopIteration:
        pass
    except Exception:
        yield x

oldlist = [1,[[[["test",3]]]],((4,5,6)),[ bytes("test", encoding="utf-8"),7,[8,9]]]
newlist = [ x for x in flatten(oldlist) ]
print(newlist)
# [1, 'test', 3, 4, 5, 6, b'test', 7, 8, 9]

I've tried solving it without using any library. Simply using two nested functions does the job.

def first(list_to_flatten):
    a = []

    def second(list_to_flatten):
        for i in list_to_flatten:
            if type(i) is not list:
                a.append(i)
            else:
                list_to_flatten = i
                second(list_to_flatten)

    second(list_to_flatten)
    return a

list_to_flatten = [1, 2, [3, 4, [5, 6, [7, 8, [9, 10]]]]]
a = first(list_to_flatten)
print(a)

>>> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Simple Function Without using instances

L = [[[1, 2, 3], [4, 5]], 6]
l1 = []
def FlattenList(List1):
    for i in range(len(List1)):
        if type(List1[i]) == type([]):
            FlattenList(List1[i])
        else:
            l1.append(List1[i])
    return l1


FlattenList(L)
[1, 2, 3, 4, 5, 6]