# 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

```