Welcome, guest | Sign In | My Account | Store | Cart

Flatten a nested array/tuple

Python, 19 lines
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
flatten = lambda arr: reduce(lambda x, y: ((isinstance(y, (list, tuple)) or x.append(y)) and x.extend(flatten(y))) or x, arr, [])

def flatten(array):
	"""
		Returns a list o flatten elements of every inner lists (or tuples)
		****RECURSIVE****
	"""
	res = []
	for el in array:
		if isinstance(el, (list, tuple)):
			res.extend(flatten(el))
			continue
		res.append(el)
	return res


>>> a = [0, 10, 20, [30, (40, 50, [60, [70, [80]], {'hello': 'world'}]), 90], set(['world', 'hello'])]
>>> flatten(a)
[0, 10, 20, 30, 40, 50, 60, 70, 80, {'hello': 'world'}, 90, set(['world', 'hello'])]

Recently i needed to flat a list of elements (don't ask why or how, i just needed) and all i could find on internet was some flatten for 2-levels depth arrays, so i wrote my own function and posted here if can be of any use for anyone.

the 2 versions, lambda and standard "def ...", do the same work. I just did them both for the sake of someone although i prefer the second one (i could use comments and it's a little faster)

4 comments

Przemyslaw Podczasi 12 years, 5 months ago  # | flag

same but non recursive version:

def make_flat(l):
    res = []
    iters_stack = [iter(l)]
    while iters_stack:
        for e in iters_stack[-1]:
            if isinstance(e, (tuple,list)):
                iters_stack.append(iter(e))
                break
            res.append(e)
        else:
            iters_stack.pop()
    return res
Robin Becker 12 years, 5 months ago  # | flag

I tried several flatten routines (see below) and find qflatten to be fastest (at least on my pc with python2.6); iflatten is like the iterative version above and p/rflatten are like the recursive original (with hopefully some speedups). The qflatten version is based on one that is in reportlab (also with some speed ups). Of course the speedups won't really work for very short inputs.

def iflatten(L):
    I=(tuple,list)
    r_append = [].append
    stack = [iter(L)]
    stack_append = stack.append
    stack_pop = stack.pop
    while stack:
        for e in stack[-1]:
            if isinstance(e,I):
                stack_append(iter(e))
                break
            r_append(e)
        else:
            stack_pop()
    return r_append.__self__

lflatten = lambda arr: reduce(lambda x, y: ((isinstance(y, (list, tuple)) or x.append(y)) and x.extend(lflatten(y))) or x, arr, [])

def pflatten(L):
    I=(tuple,list)
    r = []
    for e in L:
        if isinstance(e, I):
            r.extend(rflatten(e))
            continue
        r.append(e)
    return r

def rflatten(L):
    I=(tuple,list)
    r = []
    r_append = r.append
    r_extend = r.extend
    for e in L:
        if isinstance(e, I):
            r_extend(rflatten(e))
            continue
        r_append(e)
    return r


def _qflatten(L,a,I):
    for x in L:
        if isinstance(x,I): _flatten(x,a,I)
        else: a(x)

def qflatten(L):
    R = []
    _qflatten(L,R.append,(list,tuple))
    return R
Robin Becker 12 years, 5 months ago  # | flag

whoops the _qflatten is actually written

def _qflatten(L,a,I):
    for x in L:
        if isinstance(x,I): _qflatten(x,a,I)
        else: a(x)
Luca Zarotti (author) 12 years, 5 months ago  # | flag

thanks for the replies. the ones i posted were something between readable and performance, few rows and instructions, that's why i choose the recursive way, even if i know that the make_flat logic is better for performance when you have to compute many operations.

the rflatten and iflatten makes a useful improvment to performance if you have a lot of inputs. and i'm sure that more improvements can be made, like

def flatten(*array): and flatten(*el)

so you can use flatten(array1, array2, array3), if you want, instead of flatten([array1, array2, array3]).

ps: the lambda one was a joke :) ignore it: is not intended to use but some people wants the absolutely less rows for code, and go mad if they see a lambda solution, despite performance or readability

Created by Luca Zarotti on Mon, 31 Oct 2011 (MIT)
Python recipes (4591)
Luca Zarotti's recipes (1)

Required Modules

  • (none specified)

Other Information and Tasks