diff options
| author | Alexander Berntsen <alexander@plaimi.net> | 2014-04-18 21:41:11 +0200 |
|---|---|---|
| committer | Herbert Valerio Riedel <hvr@gnu.org> | 2014-04-19 11:47:52 +0200 |
| commit | 44512e3c855d8fb36ab6580f4f97f842ebcf4c6c (patch) | |
| tree | a88d94ae4f40afa0ab8c21b695c8239dca692de3 /libraries | |
| parent | 1bf6c0e482cfe4b9dfa0b5ed18a5741ba44fc226 (diff) | |
| download | haskell-44512e3c855d8fb36ab6580f4f97f842ebcf4c6c.tar.gz | |
Add Data.List.sortOn function (re #9004 and #2659)
`sortOn` sorts a list by comparing the results of a key function applied to each
element. `sortOn f` is equivalent to `sortBy . comparing f`, but has the
performance advantage of only evaluating `f` once for each element in the
input list.
Historical note: This was already proposed in 2008 as part of
http://www.haskell.org/pipermail/libraries/2008-October/010797.html
It was, however, the recent re-attempt
http://www.haskell.org/pipermail/libraries/2014-April/022489.html
that let `sortOn` make it into base at last. Maybe the other functions
mentioned in #2659 might be worth reconsidering as well.
Diffstat (limited to 'libraries')
| -rw-r--r-- | libraries/base/Data/List.hs | 14 | ||||
| -rw-r--r-- | libraries/base/changelog.md | 2 |
2 files changed, 16 insertions, 0 deletions
diff --git a/libraries/base/Data/List.hs b/libraries/base/Data/List.hs index 09aed9d324..7f66528a44 100644 --- a/libraries/base/Data/List.hs +++ b/libraries/base/Data/List.hs @@ -164,6 +164,7 @@ module Data.List -- ** Ordered lists , sort + , sortOn , insert -- * Generalized functions @@ -207,6 +208,8 @@ module Data.List import Data.Maybe import Data.Char ( isSpace ) +import Data.Ord ( comparing ) +import Data.Tuple ( fst, snd ) import GHC.Num import GHC.Real @@ -957,6 +960,17 @@ rqpart cmp x (y:ys) rle rgt r = #endif /* USE_REPORT_PRELUDE */ +-- | Sort a list by comparing the results of a key function applied to each +-- element. @sortOn f@ is equivalent to @sortBy . comparing f@, but has the +-- performance advantage of only evaluating @f@ once for each element in the +-- input list. This is called the decorate-sort-undecorate paradigm, or +-- Schwartzian transform. +-- +-- /Since: 4.7.1.0/ +sortOn :: Ord b => (a -> b) -> [a] -> [a] +sortOn f = + map snd . sortBy (comparing fst) . map (\x -> let y = f x in y `seq` (y, x)) + -- | The 'unfoldr' function is a \`dual\' to 'foldr': while 'foldr' -- reduces a list to a summary value, 'unfoldr' builds a list from -- a seed value. The function takes the element and returns 'Nothing' diff --git a/libraries/base/changelog.md b/libraries/base/changelog.md index 75e7710d55..3011fdfdc7 100644 --- a/libraries/base/changelog.md +++ b/libraries/base/changelog.md @@ -6,6 +6,8 @@ * Add reverse application operator `Data.Function.(&)` + * Add `Data.List.sortOn` sorting function + ## 4.7.0.0 *Apr 2014* * Bundled with GHC 7.8.1 |