Flatten an irregular list of lists

Question

Yes  I know this subject has been covered before  here  here  here  here   but as far as I know  all solutions  except for one  fail on a list like this   L      1  2  3    4  5    6    Where the desired output is   1  2  3  4  5  6    Or perhaps even better  an iterator  The only solution I saw that works for an arbitrary nesting is found in this question   def flatten x       result          for el in x          if hasattr el     iter     and not isinstance el  basestring               result extend flatten el           else              result append el      return result  flatten L    Is this the best model  Did I overlook something  Any problems

User · Answer

Pandas has a function that does this  It returns an iterator as you mentioned  In  1   import pandas In  2   pandas core common flatten    1  2  3    4  5    6   Out 2    lt generator object flatten at 0x7f12ade66200 gt  In  3   list pandas core common flatten    1  2  3    4  5    6    Out 3    1  2  3  4  5  6

User · Answer

Here is my functional version of recursive flatten which handles both tuples and lists  and lets you throw in any mix of positional arguments  Returns a generator which produces the entire sequence in order  arg by arg   flatten   lambda  n   e for a in n     for e in  flatten  a  if isinstance a   tuple  list   else  a       Usage   l1     a     b     c    d     l2    0  1   2  3     4  5   6  7   8     9    10     11    print list flatten l1  -2  -1  l2     a    b    c    d   -2  -1  0  1  2  3  4  5  6  7  8  9  10  11

User · Answer

Simple Function Without using instances  L      1  2  3    4  5    6  l1      def FlattenList List1       for i in range len List1            if type List1 i      type                  FlattenList List1 i           else              l1 append List1 i       return l1   FlattenList L   1  2  3  4  5  6

User · Answer

Although an elegant and very pythonic answer has been selected I would present my solution just for the review   def flat l       ret          for i in l          if isinstance i  list  or isinstance i  tuple               ret extend flat i           else              ret append i      return ret   Please tell how good or bad this code is

User · Answer

I m not sure if this is necessarily quicker or more effective  but this is what I do   def flatten lst       return eval       str lst  replace          replace                  L      1  2  3    4  5    6  print flatten L     The flatten function here turns the list into a string  takes out all of the square brackets  attaches square brackets back onto the ends  and turns it back into a list    Although  if you knew you would have square brackets in your list in strings  like   1  2     3  4  and  5     you would have to do something else

User · Answer

Here s the compiler ast flatten implementation in 2 7 5   def flatten seq       l          for elt in seq          t   type elt          if t is tuple or t is list              for elt2 in flatten elt                   l append elt2          else              l append elt      return l   There are better  faster methods  If you ve reached here  you have seen them already   Also note      Deprecated since version 2 6  The compiler package has been removed in Python 3

User · Answer

Shamelessly taken from my own answer to another question   This function   Does not use isinstance  because it s evil and breaks duck typing  Uses reduce recursively   There has to be an answer using reduce  Works with arbitrary nested-lists whose elements are either nested-lists  or non-nested lists of atoms  or atoms  subjected to recursion limit   Does not LBYL  But not with nested-lists that contain strings as atoms    Code below   def flattener left  right       try          res   reduce flattener  right  left      except TypeError          left append right          res   left     return res   def flatten seq       return reduce flattener  seq         gt  gt  gt  nested list    0   1       2                          3       4  5                        6   7  8                       9         10                                                   11                              12    gt  gt  gt  flatten nested list   0  1  2  3  4  5  6  7  8  9  10  11  12

User · Answer

The easiest way is to use the morph library using pip install morph   The code is   import morph  list      1  2  3    4  5    6  flattened list   morph flatten list     returns  1  2  3  4  5  6

User · Answer

Without using any library   def flat l       def  flat l  r               if type l  is not list              r append l          else              for i in l                  r   r   flat i          return r     return  flat l           example test     1     2     3      a   b   c        z   x   y       d   f   g     4      print flat test    prints  1  2  3   a    b    c    z    x    y    d    f    g   4

User · Answer

def flatten item  - gt  list      if not isinstance item  list   return item     return reduce lambda x  y  x    y  if not isinstance y  list  else x     flatten y    item        Two-line reduce function

User · Answer

Using itertools chain   import itertools from collections import Iterable  def list flatten lst       flat lst          for item in itertools chain lst           if isinstance item  Iterable               item   list flatten item              flat lst extend item          else              flat lst append item      return flat lst   Or without chaining   def flatten q  final       if not q          return     if isinstance q  list           if not isinstance q 0   list               final append q 0           else              flatten q 0   final          flatten q 1    final      else          final append q

User · Answer

def nested list depth       l    depth      for i in range depth-1  0  -1           l    i  l      return l  nested list 10        1   2   3   4   5   6   7   8   9   10             def Flatten ul       fl          for i in ul          if type i  is list              fl    Flatten i          else              fl     i      return fl  Flatten nested list 10         1  2  3  4  5  6  7  8  9  10    Benchmarking  l   nested list 100    https   stackoverflow com a 2158532   import collections  def flatten l       for el in l          if isinstance el  collections Iterable  and not isinstance el   str  bytes                yield from flatten el          else              yield el     timeit -n 1000 list flatten l        320   s    14 3   s per loop  mean    std  dev  of 7 runs  1000 loops each      timeit -n 1000 Flatten l       60   s    10 2   s per loop  mean    std  dev  of 7 runs  1000 loops each    list flatten l      Flatten l       True

User · Answer

This is a simple implement of flatten on python2  flatten lambda l  reduce lambda x y x y map flatten l      if isinstance l list  else  l   test   1 2 3  3 4 5   6 7  8 9  10  11  12 13 14         print flatten test    output  1  2  3  3  4  5  6  7  8  9  10  11  12  13  14

User · Answer

def flatten xs       res          def loop ys           for i in ys              if isinstance i  list                   loop i              else                  res append i      loop xs      return res

User · Answer

I didn t go through all the already available answers here  but here is a one liner I came up with  borrowing from lisp s way of first and rest list processing   def flatten l   return flatten l 0      flatten l 1    if len l   gt  1 else     if type l  is list else  l    here is one simple and one not-so-simple case -   gt  gt  gt  flatten  1  2 3  4    1  2  3  4    gt  gt  gt  flatten  1   2  3   4   5   6    name    some name    age  30   7     8  9   10   11   12   13    some    set    14   15   some string    16   17  18   19   20   21  22   23  24   25   26  27  28  29  30    1  2  3  4  5  6    age   30   name    some name    7  8  9  10  11  12  13  set   set    some     14  15   some string   16  17  18  19  20  21  22  23  24  25  26  27  28  29  30   gt  gt  gt

User · Answer

Here is another py2 approach  Im not sure if its the fastest or the most elegant nor safest      from collections import Iterable from itertools import imap  repeat  chain   def flat seqs  ignore  int  long  float  basestring        return repeat seqs  1  if any imap isinstance  repeat seqs   ignore   or not isinstance seqs  Iterable  else chain from iterable imap flat  seqs     It can ignore any specific  or derived  type you would like  it returns an iterator  so you can convert it to any specific container such as list  tuple  dict or simply consume it in order to reduce memory footprint  for better or worse it can handle initial non-iterable objects such as int      Note most of the heavy lifting is done in C  since as far as I know thats how itertools are implemented  so while it is recursive  AFAIK it isn t bounded by python recursion depth since the function calls are happening in C  though this doesn t mean you are bounded by memory  specially in OS X where its stack size has a hard limit as of today  OS X Mavericks       there is a slightly faster approach  but less portable method  only use it if you can assume that the base elements of the input can be explicitly determined otherwise  you ll get an infinite recursion  and OS X with its limited stack size  will throw a segmentation fault fairly quickly      def flat seqs  ignore  int  long  float  str  unicode        return repeat seqs  1  if type seqs  in ignore or not isinstance seqs  Iterable  else chain from iterable imap flat  seqs     here we are using sets to check for the type so it takes O 1  vs O number of types  to check whether or not an element should be ignored  though of course any value with derived type of the stated ignored types will fail  this is why its using str  unicode so use it with caution      tests   import random  def test flat test size 2000       def increase depth value  depth 1           for func in xrange depth               value   repeat value  1          return value      def random sub chaining nested values           for values in nested values              yield chain  values    chain from iterable imap next  repeat nested values  random randint 1  10           expected values   zip xrange test size   imap str  xrange test size        nested values   random sub chaining  increase depth value  depth  for depth  value in enumerate expected values        assert not any imap cmp  chain from iterable expected values   flat chain        nested values              gt  gt  gt  test flat    gt  gt  gt  list flat    1  2  3    4  5    6     1  2  3  4  5  6   gt  gt  gt       uname -a Darwin Samys-MacBook-Pro local 13 3 0 Darwin Kernel Version 13 3 0  Tue Jun  3 21 27 35 PDT 2014  root xnu-2422 110 17 1 RELEASE X86 64 x86 64   python --version Python 2 7 5

User · Answer

Here s a simple function that flattens lists of arbitrary depth  No recursion  to avoid stack overflow   from copy import deepcopy  def flatten list nested list          Flatten an arbitrarily nested list  without recursion  to avoid     stack overflows   Returns a new list  the original list is unchanged        gt  gt  list flatten list  1  2  3   4                5                  1  2  3  4  5       gt  gt  list flatten list   1  2   3         1  2  3               nested list   deepcopy nested list       while nested list          sublist   nested list pop 0           if isinstance sublist  list               nested list   sublist   nested list         else              yield sublist

User · Answer

Python-3  from collections import Iterable  L      1  2  3    4  5    6  7  8 9  10      def flatten thing       result           if isinstance thing  Iterable           for item in thing              result extend flatten item       else          result append thing       return result   flat   flatten L  print flat

User · Answer

Generator using recursion and duck typing  updated for Python 3    def flatten L       for item in L          try              yield from flatten item          except TypeError              yield item  list flatten    1  2  3    4  5    6     gt  gt  gt  1  2  3  4  5  6

User · Answer

I m surprised no one has thought of this  Damn recursion I don t get the recursive answers that the advanced people here made  anyway here is my attempt on this  caveat is it s very specific to the OP s use case  import re  L      1  2  3    4  5    6  flattened list   re sub               str L   replace          split      new list   list map int  flattened list   print new list    output    1  2  3  4  5  6

User · Answer

Most of the answers are using a loop to go through the items  Here I have a variant that is using an EAFP way to do things  try to get an iterator on your input  if it succeeds run your function first on the first element  next on the remainder of this iterator  If you can t get an iterator  or if it s a string or a bytes object  yield the element  Thanks to the suggestion from A  Kareem  who found out that my code was very slow  due to the fact that the recursion took too long for string and byte objects  here is an improved version of my code  def flatten x  it   None       try          if type x  in  str  bytes               yield x         else              if not it                  it   iter x              yield from flatten next it           if type x  not in  str  bytes               yield from flatten x  it      except StopIteration          pass     except Exception          yield x  oldlist    1      quot test quot  3       4 5 6     bytes  quot test quot   encoding  quot utf-8 quot   7  8 9    newlist     x for x in flatten oldlist    print newlist     1   test   3  4  5  6  b test   7  8  9

User · Answer

You could use deepflatten from the 3rd party package iteration utilities    gt  gt  gt  from iteration utilities import deepflatten  gt  gt  gt  L      1  2  3    4  5    6   gt  gt  gt  list deepflatten L    1  2  3  4  5  6    gt  gt  gt  list deepflatten L  types list      only flatten  inner  lists  1  2  3  4  5  6    It s an iterator so you need to iterate it  for example by wrapping it with list or using it in a loop   Internally it uses an iterative approach instead of an recursive approach and it s written as C extension so it can be faster than pure python approaches    gt  gt  gt   timeit list deepflatten L   12 6   s    298 ns per loop  mean    std  dev  of 7 runs  100000 loops each   gt  gt  gt   timeit list deepflatten L  types list   8 7   s    139 ns per loop  mean    std  dev  of 7 runs  100000 loops each    gt  gt  gt   timeit list flatten L       Cristian - Python 3 x approach from https   stackoverflow com a 2158532 5393381 86 4   s    4 42   s per loop  mean    std  dev  of 7 runs  10000 loops each    gt  gt  gt   timeit list flatten L       Josh Lee - https   stackoverflow com a 2158522 5393381 107   s    2 99   s per loop  mean    std  dev  of 7 runs  10000 loops each    gt  gt  gt   timeit list genflat L  list      Alex Martelli - https   stackoverflow com a 2159079 5393381 23 1   s    710 ns per loop  mean    std  dev  of 7 runs  10000 loops each      I m the author of the iteration utilities library

User · Answer

Just use a funcy library  pip install funcy  import funcy   funcy flatten     1  1   1   2   3     returns generator funcy lflatten     1  1   1   2   3     returns list

User · Answer

If you like recursion  this might be a solution of interest to you   def f E       if E               return        elif type E     list           return  E      else          a   f E 0           b   f E 1            a extend b          return a   I actually adapted this from some practice Scheme code that I had written a while back    Enjoy

User · Answer

Iterative solution with Python 3  This solution may work with all objects except str and bytes   from collections import Iterable from collections import Iterator   def flat iter obj       stack    obj      while stack          element   stack pop           if element and isinstance element  Iterator               stack append element              try                  stack append next element               except StopIteration                  stack pop           elif isinstance element  Iterable  and not isinstance element   str  bytes                stack append iter element           else              yield element   tree list      1 2 3   4 5 6   7 8   next element is 5      5 6      3 4 5   foo1    foo2    foo3     not iterable   10  it1   flat iter tree list  it2   flat iter not iterable   print list it1   print list it2         1  2  3  4  5  6  7  8   next element is 5   5  6  3  4  5   foo1    foo2    foo3         10

User · Answer

I don t see anything like this posted around here and just got here from a closed question on the same subject  but why not just do something like this if you know the type of the list you want to split     gt  gt  gt  a    1  2  3  5  10   1  25  11   1  0         gt  gt  gt  g   str a  replace          replace               gt  gt  gt  b    int x  for x in g split      if x strip      You would need to know the type of the elements but I think this can be generalised and in terms of speed I think it would be faster

User · Answer

I am aware that there are already many awesome answers but i wanted to add an answer that uses the functional programming method of solving the question  In this answer i make use of double recursion    def flatten list seq       if not seq          return        elif isinstance seq 0  list           return  flatten list seq 0   flatten list seq 1         else          return  seq 0   flatten list seq 1     print flatten list  1 2  3  4  5   6 7       output    1  2  3  4  5  6  7

User · Answer

Generator version of  unutbu s non-recursive solution  as requested by  Andrew in a comment   def genflat l  ltypes collections Sequence       l   list l      i   0     while i  lt  len l           while isinstance l i   ltypes               if not l i                   l pop i                  i -  1                 break             else                  l i i   1    l i          yield l i          i    1   Slightly simplified version of this generator   def genflat l  ltypes collections Sequence       l   list l      while l          while l and isinstance l 0   ltypes               l 0 1    l 0          if l  yield l pop 0

User · Answer

We can also use the  type  function of python  When iterating the list we check if the item is a list or not  If not we  append  it else we  extend  it  Here is a sample code -   l  1 2  3 4  5  6 7 8   x    for i in l      if type i  is list          x extend i      else          x append i  print x   Output    1  2  3  4  5  6  7  8    For more info on append   and extend   check this website   https   docs python org 2 tutorial datastructures html

User · Answer

No recursion or nested loops  A few lines  Well formatted and easy to read   def flatten deep arr  list       Flattens arbitrarily-nested list  arr  into single-dimensional       while arr      if isinstance arr 0   list      Checks whether first element is a list         arr   arr 0    arr 1      If so  flattens that first element one level     else          yield arr pop 0     Otherwise yield as part of the flat array  flatten deep L       From my own code at https   github com jorgeorpinel flatten nested lists blob master flatten py

User · Answer

L2    o for k in   j  if not isinstance j list  else j for j in  k for i in   m  if not  isinstance m list  else m for m in L  for k in i   for o in k

User · Answer

This version of flatten avoids python s recursion limit  and thus works with arbitrarily deep  nested iterables   It is a generator which can handle strings and arbitrary iterables  even infinite ones    import itertools as IT import collections  def flatten iterable  ltypes collections Iterable       remainder   iter iterable      while True          first   next remainder          if isinstance first  ltypes  and not isinstance first   str  bytes                remainder   IT chain first  remainder          else              yield first   Here are some examples demonstrating its use   print list IT islice flatten IT repeat 1   10       1  1  1  1  1  1  1  1  1  1   print list IT islice flatten IT chain IT repeat 2 3                                           10 20 30                                           foo bar  split                                           IT repeat 1     10       2  2  2  10  20  30   foo    bar   1  1   print list flatten   1 2  3 4          1  2  3  4   seq      chr i  chr i-32   for i in range ord  a    ord  z   1     list range 0 9    print list flatten seq        a    A    b    B    c    C    d    D    e    E    f    F    g    G    h    H      i    I    j    J    k    K    l    L    m    M    n    N    o    O    p    P      q    Q    r    R    s    S    t    T    u    U    v    V    w    W    x    X      y    Y    z    Z   0  1  2  3  4  5  6  7  8    Although flatten can handle infinite generators  it can not handle infinite nesting   def infinitely nested        while True          yield IT chain infinitely nested    IT repeat 1    print list IT islice flatten infinitely nested     10      hangs

User · Answer

I used recursive to solve nested list with any depth  def combine nlist nlist init 0 combiner lambda x y  x y               apply function  combiner to a nested list element by element treated as flatten list              current value init     for each item in nlist          if isinstance each item list               current value  combine nlist each item current value combiner          else              current value   combiner current value each item      return current value   So after i define function combine nlist  it is easy to use this function do flatting  Or you can combine it into one function  I like my solution because it can be applied to any nested list   def flatten nlist nlist       return combine nlist nlist    lambda x y x  y     result  In  379   flatten nlist  1 2 3  4 5   6     7  8  9  10   Out 379    1  2  3  4  5  6  7  8  9  10

User · Answer

My solution   import collections   def flatten x       if isinstance x  collections Iterable           return  a for i in x for a in flatten i       else          return  x    A little more concise  but pretty much the same

User · Answer

I am a dumb guy so I ll give a  dumb  solution  All that recursion hurts my brain   flattened list      nested list      1  2  3    4  5    6   def flatten nested list  container       for item in nested list          if isintance item  list               flatten item  container          else              container append item    gt  gt  gt  flatten nested list  flattened list   gt  gt  gt  flattened list  1  2  3  4  5  6    I get that it s using a side effect but well that s to the best of my comprehension of recursion can go

User · Answer

I m new to python and come from a lisp background  This is what I came up with  check out the var names for lulz    def flatten lst       if lst          car  cdr lst         if isinstance car  list tuple                if cdr  return flatten car    flatten cdr              return flatten car          if cdr  return  car    flatten cdr          return  car    Seems to work  Test   flatten  1 2 3  4 5 6  7 8    1 2          returns    1  2  3  4  5  6  7  8  1  2

User · Answer

This will flatten a list or dictionary  or list of lists or dictionaries of dictionaries etc   It assumes that the values are strings and it creates a string that concatenates each item with a separator argument  If you wanted you could use the separator to split the result into a list object afterward  It uses recursion if the next value is a list or a string  Use the key argument to tell whether you want the keys or the values  set key to false  from the dictionary object    def flatten obj n obj  key True  my sep          my string          if type n obj     list          for val in n obj              my sep setter   my sep if my string       else                if type val     list or type val     dict                  my string    my sep setter   flatten obj val  key  my sep              else                  my string    my sep setter   val     elif type n obj     dict          for k  v in n obj items                my sep setter   my sep if my string       else                d val   k if key else v             if type v     list or type v     dict                  my string    my sep setter   flatten obj v  key  my sep              else                  my string    my sep setter   d val     elif type n obj     str          my sep setter   my sep if my string       else            my string    my sep setter   n obj         return my string     return my string  print flatten obj   just    a     test    to    try     right    now     or    later    today                       dictionary test    test      dictionary test two    later today     my power is 9000     my sep         yields   just  a  test  to  try  right  now  or  later  today  dictionary test  dictionary test two  my power is 9000

User · Answer

It was fun trying to create a function that could flatten irregular list in Python  but of course that is what Python is for  to make programming fun   The following generator works fairly well with some caveats   def flatten iterable       try          for item in iterable              yield from flatten item      except TypeError          yield iterable   It will flatten datatypes that you might want left alone  like bytearray  bytes  and str objects   Also  the code relies on the fact that requesting an iterator from a non-iterable raises a TypeError    gt  gt  gt  L      1  2  3    4  5    6   gt  gt  gt  def flatten iterable       try          for item in iterable              yield from flatten item      except TypeError          yield iterable    gt  gt  gt  list flatten L    1  2  3  4  5  6   gt  gt  gt      Edit   I disagree with the previous implementation  The problem is that you should not be able to flatten something that is not an iterable  It is confusing and gives the wrong impression of the argument    gt  gt  gt  list flatten 123    123   gt  gt  gt    The following generator is almost the same as the first but does not have the problem of trying to flatten a non-iterable object  It fails as one would expect when an inappropriate argument is given to it   def flatten iterable       for item in iterable          try              yield from flatten item          except TypeError              yield item   Testing the generator works fine with the list that was provided  However  the new code will raise a TypeError when a non-iterable object is given to it  Example are shown below of the new behavior    gt  gt  gt  L      1  2  3    4  5    6   gt  gt  gt  list flatten L    1  2  3  4  5  6   gt  gt  gt  list flatten 123   Traceback  most recent call last     File   lt pyshell 32 gt    line 1  in  lt module gt      list flatten 123     File   lt pyshell 27 gt    line 2  in flatten     for item in iterable  TypeError   int  object is not iterable  gt  gt  gt

User · Answer

Here s another answer that is even more interesting    import re  def Flatten TheList       a   str TheList      b  Anon   re subn r                a      c   b split       d    int x  for x in c       return d   Basically  it converts the nested list to a string  uses a regex to strip out the nested syntax  and then converts the result back to a  flattened  list

User · Answer

The think that following would probably work in python 3   def get flat iter xparent       try          r   xparent         if hasattr xx     iter                  iparent   iter xparent              if iparent    xparent                  r   map a  xparent      finally           pass     return r  irregular list    1   2   3  4    flat list   list irregular list  print flat list     1  2  3  4

User · Answer

When trying to answer such a question you really need to give the limitations of the code you propose as a solution  If it was only about performances I wouldn t mind too much  but most of the codes proposed as solution  including the accepted answer  fail to flatten any list that has a depth greater than 1000   When I say most of the codes I mean all codes that use any form of recursion  or call a standard library function that is recursive   All these codes fail because for every of the recursive call made  the  call  stack grow by one unit  and the  default  python call stack has a size of 1000    If you re not too familiar with the call stack  then maybe the following will help  otherwise you can just scroll to the Implementation    Call stack size and recursive programming  dungeon analogy   Finding the treasure and exit  Imagine you enter a huge dungeon with numbered rooms  looking for a treasure  You don t know the place but you have some indications on how to find the treasure  Each indication is a riddle  difficulty varies  but you can t predict how hard they will be   You decide to think a little bit about a strategy to save time  you make two observations     It s hard  long  to find the treasure as you ll have to solve  potentially hard  riddles to get there   Once the treasure found  returning to the entrance may be easy  you just have to use the same path in the other direction  though this needs a bit of memory to recall your path      When entering the dungeon  you notice a small notebook here  You decide to use it to write down every room you exit after solving a riddle  when entering a new room   this way you ll be able to return back to the entrance  That s a genius idea  you won t even spend a cent implementing your strategy   You enter the dungeon  solving with great success the first 1001 riddles  but here comes something you hadn t planed  you have no space left in the notebook you borrowed  You decide to abandon your quest as you prefer not having the treasure than being lost forever inside the dungeon  that looks smart indeed    Executing a recursive program  Basically  it s the exact same thing as finding the treasure  The dungeon is the computer s memory  your goal now is not to find a treasure but to compute some function  find f x  for a given x   The indications simply are sub-routines that will help you solving f x   Your strategy is the same as the call stack strategy  the notebook is the stack  the rooms are the functions  return addresses    x     over here    am    I   y   sorted x    You re about to enter a room named  sorted   note down the current room address here so you can return back  0x4004f4  that room address looks weird    Seems like you went back from your quest using the return address 0x4004f4   Let s see what you ve collected  print     join y     The problem you encountered in the dungeon will be the same here  the call stack has a finite size  here 1000  and therefore  if you enter too many functions without returning back then you ll fill the call stack and have an error that look like  Dear adventurer  I m very sorry but your notebook is full   RecursionError  maximum recursion depth exceeded  Note that you don t need recursion to fill the call stack  but it s very unlikely that a non-recursive program call 1000 functions without ever returning  It s important to also understand that once you returned from a function  the call stack is freed from the address used  hence the name  stack   return address are pushed in before entering a function and pulled out when returning   In the special case of a simple recursion  a function f that call itself once -- over and over --  you will enter f over and over until the computation is finished  until the treasure is found  and return from f until you go back to the place where you called f in the first place  The call stack will never be freed from anything until the end where it will be freed from all return addresses one after the other    How to avoid this issue   That s actually pretty simple   don t use recursion if you don t know how deep it can go   That s not always true as in some cases  Tail Call recursion can be Optimized  TCO   But in python  this is not the case  and even  well written  recursive function will not optimize stack use  There is an interesting post from Guido about this question  Tail Recursion Elimination   There is a technique that you can use to make any recursive function iterative  this technique we could call bring your own notebook  For example  in our particular case we simply are exploring a list  entering a room is equivalent to entering a sublist  the question you should ask yourself is how can I get back from a list to its parent list  The answer is not that complex  repeat the following until the stack is empty    push the current list address and index in a stack when entering a new sublist  note that a list address index is also an address  therefore we just use the exact same technique used by the call stack   every time an item is found  yield it  or add them in a list   once a list is fully explored  go back to the parent list using the stack return address  and index     Also note that this is equivalent to a DFS in a tree where some nodes are sublists A    1  2  and some are simple items  0  1  2  3  4  for L    0   1 2   3  4    The tree looks like this                       L                                  -------------------                                           0   --A--   3     4                                     1   2   The DFS traversal pre-order is  L  0  A  1  2  3  4  Remember  in order to implement an iterative DFS you also  need  a stack  The implementation I proposed before result in having the following states  for the stack and the flat list     init    stack   L  0     0     stack   L  0            flat list  0    A     stack   L  1    A  0    flat list  0    1     stack   L  1    A  0    flat list  0  1    2     stack   L  1    A  1    flat list  0  1  2    3     stack   L  2            flat list  0  1  2  3    3     stack   L  3            flat list  0  1  2  3  4  return  stack                   flat list  0  1  2  3  4    In this example  the stack maximum size is 2  because the input list  and therefore the tree  have depth 2   Implementation  For the implementation  in python you can simplify a little bit by using iterators instead of simple lists  References to the  sub iterators will be used to store sublists return addresses  instead of having both the list address and the index   This is not a big difference but I feel this is more readable  and also a bit faster    def flatten iterable       return list items from iterable    def items from iterable       cursor stack    iter iterable       while cursor stack          sub iterable   cursor stack -1          try              item   next sub iterable          except StopIteration      post-order             cursor stack pop               continue         if is list like item      pre-order             cursor stack append iter item           elif item is not None              yield item            in-order  def is list like item       return isinstance item  list    Also  notice that in is list like I have isinstance item  list   which could be changed to handle more input types  here I just wanted to have the simplest version where  iterable  is just a list  But you could also do that   def is list like item       try          iter item          return not isinstance item  str     strings are not lists  hmm          except TypeError          return False   This considers strings as  simple items  and therefore flatten iter    test    a     b   will return   test    a    b   and not   t    e    s    t    a    b    Remark that in that case  iter item  is called twice on each item  let s pretend it s an exercise for the reader to make this cleaner    Testing and remarks on other implementations  In the end  remember that you can t print a infinitely nested list L using print L  because internally it will use recursive calls to   repr    RecursionError  maximum recursion depth exceeded while getting the repr of an object   For the same reason  solutions to flatten involving str will fail with the same error message    If you need to test your solution  you can use this function to generate a simple nested list   def build deep list depth          Returns a list of the form  l  depth     depth-1  l  depth-1        with  depth  gt  1  and  l 0    0                sub list    0      for d in range 1  depth           sub list    d  sub list      return sub list   Which gives  build deep list 5       4   3   2   1   0

User · Answer

I prefer simple answers   No generators   No recursion or recursion limits   Just iteration   def flatten TheList       listIsNested   True      while listIsNested                   outer loop         keepChecking   False         Temp               for element in TheList           inner loop             if isinstance element list                   Temp extend element                  keepChecking   True             else                  Temp append element           listIsNested   keepChecking      determine if outer loop exits         TheList   Temp         return TheList   This works with two lists  an inner for loop and an outer while loop     The inner for loop iterates through the list   If it finds a list element  it  1  uses list extend   to flatten that part one level of nesting and  2  switches keepChecking to True   keepchecking is used to control the outer while loop   If the outer loop gets set to true  it triggers the inner loop for another pass     Those passes keep happening until no more nested lists are found   When a pass finally occurs where none are found  keepChecking never gets tripped to true  which means listIsNested stays false and the outer while loop exits     The flattened list is then returned   Test-run     flatten  1 2 3 4  100 200 300  1000 2000 3000        1  2  3  4  100  200  300  1000  2000  3000

User · Answer

totally hacky but I think it would work  depending on your data type   flat list   ast literal eval    s   re sub             str the list

User · Answer

Using generator functions can make your example a little easier to read and probably boost the performance  Python 2 def flatten l       for el in l          if isinstance el  collections Iterable  and not isinstance el  basestring               for sub in flatten el                   yield sub         else              yield el  I used the Iterable ABC added in 2 6  Python 3 In Python 3  the basestring is no more  but you can use a tuple of str and bytes to get the same effect there  The yield from operator returns an item from a generator one at a time  This syntax for delegating to a subgenerator was added in 3 3 from collections abc import Iterable  def flatten l       for el in l          if isinstance el  Iterable  and not isinstance el   str  bytes                yield from flatten el          else              yield el

User · Answer

From my previous answer  this function flattens most cases I can think of  I believe this works down to python 2 3   def flatten item  keepcls     keepobj          if not hasattr item     iter     or isinstance item  keepcls  or item in keepobj          yield item     else          for i in item              for j in flatten i  keepcls  keepobj    item                     yield j   Circular lists   gt  gt  gt  list flatten  1  2         3     1  2   1  2         3   3    Depth first lists   gt  gt  gt  list flatten    1  2  3    4  5    6     1  2  3  4  5  6    Nested repeated lists    gt  gt  gt  list flatten   1 2   1  1 2    1 2      1  2  1  1  2  1  2    Lists with dicts  or other objects to not flatten    gt  gt  gt  list flatten  1 2    a  1   b  2    text    keepcls  dict  str     1  2    a   1   b   2    text     Any iterables   gt  gt  gt  list flatten  x for x in  1 2  set  3  4 5  6        1  2  4  5  3  6       You may want to keep some default classes in keepcls to make calling   the function more terse

User · Answer

I modified the code of the accepted answer and added a keyword max depth to only flatten up to a specified depth  max depth 0 means  the list stays as it is  Maybe somebody can use it  def flatten l    depth 0  max depth 100        for el in l           if isinstance el  collections Iterable  and not isinstance el   str  bytes                   depth    1             if   depth  lt   max depth                  yield from flatten el    depth   depth  max depth max depth              else                  yield el               depth -  1          else               yield el  Some examples    A l      depth   5 for i in range depth       el   i     for j in range i           el    el      l append el     0   1     2       3         4       for i in range depth       print list flatten gen l  max depth i       0   1     2       3         4         0   1     2       3         4        0   1     2       3         4       0   1     2       3         4      0   1     2       3         4      B l     1  2    3  4   5  6   7   8   9     10   12   13    14   15    for i in range 6       print list flatten gen l  max depth i        1  2    3  4   5  6   7   8   9     10   12   13    14   15       1  2    3  4   5  6   7   8   9     10   12   13    14   15      1  2    3  4   5  6   7   8   9     10   12   13    14   15      1  2    3  4   5  6   7   8   9     10   12   13    14   15      1  2    3  4   5  6   7   8   9     10   12   13    14   15      1  2    3  4   5  6   7   8   9     10   12   13    14   15

[python] Flatten an irregular list of lists

Examples related to python

Examples related to list

Examples related to optimization

Examples related to nested-lists

Examples related to flatten