<div dir="ltr">That's still potentially a lot of list copying though, isn't it?<br></div><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Feb 19, 2016 at 9:40 AM, Aaron Elmquist <span dir="ltr"><<a href="mailto:elmq0022@umn.edu" target="_blank">elmq0022@umn.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Brad, that's a really cool approach and very readable. Thanks!<br></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Feb 19, 2016 at 9:34 AM, Brad Martsberger <span dir="ltr"><<a href="mailto:bradley.marts@gmail.com" target="_blank">bradley.marts@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>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).<br><br></div>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).<br><br>def press(lst):<br> """<br> Flattens nested lists one level<br><br> Returns a tuple (new_list, changed) where changed is a boolean indicating<br> whether new_list is different from lst.<br> """<br> changed = False<span><br> new_list = []<br> for element in lst:<br> if isinstance(element, list):<br></span> new_list.extend(element)<br> changed = True<br> else:<br> new_list.append(element)<br><br> return new_list, changed<br><br><br>def flatten(lst):<br> """<br> Fully flattens nested lists into a list with no sublists<br> """<br> new_list = lst<br> changed = True<br> while changed:<br> new_list, changed = press(new_list)<br> return new_list<br></div><div><div><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Feb 19, 2016 at 6:59 AM, Aaron Elmquist <span dir="ltr"><<a href="mailto:elmq0022@umn.edu" target="_blank">elmq0022@umn.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>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. </div><div><br></div><div>def flatten_big_list(lst):<br> stack = []<br> while(lst):<br> top = lst.pop(0)<br> while(isinstance(top,list)):<br> temp = top.pop(0)<br> if top:<br> lst.insert(0,top)<br> top = temp<br> stack.append(top)<br> return stack</div><div><br></div><div><br>def flatten_big_list_gen(lst):<br> while(lst):<br> top = lst.pop(0)<br> while(isinstance(top,list)):<br> temp = top.pop(0)<br> if top:<br> lst.insert(0,top)<br> top = temp<br> yield top</div><div><br></div><div><br></div><div>print(flatten_big_list([1, [2, [3, [4, 5]]]]))<br>print(list(flatten_big_list_gen([1, [2, [3, [4, 5]]]])))</div><div><br></div><div>Feedback is always welcome. </div><div><br></div></div><div><div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Feb 18, 2016 at 9:29 PM, Mark Graves <span dir="ltr"><<a href="mailto:mgraves87@gmail.com" target="_blank">mgraves87@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Doug,<div><br></div><div>Also, I didn't see your question get answered.</div><div><br></div><div>"The" answer to why is recursion expensive vs iteration is stack traces. See Guido's answer <a href="https://t.yesware.com/tt/6640a48a14dbdef70b47105ac6b72156559fc5a6/5ba2375237a9fdc8efa681b19014981f/d6c3025efb0710ebe9f6fa425f843d2c/plus.google.com/115212051037621986145/posts/HajXHPGN752" target="_blank">here</a> or try it yourself as mentioned <a href="http://t.yesware.com/tt/6640a48a14dbdef70b47105ac6b72156559fc5a6/5ba2375237a9fdc8efa681b19014981f/dda1509570b2b5d9d162e6293a1b3f07/stackoverflow.com/questions/22893139/why-is-a-function-method-call-in-python-expensive" target="_blank">here</a>.</div><div><br></div><div>Recursion means creating more functions / stack traces.</div><img style="border:0;width:0;min-height:0;overflow:hidden" src="https://t.yesware.com/t/6640a48a14dbdef70b47105ac6b72156559fc5a6/5ba2375237a9fdc8efa681b19014981f/spacer.gif" height="0" width="0"><img style="border:0;width:0;min-height:0;overflow:hidden" src="http://t.yesware.com/t/6640a48a14dbdef70b47105ac6b72156559fc5a6/5ba2375237a9fdc8efa681b19014981f/spacer.gif" height="0" width="0"><font face="yw-6640a48a14dbdef70b47105ac6b72156559fc5a6-5ba2375237a9fdc8efa681b19014981f--tol"></font></div><div><div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Feb 18, 2016 at 7:55 PM, Adam Forsyth <span dir="ltr"><<a href="mailto:adam@adamforsyth.net" target="_blank">adam@adamforsyth.net</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><p dir="ltr">Phil,</p>
<p dir="ltr">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. </p><span><font color="#888888">
<p dir="ltr">Adam </p>
</font></span><div class="gmail_quote"><div><div>On Feb 18, 2016 19:22, "Robare, Phillip (TEKSystems)" <<a href="mailto:proba@allstate.com" target="_blank">proba@allstate.com</a>> wrote:<br type="attribution"></div></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div>
<div vlink="purple" link="blue" lang="EN-US">
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">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 data structure that I got from loading a JSON string.<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-family:"Calibri",sans-serif;color:#1f497d">Phil Robare<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d"><u></u> <u></u></span></p>
<div>
<div>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<div>
<div>
<div>
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><snip/><u></u><u></u></span></b></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><u></u> <u></u></span></p>
<div>
<p class="MsoNormal">On Thu, Feb 18, 2016 at 1:43 PM, Aaron Elmquist <<a href="mailto:elmq0022@umn.edu" target="_blank">elmq0022@umn.edu</a>> wrote:<u></u><u></u></p>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<div>
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt">Douglas, <u></u><u></u></p>
</div>
<p class="MsoNormal">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.<u></u><u></u></p>
<div>
<div>
<p class="MsoNormal" style="margin-right:0in;margin-bottom:12.0pt;margin-left:23.1pt">
<br>
def flatten(lst):<br>
for item1 in lst:<br>
if hasattr(item1, '__iter__'):<br>
for item2 in flatten(item1):<br>
yield item2<br>
else:<br>
yield item1<br>
<br>
print([x for x in flatten([1, [2,3,[4,5,6,[7,8,9]]]]) if x%2 == 1])<br>
<br>
y = flatten([1, [2,3,[4,5,6,[7,8,9]]]])<br>
<br>
print(next(y))<br>
print(next(y))<br>
print(next(y))<br>
.<br>
.<br>
.<br>
<snip/><u></u><u></u></p>
</div>
</div>
</div>
<div>
<div>
<div>
<div>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<div>
<div>
<div>
<div>
<p class="MsoNormal">On Wed, Feb 17, 2016 at 9:48 PM, DiPierro, Massimo <<a href="mailto:MDiPierro@cs.depaul.edu" target="_blank">MDiPierro@cs.depaul.edu</a>> wrote:<u></u><u></u></p>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<p class="MsoNormal" style="margin-left:46.2pt">here is a one liner:<br>
<br>
def flatten(x):<br>
return [z for y in x for z in flatten(y)] if isinstance(x,list) else [x]<br>
<br>
<br>
<u></u><u></u></p>
</blockquote>
</div>
</div>
</div>
</div>
</blockquote>
</div>
</div>
</div>
</div>
</blockquote>
</div>
</div>
</div>
</div>
</blockquote>
</div>
</div>
</div>
</div>
<br></div></div><span>_______________________________________________<br>
Chicago mailing list<br>
<a href="mailto:Chicago@python.org" target="_blank">Chicago@python.org</a><br>
<a href="https://mail.python.org/mailman/listinfo/chicago" rel="noreferrer" target="_blank">https://mail.python.org/mailman/listinfo/chicago</a><br>
<br></span></blockquote></div>
<br>_______________________________________________<br>
Chicago mailing list<br>
<a href="mailto:Chicago@python.org" target="_blank">Chicago@python.org</a><br>
<a href="https://mail.python.org/mailman/listinfo/chicago" rel="noreferrer" target="_blank">https://mail.python.org/mailman/listinfo/chicago</a><br>
<br></blockquote></div><br></div>
</div></div><br>_______________________________________________<br>
Chicago mailing list<br>
<a href="mailto:Chicago@python.org" target="_blank">Chicago@python.org</a><br>
<a href="https://mail.python.org/mailman/listinfo/chicago" rel="noreferrer" target="_blank">https://mail.python.org/mailman/listinfo/chicago</a><br>
<br></blockquote></div><br></div>
</div></div><br>_______________________________________________<br>
Chicago mailing list<br>
<a href="mailto:Chicago@python.org" target="_blank">Chicago@python.org</a><br>
<a href="https://mail.python.org/mailman/listinfo/chicago" rel="noreferrer" target="_blank">https://mail.python.org/mailman/listinfo/chicago</a><br>
<br></blockquote></div><br></div>
</div></div><br>_______________________________________________<br>
Chicago mailing list<br>
<a href="mailto:Chicago@python.org" target="_blank">Chicago@python.org</a><br>
<a href="https://mail.python.org/mailman/listinfo/chicago" rel="noreferrer" target="_blank">https://mail.python.org/mailman/listinfo/chicago</a><br>
<br></blockquote></div><br></div>
</div></div></blockquote></div><br></div>