Proposal #2659: Add sortOn and friends to Data.List

[Mitchell, Neil]

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