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... 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.... 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.