Flatten an irregular list of lists

Question

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?

Answer 1

Shamelessly taken from my own answer to another question.

This function

• Does not use isinstance, because it's evil and breaks duck typing.
• Uses reduce recursively. There has to be an answer using reduce.
• Works with arbitrary nested-lists whose elements are either nested-lists, or non-nested lists of atoms, or atoms (subjected to recursion limit).
• Does not LBYL.
• But not with nested-lists that contain strings as atoms.

Code below:

def flattener(left, right):
    try:
        res = reduce(flattener, right, left)
    except TypeError:
        left.append(right)
        res = left
    return res


def flatten(seq):
    return reduce(flattener, seq, [])


>>> nested_list = [0, [1], [[[[2]]]],
                   [3, [], [4, 5]],
                   [6, [7, 8],
                    9, [[[]], 10,
                        []]],
                   11, [], [],
                   [12]]
>>> flatten(nested_list)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

Answer 2

Although an elegant and very pythonic answer has been selected I would present my solution just for the review:

def flat(l):
    ret = []
    for i in l:
        if isinstance(i, list) or isinstance(i, tuple):
            ret.extend(flat(i))
        else:
            ret.append(i)
    return ret

Please tell how good or bad this code is?

Answer 3

Using itertools.chain:

import itertools
from collections import Iterable

def list_flatten(lst):
    flat_lst = []
    for item in itertools.chain(lst):
        if isinstance(item, Iterable):
            item = list_flatten(item)
            flat_lst.extend(item)
        else:
            flat_lst.append(item)
    return flat_lst

Or without chaining:

def flatten(q, final):
    if not q:
        return
    if isinstance(q, list):
        if not isinstance(q[0], list):
            final.append(q[0])
        else:
            flatten(q[0], final)
        flatten(q[1:], final)
    else:
        final.append(q)

Answer 4

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.

Answer 5

Here's a simple function that flattens lists of arbitrary depth. No recursion, to avoid stack overflow.

from copy import deepcopy

def flatten_list(nested_list):
    """Flatten an arbitrarily nested list, without recursion (to avoid
    stack overflows). Returns a new list, the original list is unchanged.

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

    """
    nested_list = deepcopy(nested_list)

    while nested_list:
        sublist = nested_list.pop(0)

        if isinstance(sublist, list):
            nested_list = sublist + nested_list
        else:
            yield sublist

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!