<div dir="ltr"><div dir="ltr">(A word of counsel to the O.P.: the cafe is a place your q is liable to get sidetracked into all sorts of places you didn't ask about. When you get to a certain level of comfort with Haskell, that can be a learning experience. Meantime you might find it better to ask on the Beginners' list, or Stackoverflow -- as @Jerzy links to.)</div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sat, 25 Mar 2023 at 11:05, David Feuer <<a href="mailto:david.feuer@gmail.com">david.feuer@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><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></div></blockquote><div><br></div><div>Thank you David. Let me take this opportunity to demonstrate why the Haskell community is so off-putting to learners ...</div><div><br></div><div>The first thing the learner will come across at Johannes' link is</div><div><br></div><div>>    <span class="gmail-annot" style="color:rgb(0,0,0)"><a href="https://hackage.haskell.org/package/base-4.18.0.0/docs/src/Data.OldList.html#sortBy" class="gmail-" style="text-decoration-line:none;border-bottom:1px solid rgb(238,232,213)"><span class="gmail-hs-identifier gmail-hs-type" style="color:rgb(95,95,175)">sortBy</span></a></span><span style="color:rgb(0,0,0)"> </span><span class="gmail-hs-glyph" style="color:rgb(220,50,47)">::</span><span style="color:rgb(0,0,0)"> </span><span class="gmail-hs-special" style="color:rgb(220,50,47)">(</span><span class="gmail-annot" style="color:rgb(0,0,0)"><a href="https://hackage.haskell.org/package/base-4.18.0.0/docs/src/Data.OldList.html#local-6989586621679636970" class="gmail-" style="text-decoration-line:none;border-bottom:1px solid rgb(238,232,213)"><span class="gmail-hs-identifier gmail-hs-type" style="color:rgb(95,95,175)">a</span></a></span><span style="color:rgb(0,0,0)"> </span><span class="gmail-hs-glyph" style="color:rgb(220,50,47)">-></span><span style="color:rgb(0,0,0)"> </span><span class="gmail-annot" style="color:rgb(0,0,0)"><a href="https://hackage.haskell.org/package/base-4.18.0.0/docs/src/Data.OldList.html#local-6989586621679636970" class="gmail-" style="text-decoration-line:none;border-bottom:1px solid rgb(238,232,213)"><span class="gmail-hs-identifier gmail-hs-type" style="color:rgb(95,95,175)">a</span></a></span><span style="color:rgb(0,0,0)"> </span><span class="gmail-hs-glyph" style="color:rgb(220,50,47)">-></span><span style="color:rgb(0,0,0)"> </span><span class="gmail-annot" style="color:rgb(0,0,0)"><a href="https://hackage.haskell.org/package/base-4.18.0.0/docs/https://hackage.haskell.org/package/ghc-prim-0.10.0/docs/src/GHC.Types.html#Ordering/GHC.Types.html#Ordering" class="gmail-" style="text-decoration-line:none;border-bottom:1px solid rgb(238,232,213)"><span class="gmail-hs-identifier gmail-hs-type" style="color:rgb(95,95,175)">Ordering</span></a></span><span class="gmail-hs-special" style="color:rgb(220,50,47)">)</span><span style="color:rgb(0,0,0)"> </span><span class="gmail-hs-glyph" style="color:rgb(220,50,47)">-></span><span style="color:rgb(0,0,0)"> </span><span class="gmail-hs-special" style="color:rgb(220,50,47)">[</span><span class="gmail-annot" style="color:rgb(0,0,0)"><a href="https://hackage.haskell.org/package/base-4.18.0.0/docs/src/Data.OldList.html#local-6989586621679636970" class="gmail-" style="text-decoration-line:none;border-bottom:1px solid rgb(238,232,213)"><span class="gmail-hs-identifier gmail-hs-type" style="color:rgb(95,95,175)">a</span></a></span><span class="gmail-hs-special" style="color:rgb(220,50,47)">]</span><span style="color:rgb(0,0,0)"> </span><span class="gmail-hs-glyph" style="color:rgb(220,50,47)">-></span><span style="color:rgb(0,0,0)"> </span><span class="gmail-hs-special" style="color:rgb(220,50,47)">[</span><span class="gmail-annot" style="color:rgb(0,0,0)"><a href="https://hackage.haskell.org/package/base-4.18.0.0/docs/src/Data.OldList.html#local-6989586621679636970" class="gmail-" style="text-decoration-line:none;border-bottom:1px solid rgb(238,232,213)"><span class="gmail-hs-identifier gmail-hs-type" style="color:rgb(95,95,175)">a</span></a></span><span class="gmail-hs-special" style="color:rgb(220,50,47)">]</span></div><div><span class="gmail-hs-special" style="color:rgb(220,50,47)"><br></span></div><div>So now they have to find out about `Ordering` and generic compare functions.<br></div><div><br></div><div>The next thing they might know is that sorting can't emit anything until it's read the whole input -- just in case the least element is also the last. So the gentle work @Viktor's answer did in extolling the benefits of laziness is undone.</div><div><br></div><div>Now the O.P.'s concern was "<span style="color:rgb(0,0,0);white-space:pre-wrap">constantly building and breaking apart pairs</span>". This is a rather naieve q, showing over-much procedural thinking IMO; but the way to allay those fears is exactly _not_ what's going on inside `sort`.</div><div><br></div><div>* `ascending` is using a short-circuited form of `append` -- famous for being inefficient.</div><div>* `descending` is using a short-circuited form of `reverse` -- also famous for being inefficient.</div><div><br></div><div>Now the short-circuiting allays some of those inefficiencies (maybe, for a smart compiler); but at first reading the code is doing far more "building and breaking apart".</div><div><br></div><div>So a) Johannes' post hasn't answered the sub-text of the O.P.; b) it has sent the learner on a wild goose chase.</div><div><br></div><div>Now, I don't know if this style of response is typical from Haskell instructors. It is certainly not the warm and sympathetic welcome I experienced when learning Haskell 12~15 years ago (before there was StackOverflow). So if this is what @DavidF means by the "educational context" for Haskell, I as a learner would have been inclined to abandon Haskell as soon as my course allowed it.</div><div><br></div><div>I can only take it that "an educational context" means for those on track to a PhD in advanced type theory and convoluted data structuring; and exclude others from the ivory tower at the earliest opportunity.</div><div><br></div><div>AntC</div><div><br></div><div> </div></div></div>