<p>Well it&#39;s possible to code this by passing over the list only once, the question is, is it possible consicely using builtin haskell higher order functions.</p>
<p>In my case the list is very short so it&#39;s really an academic question.</p>
<div class="gmail_quote">On 18 Nov 2012 10:02, &quot;KC&quot; &lt;<a href="mailto:kc1956@gmail.com">kc1956@gmail.com</a>&gt; wrote:<br type="attribution"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Lists are good if they are short; otherwise, lists are good if you are<br>
only traversing them from head to tail or decapitating them.<br>
<br>
You want a more complex data structure.<br>
<br>
<br>
On Sat, Nov 17, 2012 at 11:51 PM, Emmanuel Touzery &lt;<a href="mailto:etouzery@gmail.com">etouzery@gmail.com</a>&gt; wrote:<br>
&gt; well for isSorted, better use the implementation from Data.List.Ordered.<br>
&gt; That part was poor in performance for sure, but it wasn&#39;t my main focus, I<br>
&gt; was more interested in the rest.<br>
&gt;<br>
&gt;<br>
&gt; On Sun, Nov 18, 2012 at 8:45 AM, Emmanuel Touzery &lt;<a href="mailto:etouzery@gmail.com">etouzery@gmail.com</a>&gt;<br>
&gt; wrote:<br>
&gt;&gt;<br>
&gt;&gt; Hello,<br>
&gt;&gt;<br>
&gt;&gt;  i wonder what would be the idiomatic way to achieve that algorithm in<br>
&gt;&gt; haskell:<br>
&gt;&gt;<br>
&gt;&gt; [1,4,56,450,23,46,52] =&gt; [1,4,56,450]<br>
&gt;&gt; [1,4,56,450,23,46,52] =&gt; [23,46,52]<br>
&gt;&gt;<br>
&gt;&gt;  in other words split the list when one element gets smaller than the<br>
&gt;&gt; previous one. Tge rest of the time the list is sorted. There would be only<br>
&gt;&gt; two lists, not N. I always need the first or second sublist, I don&#39;t need<br>
&gt;&gt; both at once. But of course a more complete algorithm handling the N case<br>
&gt;&gt; and/or returning both sublists would be good.<br>
&gt;&gt;<br>
&gt;&gt;  i could code this by hand, but i&#39;m trying to use as much as possible<br>
&gt;&gt; builtin higher-order functions. However in this case so far I&#39;ve only come<br>
&gt;&gt; up with this:<br>
&gt;&gt;<br>
&gt;&gt; import Data.List<br>
&gt;&gt;<br>
&gt;&gt; isSorted :: Ord a =&gt; [a] -&gt; Bool<br>
&gt;&gt; isSorted l = (sort l) == l<br>
&gt;&gt;<br>
&gt;&gt; secondPart :: Ord a =&gt; [a] -&gt; [a]<br>
&gt;&gt; secondPart l = head $ filter isSorted (tails l)<br>
&gt;&gt;<br>
&gt;&gt; firstPart :: Ord a =&gt; [a] -&gt; [a]<br>
&gt;&gt; firstPart l = last $ filter isSorted (inits l)<br>
&gt;&gt;<br>
&gt;&gt;  It is concise alright, but it seems contrived and also in terms of<br>
&gt;&gt; performance I don&#39;t think it&#39;s OK (for small lists sure but for big lists?).<br>
&gt;&gt;<br>
&gt;&gt;  Anyway, somehow I think something as simple as this must be doable very<br>
&gt;&gt; concisely and with optimal performance using only builtin higher-order<br>
&gt;&gt; functions. Any idea?<br>
&gt;&gt;<br>
&gt;&gt;  Thanks!<br>
&gt;&gt;<br>
&gt;&gt; Emmanuel<br>
&gt;<br>
&gt;<br>
&gt;<br>
&gt; _______________________________________________<br>
&gt; Beginners mailing list<br>
&gt; <a href="mailto:Beginners@haskell.org">Beginners@haskell.org</a><br>
&gt; <a href="http://www.haskell.org/mailman/listinfo/beginners" target="_blank">http://www.haskell.org/mailman/listinfo/beginners</a><br>
&gt;<br>
<br>
<br>
<br>
--<br>
--<br>
Regards,<br>
KC<br>
</blockquote></div>