Opened 4 years ago

Closed 4 years ago

Last modified 3 years ago

#9004 closed feature request (fixed)

Add sortOn function to Data.List

Reported by: JohnWiegley Owned by:
Priority: normal Milestone: 7.10.1
Component: libraries/base Version: 7.8.2
Keywords: report-impact Cc: hvr, ekmett
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

The following passed for two weeks on the libraries mailing list without any dissenting votes.

The request is to add the following function to Data.List:

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

Attachments (2)

0001-Data.List-Add-sortOn.patch (1.5 KB) - added by bernalex 4 years ago.
0001-Data.List-Add-sortOn-9004.patch (1.5 KB) - added by bernalex 4 years ago.

Download all attachments as: .zip

Change History (7)

Changed 4 years ago by bernalex

comment:1 Changed 4 years ago by bernalex

Status: newpatch

Changed 4 years ago by bernalex

comment:2 Changed 4 years ago by bernalex

I forgot to add the bug number to the commit message. Please use the latter patch.

comment:3 Changed 4 years ago by Herbert Valerio Riedel <hvr@…>

In 44512e3c855d8fb36ab6580f4f97f842ebcf4c6c/ghc:

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.

comment:4 Changed 4 years ago by hvr

Resolution: fixed
Status: patchclosed

comment:5 Changed 3 years ago by hvr

Cc: ekmett added
Keywords: report-impact added
Note: See TracTickets for help on using tickets.