Wishlist item: itertools.flatten

Michael Spencer mahs at telcopartners.com
Sat Mar 12 00:04:41 CET 2005


Ville Vainio wrote:
>>>>>>"Christos" == TZOTZIOY  <Christos> writes:
> 
> 
>     >> For quick-and-dirty stuff, it's often convenient to flatten a sequence
>     >> (which perl does, surprise surprise, by default):
>     >> 
>     >> [1,2,[3,"hello",[[4]]]]  ->
>     >> 
>     >> [1, 2, 3, 'hello', 4]
> 
>     Christos> See Python Library Reference, "5.16.3 Recipes".  Now
>     Christos> that all and any (also
> 
> The recipe is:
> 
> def flatten(listOfLists):
>     return list(chain(*listOfLists))
> 
> That one is trivial, because it only flattens one level. The
> flattening I'm talking about involves flattening to arbitrary depth to
> get a single sequence of "atoms". The itertools implementation might
> also be able to avoid recursion by using a stack.

Here's a non-recursive implementation.  There are lots around.  One issue is 
specifying iterable types which should be atomic (notably strings).  This uses a 
simple hardwired test for that.

def flatten(iterable):
     stack = []
     iterator = iter(iterable)
     while 1:
         try:
             item = iterator.next()
             if hasattr(item,"__iter__"): # Avoids iterating over strings
                 stack.append(iterator)
                 iterator = iter(item)
             else:
                 yield item
         except StopIteration:
             if stack:
                 iterator = stack.pop()
             else:
                 raise StopIteration

  >>> list(flatten([[[1,2,[3,[4,5]],[6,7,[8,[9],(10,11,12)]]]]]))
  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  >>> list(flatten(["abc","def",["ghi", "jkl"]]))
  ['abc', 'def', 'ghi', 'jkl']

Michael




More information about the Python-list mailing list