Request: Add sortOn to Data.Sequence

[Edward Kmett]

We've already accepted a similar addition to Data.List, so I see no harm in
having an implementation for Data.Sequence.

-Edward

On Fri, Jun 10, 2016 at 12:45 PM, David Feuer <david.feuer at gmail.com> wrote:

> I think thIs is an interesting idea, generally. There seem to be two
> situations that may call for separate functions. If the "key" type can be
> stored in an unboxed mutable array, then it seems likely desirable to sort
> using such an array. Otherwise, we can use the existing sortBy as suggested.
> On Jun 10, 2016 12:30 PM, "Alan Isaac" <alan.isaac at gmail.com> wrote:
>
> 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.
>
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
>
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20160610/04115445/attachment.html>