Proposal #2659: Add sortOn and friends to Data.List
Mitchell, Neil
neil.mitchell.2 at credit-suisse.com
Mon Oct 6 04:21:45 EDT 2008
Hi Twan,
> Almost all uses of sortBy in user code use 'comparing', 'on'
> or a similar construction [1]. I think we should add a
> function that makes this common behavior more convenient:
>
> sortOn :: Ord b => (a -> b) -> [a] -> [a]
>
> For consistency we should also add *On for the other *By
> functions in Data.List:
>
> nubOn :: Eq b => (a -> b) -> [a] -> [a]
> deleteOn :: Eq b => (a -> b) -> a -> [a] -> [a]
> deleteFirstsOn :: Eq b => (a -> b) -> [a] -> [a] -> [a]
> unionOn :: Eq b => (a -> b) -> [a] -> [a] -> [a]
> intersectOn :: Eq b => (a -> b) -> [a] -> [a] -> [a]
> groupOn :: Eq b => (a -> b) -> [a] -> [[a]]
> sortOn :: Ord b => (a -> b) -> [a] -> [a]
> insertOn :: Ord b => (a -> b) -> a -> [a] -> [a]
> maximumOn :: Ord b => (a -> b) -> [a] -> a
> minimumOn :: Ord b => (a -> b) -> [a] -> a
> (nubSortOn :: Ord b => (a -> b) -> [a] -> [a]) -- see #2629
All good, apart from deleteFirstsOn. I honestly don't know what that
function does, I was thinking possibly something like the first
component of tuples? But no real idea.
> When f is a slow function the call "sortOn f xs" recomputes f
> more than necessary. A version that caches the result of f is
> easy to define:
>
> sortOn' f = map fst . sortOn snd . map (\x -> (x,f x))
In Hoogle I use sortOn to be the non-cacheing version, and sortWith to
be the cacheing version. However, I think we can just ignore the
non-cacheing version - if your extraction function is expensive you
probably want to think a bit anyway.
> To be able to sort lists in reverse order, a simple newtype
> should be added to
> Data.Ord:
>
> newtype Down a = Down { getDown :: a }
>
> instance Ord a => Ord (Down a) where
> Down x < Down y = y < x
>
> Now "sortOn Down xs == reverse (sort xs)".
> The name Down comes from [2], maybe Desc is a better name?
I prefer Down, and strongly support this proposal as well.
> 1. should sortOn be added to Data.List?
Yes.
> 2. should all other *On functions be added as well?
Yes (apart from deleteFirstsOn)
> 3. what name should these functions get?
*On, as you have given them.
> 4. should the sortOn' variations be added? What about the naming?
No.
> 5. should Down be added to Data.Ord?
Yes.
Thanks
Neil
==============================================================================
Please access the attached hyperlink for an important electronic communications disclaimer:
http://www.credit-suisse.com/legal/en/disclaimer_email_ib.html
==============================================================================
More information about the Libraries
mailing list