Request: Add sortOn to Data.Sequence

[Alan Isaac]

REQUEST
-------

The request is to add `sortOn` to Data.Sequence.
`sortOn f` would be equivalent to `sortBy . comparing f`,
but would offer a performance advantage by using a Schwartzian
transform to only evaluate `f` once for each element
in the input sequence.


BACKGROUND
----------

Adding `sortOn` to `Data.List` was proposed at least as early as 2008:
http://www.haskell.org/pipermail/libraries/2008-October/010797.html
It was added in 2014, in response to this feature request:
https://ghc.haskell.org/trac/ghc/ticket/9004


RATIONALES
----------

- convenience
- performance: faster than `sortBy`
- safety: encourages (although does not require) reliance on existing instances of Ord
- interface consistency (specifically, when comparing to Data.List)

Comment: it is certainly possible to pick at each of these rationales.
See the discussion here:
http://stackoverflow.com/questions/37691898/why-is-sortby-so-oddly-unconstrained-and-why-no-general-sorton/37735121


SCOPE
-----

Introduces no new dependencies except possibly on `Data.Ord.comparing`.


SOLUTIONS
-----------

The implementation in Data.List is::

         sortOn :: Ord b => (a -> b) -> [a] -> [a]
         sortOn f = map snd . sortBy (comparing fst)
                            . map (\x -> let y = f x in y `seq` (y, x))

An analogous implementation is possible for Data.Sequence.
However, this request does not propose a specific implementation.


WHAT MIGHT BREAK
----------------

No anticipated breakage.