flatten(...) (Python recipe) by Orri Ganel

ActiveState Code (http://code.activestate.com/recipes/363051/)

Flatten. I think everyone carries around a version of flatten. Search examples on groups.google.com for "flatten list python" to see people golfing for the shortest/fastest/clearest solutions.

a simple non-recursive version that modifies in-place. There is a very simple and quick flattener that can be found in the basictypes folder in the latebind.py script by Mike C. Fletcher. The source can be downloaded from

http://sourceforge.net/project/showfiles.php?group_id=87034&package_id=90541&release_id=288585

Here it is:

import sys
def flatten(inlist, type=type, ltype=(list,tuple), maxint= sys.maxint):
    """Flatten out a list."""
    try:
        # for every possible index
        for ind in xrange( maxint):
            # while that index currently holds a list
            while isinstance( inlist[ind], ltype):
                # expand that list into the index (and subsequent indicies)
                inlist[ind:ind+1] = list(inlist[ind])
            #ind = ind+1
    except IndexError:
        pass
    return inlist

I'm not sure why the "type=type" argument is present since "type" is not used in the function. Also, if you omit the last line a copy will not be returned; the modification will only be done in place.

a further simplification... Fletcher's version is really cool! I have a (slight) improvement to make it even simpler:

def flatten(l, ltypes=(list, tuple)):
    i = 0
    while (i < len(l)):
       while (isinstance(l[i], ltypes)):
           l[i:i+1] = list(l[i])
       i += 1
    return l

Since len(l) is evaluated each time through the loop, we can just run to the dynamic size of the list, no need to run to maxint and catch the index error.

Too simple?

>>> flatten([1, 2, [3, []]])
Traceback (most recent call last):
  File "", line 1, in
  File "", line 4, in flatten
IndexError: list index out of range

or simply...

>>> flatten([[]])
Traceback (most recent call last):
  File "", line 1, in
  File "", line 4, in flatten
IndexError: list index out of range

need to do something with the inner while loop so that it doesn't crash when the last element to be flattened is an empty list.

noah

Yup, good point... OK, good point. So here is a fixed version to support empty lists (in any position):

def flatten(l, ltypes=(list, tuple)):
  i = 0
  while i OK, good point. So here is a fixed version to support empty lists (in any position):

<pre>
def flatten(l, ltypes=(list, tuple)):
  i = 0
  while i

</pre>

err, it messed up my post...

def flatten(l, ltypes=(list, tuple)):
  i = 0
  while i < len(l):
    if not l[i]:
      l.pop(i)
      continue
    while isinstance(l[i], ltypes):
      l[i:i+1] = list(l[i])
    i += 1
  return l

Still problems with empty lists. >>> flatten([[[]]])

Traceback (most recent call last):

File "", line 1, in

File "/tmp/python-2596k4V", line 7, in flatten

IndexError: list index out of range

Another fix... OK, this should fix it.

def flatten(l, ltypes=(list, tuple)):
  i = 0
  while i < len(l):
    while isinstance(l[i], ltypes):
      if not l[i]:
        l.pop(i)
        if not len(l):
          break
      else:
        l[i:i+1] = list(l[i])
    i += 1
  return l

the last line doesn't copy. It just returns a reference to the in-place-modified input.

Yet another fix... OK, this should cover all the test cases now (thx John Y.).

def flatten(l, ltypes=(list, tuple)):
    ltype = type(l)
    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]
        i += 1
    return ltype(l)

recursive : [code]def flatten( listIn=[], listOut = [] ): ''' returns flattened listIn ''' for element in listIn: if getattr(element, '__iter__', False): listOut += flatten( element, [] ) else: listOut.append( element) return listOut [/code]

sorry for formatting:

def flatten( listIn=[], listOut = [] ):
    ''' returns flattened listIn '''
    for element in listIn:
        if getattr(element, '__iter__', False): listOut += flatten( element, [] )
        else: listOut.append( element)
    return listOut

<pre> def flattenlist(L): import types Types =dir(types)[:-5] Types.pop(Types.index('StringType')) Types.pop(Types.index('UnicodeType')) Types.pop(Types.index('StringTypes')) Types.pop(Types.index('ListType')) Types.pop(Types.index('ObjectType')) Types.pop(Types.index('TupleType'))

        Types = tuple(( eval("types.%s "% i ) for i in  Types))
        tmp = []
        def core(L):
            for i in L:
                if isinstance(i,Types):
                    tmp.append(i)
                    continue
                if type(i) == type(str()):
                     tmp.append(i)
                else:
                     core(i)
            return tmp
    return core(L)

<pre>

def flattenlist(L):
        Types =dir(types)[:-5]
        Types.pop(Types.index('StringType'))
        Types.pop(Types.index('UnicodeType'))
        Types.pop(Types.index('StringTypes'))
        Types.pop(Types.index('ListType'))
        Types.pop(Types.index('ObjectType'))
        Types.pop(Types.index('TupleType'))
        Types = tuple(( eval("types.%s "% i ) for i in  Types))
        tmp = []
        def core(L):
             for i in L:
                if isinstance(i,Types):
                    tmp.append(i)
                    continue
                 if type(i) == type(str()):
                    tmp.append(i)
                 else:
                    core(i)
             return tmp
        return core(L)

sorry for previous post that was a mistake

Examples

>>> x=[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[['x']]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]
>>> flattenlist(x)
['x']
>>> x=[[[[[[[[[[[[[2,3,4,{'a':[]}]]]]]]]]]]]],flattenlist]
>>> flattenlist(x)
[2, 3, 4, {'a': []}, <function flattenlist at 0x1a05320>]