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

JS Irick hundredpercentjuice at gmail.com
Fri Feb 19 11:39:25 EST 2016

```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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/chicago/attachments/20160219/17c56d80/attachment.html>
```