[Haskell-cafe] Basic list exercise

[Johannes Waldmann]

 > can we do better than this?

Does the implementation in Data.List do better?

https://hackage.haskell.org/package/base-4.18.0.0/docs/src/Data.OldList.html#sort

note that 'ascending' does some trickery there -
perhaps exactly to solve the problem you describe?

Since this is about "exercise" - I would expect my students
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.


NB: 'descending' is different here, and that's no surprise
since lists are asymmetric. We do have a symmetric (and strict) 
implementation of sequences - how do we sort these?

https://hackage.haskell.org/package/containers-0.6.7/docs/src/Data.Sequence.Internal.Sorting.html#sortBy

That's not exactly an advertisement for functional programming,
as it has "state" written all over the place?
But it makes for a nice exercise reading the types.

I needed some time to understand that the mouse-over block
for an identifier contains _two_ types:
the instantiated one (for the use site)
and, below that, the general one (from the definition).


- J.W.