Proposal #2659: Add sortOn and friends to Data.List
Twan van Laarhoven
twanvl at gmail.com
Sun Oct 5 11:39:40 EDT 2008
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
More information about the Libraries
mailing list