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

[Twan van Laarhoven]

Hello list,


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


-- Naming --

"On": The reason for the "on" suffix is that it relates to the "on" function 
from Data.Function: "sortOn f = sort (compare `on` f)". In code, "sortOn fst" is 
reasonably natural, "sortBy fst" would be better but that is already taken.

"With": Another possible choice is the "with" suffix. There is some precedence 
for this choice [2]. A big disadvantage is that the "with" suffix is commonly 
used for combining functions, as in Data.Map.unionWith. Making a 
Data.List.unionWith that does something completely different sounds like a bad idea.

"ByComparing": Defining
    sortByComparing f = sortBy (comparing f)
makes sense, naming wise. A disadvantage of this name is that it is too long. 
Also, we would get a distinction between "groupByEquating" and "sortByComparing".


-- Variations --

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

This is perhaps not the best name, since ' usually means strictness.


-- Descending sort--

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?


-- Proposal--

Ticket:   #2659 (for sortOn and friends)
Ticket:   #2660 (for Down newtype)
Deadline: now+2 weeks = 2008-10-20

Questions:
   1. should sortOn be added to Data.List?
   2. should all other *On functions be added as well?
   3. what name should these functions get?
   4. should the sortOn' variations be added? What about the naming?
   5. should Down be added to Data.Ord?

Note: The addition of sortOn was previously proposed as #2406 and rejected 
because it did not follow the library submission guidelines.


Twan


[1] http://www.google.com/codesearch?q=lang%3Ahaskell+sortBy
[2] http://research.microsoft.com/~simonpj/papers/list-comp/index.htm