Monday, March 14, 2011

Flattening abitrarily nested lists in Python

Lists are one of the three most important data structures in Python, other being dict and str, (tuple is the younger cousin  of list). The lists can be arbitrarily nested with any kind of data inside them, e.g.

['a', [1, 2], (3, 4, 5, [7, 8, ['gnu', 'linux']]), ['a', 'b', 'c'], [['d', 'e', 'f'], 12, [13, [14, [15,]]]]]


The objective is flatten nested lists of this kind to a single list. It can be simply stated as to remove all square brackets (and parenthesis) and retain only square brackets at the end, while maintaining the order of the items as they appear in the nested list. One of the simple solution can be:

def flatten(l):
    '''Flatten a arbitrarily nested lists and return the result as a single list.
    '''
    ret = []
    for i in l:
        if isinstance(i, list) or isinstance(i, tuple):
            ret.extend(flatten(i))
        else:
            ret.append(i)
    return ret


Run this on the example and you get:

['a', 1, 2, 3, 4, 5, 7, 8, 'gnu', 'linux', 'a', 'b', 'c', 'd', 'e', 'f', 12, 13, 14, 15]


Can this be made more Pythonic and efficient. Any ides?