<div dir="ltr">We've already accepted a similar addition to Data.List, so I see no harm in having an implementation for Data.Sequence.<div><br></div><div>-Edward</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Jun 10, 2016 at 12:45 PM, David Feuer <span dir="ltr"><<a href="mailto:david.feuer@gmail.com" target="_blank">david.feuer@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><p dir="ltr">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.</p><div class="HOEnZb"><div class="h5">
<div class="gmail_quote">On Jun 10, 2016 12:30 PM, "Alan Isaac" <<a href="mailto:alan.isaac@gmail.com" target="_blank">alan.isaac@gmail.com</a>> wrote:<br type="attribution"><blockquote style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">REQUEST<br>
-------<br>
<br>
The request is to add `sortOn` to Data.Sequence.<br>
`sortOn f` would be equivalent to `sortBy . comparing f`,<br>
but would offer a performance advantage by using a Schwartzian<br>
transform to only evaluate `f` once for each element<br>
in the input sequence.<br>
<br>
<br>
BACKGROUND<br>
----------<br>
<br>
Adding `sortOn` to `Data.List` was proposed at least as early as 2008:<br>
<a href="http://www.haskell.org/pipermail/libraries/2008-October/010797.html" rel="noreferrer" target="_blank">http://www.haskell.org/pipermail/libraries/2008-October/010797.html</a><br>
It was added in 2014, in response to this feature request:<br>
<a href="https://ghc.haskell.org/trac/ghc/ticket/9004" rel="noreferrer" target="_blank">https://ghc.haskell.org/trac/ghc/ticket/9004</a><br>
<br>
<br>
RATIONALES<br>
----------<br>
<br>
- convenience<br>
- performance: faster than `sortBy`<br>
- safety: encourages (although does not require) reliance on existing instances of Ord<br>
- interface consistency (specifically, when comparing to Data.List)<br>
<br>
Comment: it is certainly possible to pick at each of these rationales.<br>
See the discussion here:<br>
<a href="http://stackoverflow.com/questions/37691898/why-is-sortby-so-oddly-unconstrained-and-why-no-general-sorton/37735121" rel="noreferrer" target="_blank">http://stackoverflow.com/questions/37691898/why-is-sortby-so-oddly-unconstrained-and-why-no-general-sorton/37735121</a><br>
<br>
<br>
SCOPE<br>
-----<br>
<br>
Introduces no new dependencies except possibly on `Data.Ord.comparing`.<br>
<br>
<br>
SOLUTIONS<br>
-----------<br>
<br>
The implementation in Data.List is::<br>
<br>
        sortOn :: Ord b => (a -> b) -> [a] -> [a]<br>
        sortOn f = map snd . sortBy (comparing fst)<br>
                           . map (\x -> let y = f x in y `seq` (y, x))<br>
<br>
An analogous implementation is possible for Data.Sequence.<br>
However, this request does not propose a specific implementation.<br>
<br>
<br>
WHAT MIGHT BREAK<br>
----------------<br>
<br>
No anticipated breakage.<br>
<br>
_______________________________________________<br>
Libraries mailing list<br>
<a href="mailto:Libraries@haskell.org" target="_blank">Libraries@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries</a><br>
</blockquote></div>
</div></div><br>_______________________________________________<br>
Libraries mailing list<br>
<a href="mailto:Libraries@haskell.org">Libraries@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries</a><br>
<br></blockquote></div><br></div>