<div style="font-family:arial,sans-serif;font-size:13px"><div>import Control.Applicative</div><div><br></div><div>breakup :: Ord a =&gt; [a] -&gt; ([a],[a])</div><div>breakup [] = ([],[])</div><div>breakup xs@(x:_) = unpairs . breakWhenLess . pairs $ x:xs</div>

<div>    where pairs = zip &lt;$&gt; tail &lt;*&gt; id</div><div>          unpairs (xs,ys) = (fst &lt;$&gt; xs, fst &lt;$&gt; ys) </div><div>          breakWhenLess = break (uncurry (&lt;))</div></div><div style="font-family:arial,sans-serif;font-size:13px">

        </div><div style="font-family:arial,sans-serif;font-size:13px">Trick is to duplicate the first element so it doesn&#39;t get &#39;lost&#39; by the tail zip. Applicatives not strictly necessary, but I like them.</div>

<div style="font-family:arial,sans-serif;font-size:13px"><br></div><div style="font-family:arial,sans-serif;font-size:13px">Peter</div><div class="gmail_extra"><br><br><div class="gmail_quote">On 18 November 2012 10:06, Emmanuel Touzery <span dir="ltr">&lt;<a href="mailto:etouzery@gmail.com" target="_blank">etouzery@gmail.com</a>&gt;</span> wrote:<br>

<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><p>That is EXACTLY the kind of answer i was hoping for!<br>
Great implementation, I&#39;ll be sure to reuse that trick of zipping with the tail of the list.. really really good.</p>
<p>I&#39;m relieved it&#39;s not trivial (for me) to write since i could not come up with it, and happy i understand it :-)</p>
<p>Intuitively it&#39;s more expensive than what an imperative language would do (new list creations, going several times over the list -zip, spam, map - still O(n) though).</p>
<p>If it was in your project you&#39;d use that, or would you use a more &quot;straightforward&quot; implementation and you came up with this one just because i asked explicitely for such a way?</p><div class="HOEnZb"><div class="h5">


<div class="gmail_quote">On 18 Nov 2012 10:47, &quot;Tobias Brandt&quot; &lt;<a href="mailto:tob.brandt@googlemail.com" target="_blank">tob.brandt@googlemail.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">


Here is a possible solution:<div><br></div><div>import Data.List</div><div><br></div><div>split xs = getSnds $ span (uncurry (&lt;)) $ zip xs (tail xs)</div><div>    where getSnds (as, bs) = (map snd as, map snd bs)</div>


<div>
<br></div><div>firstPart xs = fst $ split xs</div><div><br></div><div>sndPart xs = snd $ split xs</div><div><br></div><div>This is a one pass algortihm, it works for infinite lists.<br><br><div class="gmail_quote">On 18 November 2012 08:45, Emmanuel Touzery <span dir="ltr">&lt;<a href="mailto:etouzery@gmail.com" target="_blank">etouzery@gmail.com</a>&gt;</span> wrote:<br>



<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hello,<br><br> i wonder what would be the idiomatic way to achieve that algorithm in haskell:<br><br>[1,4,56,450,23,46,52] =&gt; [1,4,56,450]<br>



[1,4,56,450,23,46,52] =&gt; [23,46,52]<br><br> in other words split the list when one element gets smaller than the previous one. Tge rest of the time the list is sorted. There would be only two lists, not N. I always need the first or second sublist, I don&#39;t need both at once. But of course a more complete algorithm handling the N case and/or returning both sublists would be good.<br>




<br> i could code this by hand, but i&#39;m trying to use as much as possible builtin higher-order functions. However in this case so far I&#39;ve only come up with this:<br><br>import Data.List<br><br>isSorted :: Ord a =&gt; [a] -&gt; Bool<br>




isSorted l = (sort l) == l<br><br>secondPart :: Ord a =&gt; [a] -&gt; [a]<br>secondPart l = head $ filter isSorted (tails l)<br><br>firstPart :: Ord a =&gt; [a] -&gt; [a]<br>firstPart l = last $ filter isSorted (inits l)<br>




<br> It is concise alright, but it seems contrived and also in terms of performance I don&#39;t think it&#39;s OK (for small lists sure but for big lists?).<br><br> Anyway, somehow I think something as simple as this must be doable very concisely and with optimal performance using only builtin higher-order functions. Any idea?<br>




<br> Thanks!<span><font color="#888888"><br><br>Emmanuel<br>
</font></span><br>_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/beginners" target="_blank">http://www.haskell.org/mailman/listinfo/beginners</a><br>
<br></blockquote></div><br></div>
</blockquote></div>
</div></div><br>_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org">Beginners@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/beginners" target="_blank">http://www.haskell.org/mailman/listinfo/beginners</a><br>
<br></blockquote></div><br></div>