<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Thu, Jul 17, 2014 at 8:54 PM, Richard A. O'Keefe <span dir="ltr"><<a href="mailto:ok@cs.otago.ac.nz" target="_blank">ok@cs.otago.ac.nz</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="">> But the original haskell functions last and init are O(n).<br>
<br>
</div>Haskell lists are singly linked lists.  Even by going to<br>
assembly code, you could not make these operations O(1)<br>
without *using a different data structure*.<br>
<div class=""></div></blockquote></div><br>At this point, you may be wondering why Haskell uses singly linked lists so much, when one might think an array/vector type might be more generally useful.</div><div class="gmail_extra">
<br></div><div class="gmail_extra">The thing about functional languages, and in particular pure functional languages such as Haskell, is that you don't generally have things like looping constructs; instead, you represent your data in a form which implies such a construct. In particular, when you might use a for/foreach loop in other languages, in a functional language you use a singly linked list and a map or fold over the list. (Some object-oriented languages do this as well; consider the "each" method in Smalltalk or Ruby.)</div>
<div class="gmail_extra"><br></div><div class="gmail_extra">In a pure functional language like Haskell, this can lead to optimizations you would not get from an explicit foreach loop: since values are immutable and can be generated lazily, a compiler can more easily recognize that it doesn't need to generate or maintain a list at all but just consume values as they are generated. Languages that use foreach loops often can only do this optimization in specific cases: for example, in Perl a foreach loop on a constant numeric range is optimized this way, but not others; in Ruby, it's much harder to do this at all because the "each" method needs to be resolved to a list object; and commercial Smalltalk implementations generally have quite a lot of behind the scenes intelligence to try to recognize and optimize these kinds of cases without falling into the same trap as e.g. Ruby.<br>
<div><br></div>-- <br><div dir="ltr"><div>brandon s allbery kf8nh                               sine nomine associates</div><div><a href="mailto:allbery.b@gmail.com" target="_blank">allbery.b@gmail.com</a>                                  <a href="mailto:ballbery@sinenomine.net" target="_blank">ballbery@sinenomine.net</a></div>
<div>unix, openafs, kerberos, infrastructure, xmonad        <a href="http://sinenomine.net" target="_blank">http://sinenomine.net</a></div></div>
</div></div>