# [Chicago] Resolving lists within lists within lists within .....

Aaron Elmquist elmq0022 at umn.edu
Fri Feb 19 11:42:40 EST 2016

```Okay, that made my jaw drop.

On Fri, Feb 19, 2016 at 10:39 AM, JS Irick <hundredpercentjuice at gmail.com>
wrote:

> I think we can agree that there is only one true solution:
>
> >>> my_list
>
> [1, 2, [1, 2, 3, [1, 2, 3, 4], 5], 4, 5]
>
>
> [1, 2, 1, 2, 3, 1, 2, 3, 4, 5, 4, 5]
>
> On Fri, Feb 19, 2016 at 10:05 AM, Aaron Elmquist <elmq0022 at umn.edu> wrote:
>
>> That's still potentially a lot of list copying though, isn't it?
>>
>> On Fri, Feb 19, 2016 at 9:40 AM, Aaron Elmquist <elmq0022 at umn.edu> wrote:
>>
>>>
>>> On Fri, Feb 19, 2016 at 9:34 AM, Brad Martsberger <
>>>
>>>> Aaron, Thanks for your example. One thing to point out is that popping
>>>> from the front of a list is expensive because the entire list has to be
>>>> copied. Some options are to flatten the list from the back (popping off the
>>>> end of the list is cheap), or copying the list into a deque (from
>>>> collections import deque).
>>>>
>>>> Here is another example of a non recursive version of flatten. It's not
>>>> nearly as elegant as the recursive version. It's longer than Aaron's
>>>> iterative version, but avoids hand manipulating the iteration over the
>>>> lists (no popping or inserting).
>>>>
>>>> def press(lst):
>>>>     """
>>>>     Flattens nested lists one level
>>>>
>>>>     Returns a tuple (new_list, changed) where changed is a boolean
>>>> indicating
>>>>     whether new_list is different from lst.
>>>>     """
>>>>     changed = False
>>>>     new_list = []
>>>>     for element in lst:
>>>>         if isinstance(element, list):
>>>>             new_list.extend(element)
>>>>             changed = True
>>>>         else:
>>>>             new_list.append(element)
>>>>
>>>>     return new_list, changed
>>>>
>>>>
>>>> def flatten(lst):
>>>>     """
>>>>     Fully flattens nested lists into a list with no sublists
>>>>     """
>>>>     new_list = lst
>>>>     changed = True
>>>>     while changed:
>>>>         new_list, changed = press(new_list)
>>>>     return new_list
>>>>
>>>> On Fri, Feb 19, 2016 at 6:59 AM, Aaron Elmquist <elmq0022 at umn.edu>
>>>> wrote:
>>>>
>>>>> Here's one last approach that is stack based.  There is some clean up
>>>>> to do here for sure (I'm mutating the original list for one), but the point
>>>>> is to illustrate an approach that is not recursive.
>>>>>
>>>>> def flatten_big_list(lst):
>>>>>     stack = []
>>>>>     while(lst):
>>>>>         top = lst.pop(0)
>>>>>         while(isinstance(top,list)):
>>>>>             temp = top.pop(0)
>>>>>             if top:
>>>>>                 lst.insert(0,top)
>>>>>             top = temp
>>>>>         stack.append(top)
>>>>>     return stack
>>>>>
>>>>>
>>>>> def flatten_big_list_gen(lst):
>>>>>     while(lst):
>>>>>         top = lst.pop(0)
>>>>>         while(isinstance(top,list)):
>>>>>             temp = top.pop(0)
>>>>>             if top:
>>>>>                 lst.insert(0,top)
>>>>>             top = temp
>>>>>         yield top
>>>>>
>>>>>
>>>>> print(flatten_big_list([1, [2, [3, [4, 5]]]]))
>>>>> print(list(flatten_big_list_gen([1, [2, [3, [4, 5]]]])))
>>>>>
>>>>> Feedback is always welcome.
>>>>>
>>>>>
>>>>> On Thu, Feb 18, 2016 at 9:29 PM, Mark Graves <mgraves87 at gmail.com>
>>>>> wrote:
>>>>>
>>>>>> Doug,
>>>>>>
>>>>>>
>>>>>> "The" answer to why is recursion expensive vs iteration is stack
>>>>>> traces.  See Guido's answer here
>>>>>> try it yourself as mentioned here
>>>>>> <http://t.yesware.com/tt/6640a48a14dbdef70b47105ac6b72156559fc5a6/5ba2375237a9fdc8efa681b19014981f/dda1509570b2b5d9d162e6293a1b3f07/stackoverflow.com/questions/22893139/why-is-a-function-method-call-in-python-expensive>
>>>>>> .
>>>>>>
>>>>>> Recursion means creating more functions / stack traces.
>>>>>>
>>>>>> wrote:
>>>>>>
>>>>>>> Phil,
>>>>>>>
>>>>>>> That's generally true, but one small correction. Aaron's solution
>>>>>>> won't actually won't flatten strings, as they don't have "__iter__"
>>>>>>> methods. They implement iteration because they take sequential numeric
>>>>>>> indexes starting at 0, and raise an IndexError after the index passed is
>>>>>>> too large.
>>>>>>>
>>>>>>> On Feb 18, 2016 19:22, "Robare, Phillip (TEKSystems)" <
>>>>>>> proba at allstate.com> wrote:
>>>>>>>
>>>>>>>> Aaron, unlike Massimo’s elegant one-liner you don’t check that what
>>>>>>>> you are iterating over is a list.  Since Python will happily iterate over
>>>>>>>> strings, dictionaries, and much more you quickly get into problems when the
>>>>>>>> list includes more types than lists and numbers.  I recount this from
>>>>>>>> experience when I tried to throw together a flatten routine and pass it a
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>> Phil Robare
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>> *<snip/>*
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>> On Thu, Feb 18, 2016 at 1:43 PM, Aaron Elmquist <elmq0022 at umn.edu>
>>>>>>>> wrote:
>>>>>>>>
>>>>>>>> Douglas,
>>>>>>>>
>>>>>>>> Here's one more version for you and the rest of the list. It's
>>>>>>>> based on Brad's code.  I will let you think about why this version might be
>>>>>>>> better or worse.  Also, recursion is great.  It's just too bad it's not one
>>>>>>>> of python's strong points.
>>>>>>>>
>>>>>>>>
>>>>>>>> def flatten(lst):
>>>>>>>>     for item1 in lst:
>>>>>>>>         if hasattr(item1, '__iter__'):
>>>>>>>>             for item2 in flatten(item1):
>>>>>>>>                 yield item2
>>>>>>>>         else:
>>>>>>>>             yield item1
>>>>>>>>
>>>>>>>> print([x for x in flatten([1, [2,3,[4,5,6,[7,8,9]]]]) if x%2 == 1])
>>>>>>>>
>>>>>>>> y = flatten([1, [2,3,[4,5,6,[7,8,9]]]])
>>>>>>>>
>>>>>>>> print(next(y))
>>>>>>>> print(next(y))
>>>>>>>> print(next(y))
>>>>>>>> .
>>>>>>>> .
>>>>>>>> .
>>>>>>>> <snip/>
>>>>>>>>
>>>>>>>> On Wed, Feb 17, 2016 at 9:48 PM, DiPierro, Massimo <
>>>>>>>> MDiPierro at cs.depaul.edu> wrote:
>>>>>>>>
>>>>>>>> here is a one liner:
>>>>>>>>
>>>>>>>> def flatten(x):
>>>>>>>>     return [z for y in x for z in flatten(y)] if isinstance(x,list)
>>>>>>>> else [x]
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>> _______________________________________________
>>>>>>>> Chicago mailing list
>>>>>>>> Chicago at python.org
>>>>>>>> https://mail.python.org/mailman/listinfo/chicago
>>>>>>>>
>>>>>>>>
>>>>>>> _______________________________________________
>>>>>>> Chicago mailing list
>>>>>>> Chicago at python.org
>>>>>>> https://mail.python.org/mailman/listinfo/chicago
>>>>>>>
>>>>>>>
>>>>>>
>>>>>> _______________________________________________
>>>>>> Chicago mailing list
>>>>>> Chicago at python.org
>>>>>> https://mail.python.org/mailman/listinfo/chicago
>>>>>>
>>>>>>
>>>>>
>>>>> _______________________________________________
>>>>> Chicago mailing list
>>>>> Chicago at python.org
>>>>> https://mail.python.org/mailman/listinfo/chicago
>>>>>
>>>>>
>>>>
>>>> _______________________________________________
>>>> Chicago mailing list
>>>> Chicago at python.org
>>>> https://mail.python.org/mailman/listinfo/chicago
>>>>
>>>>
>>>
>>
>> _______________________________________________
>> Chicago mailing list
>> Chicago at python.org
>> https://mail.python.org/mailman/listinfo/chicago
>>
>>
>
>
> --
> ====
> JS Irick
> 312-307-8904
> Consultant: truqua.com
> Coach: atlascrossfit.com
> Programmer: juicetux.com
>
> _______________________________________________
> Chicago mailing list
> Chicago at python.org
> https://mail.python.org/mailman/listinfo/chicago
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/chicago/attachments/20160219/e4f4aa5b/attachment.html>
```