<div dir="auto"><div>The correctness argument he was referring to was about understanding code in an educational context. The relevance is that Data.List.sort breaks up the input list into maximal "runs" of ascending or descending elements, to take advantage of any pre-existing organization. It then merges up runs rather than individual elements.</div><div dir="auto"><br><div class="gmail_quote" dir="auto"><div dir="ltr" class="gmail_attr">On Fri, Mar 24, 2023, 5:12 PM Anthony Clayden <<a href="mailto:anthony.d.clayden@gmail.com">anthony.d.clayden@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><pre style="white-space:pre-wrap;color:rgb(0,0,0)">><i> On 24 Mar 2023, at 18:44, Johannes Waldmann <<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" target="_blank" rel="noreferrer">johannes.waldmann at htwk-leipzig.de</a>> wrote:

</i>><i> 

</i>><i> ...

> Does the implementation in Data.List do better?

</i>><i> </i></pre><pre style="white-space:pre-wrap;color:rgb(0,0,0)"><br></pre><pre style="white-space:pre-wrap;color:rgb(0,0,0)">Data.List's sort is doing a different thing. So I'm not seeing the relevance. Specifically, sort doesn't pay any attention to the incoming list's ordering.</pre><pre style="white-space:pre-wrap;color:rgb(0,0,0)"><br></pre><pre style="white-space:pre-wrap;color:rgb(0,0,0)"><pre style="white-space:pre-wrap">><i> Since this is about "exercise" - I would expect my students

</i>><i> to find that code, so perhaps I'd point them to it right away,

> and give the task to "understand it" (= argue that it is correct).

> Arguing about cost seems harder.

</i>><i> </i></pre>

This (ex-)student would wonder why you'd sent me to that code. (Perhaps the lesson is: first read the question.)</pre><pre style="white-space:pre-wrap;color:rgb(0,0,0)">Why does the correctness (or otherwise) of a sort bear any relation to preserving list sequence and chopping up a list into ascending sublists?</pre><pre style="white-space:pre-wrap;color:rgb(0,0,0)"><br></pre><pre style="white-space:pre-wrap;color:rgb(0,0,0)">AntC</pre></div>

_______________________________________________<br>

Haskell-Cafe mailing list<br>

To (un)subscribe, modify options or view archives go to:<br>

<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>

Only members subscribed via the mailman list are allowed to post.</blockquote></div></div></div>