GitLab

Marge Bot pushed to branch master at Glasgow Haskell Compiler / GHC

Commits:

1f9e4f54

by Stephen Morgan at 2025-08-03T15:14:08+10:00

refactor: Modify Data.List.sortOn to use (>) instead of compare. (#26184)

This lets a more efficient (>) operation be used if one exists.

This is technically a breaking change for malformed Ord instances, where
x > y is not equivalent to compare x y == GT.

Discussed by the CLC in issue #332: https://github.com/haskell/core-libraries-committee/issues/332

3 changed files:

libraries/base/changelog.md
libraries/base/src/Data/List/NonEmpty.hs
libraries/ghc-internal/src/GHC/Internal/Data/OldList.hs

Changes:

libraries/base/changelog.md

@@ -3,6 +3,7 @@
  ## 4.23.0.0 *TBA*
    * Add `Data.List.NonEmpty.mapMaybe`. ([CLC proposal #337](https://github.com/haskell/core-libraries-committee/issues/337))
    * Fix issues with toRational for types capable to represent infinite and not-a-number values ([CLC proposal #338](https://github.com/haskell/core-libraries-committee/issues/338))
 +  * Modify the implementation of `Data.List.sortOn` to use `(>)` instead of `compare`. ([CLC proposal #332](https://github.com/haskell/core-libraries-committee/issues/332))
  ## 4.22.0.0 *TBA*
    * Shipped with GHC 9.14.1

libraries/base/src/Data/List/NonEmpty.hs

@@ -268,6 +268,9 @@ sort = lift List.sort
  -- >>> (sortBy . comparing) fst $ (3, 1) :| [(2, 2), (1, 3)]
  -- (1,3) :| [(2,2),(3,1)]
  --
 +-- However, 'sortOn' may still be faster for instances with a more efficient
 +-- implementation of '(>)' than 'compare'.
 +--
  -- 'sortWith' is an alias for `sortBy . comparing`.
  --
  -- @since 4.20.0.0

libraries/ghc-internal/src/GHC/Internal/Data/OldList.hs

@@ -216,7 +216,6 @@ module GHC.Internal.Data.OldList
  import GHC.Internal.Data.Maybe
  import GHC.Internal.Data.Bits        ( (.&.) )
  import GHC.Internal.Unicode      ( isSpace )
 -import GHC.Internal.Data.Ord         ( comparing )
  import GHC.Internal.Data.Tuple       ( fst, snd )
  import GHC.Internal.Num
@@ -1862,10 +1861,13 @@ rqpart cmp x (y:ys) rle rgt r =
  -- >>> (sortBy . comparing) fst [(3, 1), (2, 2), (1, 3)]
  -- [(1,3),(2,2),(3,1)]
  --
 +-- However, 'sortOn' may still be faster for instances with a more efficient
 +-- implementation of '(>)' than 'compare'.
 +--
  -- @since base-4.8.0.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))
 +  map snd . actualSort (\x y -> fst x > fst y) . map (\x -> let y = f x in y `seq` (y, x))
  -- | Construct a list from a single element.
  --