[Haskell-cafe] Basic list exercise

[Johannes Waldmann]

Dear Anthony, and Cafe,


 > ... get sidetracked into all sorts of places you didn't ask about

that's the semantics of "-cafe"? I think we agree.
In that spirit, allow me to continue with some more tangential remarks.


 > Haskell community is so off-putting to learners ...

I think a language (or other tool) is best for learning
if it shows the concepts (that are the subject of the study)
most clearly, instead of ignoring, hiding, or sugarcoating them.

 > So now they have to find out about `Ordering`
 > and generic compare functions.

Yes - that's algebraic data types, higher order functions,
generic polymorphism. You don't get Haskell without that.
(By definition: functional, strongly typed)

Now we might argue whether that's really the concepts
that are needed to answer the original question of this thread.
In a way, yes - it is about runs in a list,
and a run is defined with respect to an order,
so it feels natural that the order is an input of the problem.


In another way, no (I think that is your point) -
it was about efficient implementation, and that could as well
be discussed with a monomorphic type and some fixed order.

I found the original question interesting, and I thought
that authors of the standard library must have asked
the same thing, and the resulting library source code seems
to confirm what the OP conjectured: there is no easy way to get
ascending runs. How bad is it? I made this experiment:

import Criterion.Main
import qualified Data.List as L

main = do
   let up = [1 .. 10^7 :: Int]
       down = reverse up
   print (sum  up, sum down)
   defaultMain
     [ bench "length up"   $ nf length up
     , bench "length down" $ nf length down
     , bench "sort up"   $ nf L.sort up
     , bench "sort down" $ nf L.sort down
     ]

and it shows that sorting an ascending list
(which just builds the one ascending run)
takes three times the work of just traversing it,
but sorting a descending list (building
one descending run) only two times.


Now, I am not too much worried about efficiency
of these particular functions (ascending/descending/sort)
because I firmly believe that: 1. using a list as a container
is wrong (did you mean Data.Sequence?) 2. sorting lists
is more wrong  (use Data.Set from the start) 3. writing a sort
function yourself is most wrong, - of course with the caveat:
0. unless you get this as homework. Then you should absolutely do it
(and then learn from it, and then forget the concrete instance).


What worries me here much more deeply is
https://github.com/haskell/criterion/issues/273
yes, that's another thing the OP did not ask about.


- J.W.