[Git][ghc/ghc][wip/nubOrd] Add nubOrd / nubOrdBy to Data.List and Data.List.NonEmpty

19 Jul 2025


      Bodigrim pushed to branch wip/nubOrd at Glasgow Haskell Compiler / GHC


Commits:
ba4a2263 by Andrew Lelechenko at 2025-07-19T15:38:30+01:00
Add nubOrd / nubOrdBy to Data.List and Data.List.NonEmpty

As per https://github.com/haskell/core-libraries-committee/issues/336

- - - - -


8 changed files:

- libraries/base/base.cabal.in
- libraries/base/changelog.md
- libraries/base/src/Data/List.hs
- libraries/base/src/Data/List/NonEmpty.hs
- testsuite/tests/interface-stability/base-exports.stdout
- testsuite/tests/interface-stability/base-exports.stdout-javascript-unknown-ghcjs
- testsuite/tests/interface-stability/base-exports.stdout-mingw32
- testsuite/tests/interface-stability/base-exports.stdout-ws-32


Changes:

=====================================
libraries/base/base.cabal.in
=====================================
@@ -305,6 +305,7 @@ Library
             , GHC.JS.Foreign.Callback
 
     other-modules:
+        Data.List.Set
         System.CPUTime.Unsupported
         System.CPUTime.Utils
     if os(windows)


=====================================
libraries/base/changelog.md
=====================================
@@ -2,6 +2,7 @@
 
 ## 4.23.0.0 *TBA*
   * Add `Data.List.NonEmpty.mapMaybe`. ([CLC proposal #337](https://github.com/haskell/core-libraries-committee/issues/337))
+  * Add `nubOrd` / `nubOrdBy` to `Data.List` and `Data.List.NonEmpty`. ([CLC proposal #336](https://github.com/haskell/core-libraries-committee/issues/336))
 
 ## 4.22.0.0 *TBA*
   * Shipped with GHC 9.14.1


=====================================
libraries/base/src/Data/List.hs
=====================================
@@ -137,6 +137,7 @@ module Data.List
      unwords,
      -- **  \"Set\" operations
      nub,
+     nubOrd,
      delete,
      (\\),
      union,
@@ -157,6 +158,7 @@ module Data.List
      -- ***  User-supplied equality (replacing an @Eq@ context)
      -- |  The predicate is assumed to define an equivalence.
      nubBy,
+     nubOrdBy,
      deleteBy,
      deleteFirstsBy,
      unionBy,
@@ -180,12 +182,14 @@ module Data.List
      ) where
 
 import GHC.Internal.Data.Bool (otherwise)
+import GHC.Internal.Data.Function (const, flip)
 import GHC.Internal.Data.List
 import GHC.Internal.Data.List.NonEmpty (NonEmpty(..))
-import GHC.Internal.Data.Ord (Ordering(..), (<), (>))
+import GHC.Internal.Data.Ord (Ord, compare, Ordering(..), (<), (>))
 import GHC.Internal.Int (Int)
 import GHC.Internal.Num ((-))
 import GHC.List (build)
+import qualified Data.List.Set as Set
 
 inits1, tails1 :: [a] -> [NonEmpty a]
 
@@ -282,3 +286,15 @@ compareLength xs n
     (\m -> if m > 0 then LT else EQ)
     xs
     n
+
+-- | Same as 'nub', but asymptotically faster, taking only /O/(/n/ log /n/) time.
+--
+-- @since 4.23.0.0
+nubOrd :: Ord a => [a] -> [a]
+nubOrd = nubOrdBy compare
+
+-- | Overloaded version of 'Data.List.nubOrd'.
+--
+-- @since 4.23.0.0
+nubOrdBy :: (a -> a -> Ordering) -> [a] -> [a]
+nubOrdBy cmp = flip (foldr (\x acc seen -> if Set.member cmp x seen then acc seen else x : acc (Set.insert cmp x seen)) (const [])) Set.empty


=====================================
libraries/base/src/Data/List/NonEmpty.hs
=====================================
@@ -94,7 +94,9 @@ module Data.List.NonEmpty (
    , isPrefixOf  -- :: Eq a => [a] -> NonEmpty a -> Bool
    -- * \"Set\" operations
    , nub         -- :: Eq a => NonEmpty a -> NonEmpty a
+   , nubOrd      -- :: Ord a => NonEmpty a -> NonEmpty a
    , nubBy       -- :: (a -> a -> Bool) -> NonEmpty a -> NonEmpty a
+   , nubOrdBy    -- :: (a -> a -> Ordering) -> NonEmpty a -> NonEmpty a
    -- * Indexing streams
    , (!!)        -- :: NonEmpty a -> Int -> a
    -- * Zipping and unzipping streams
@@ -119,6 +121,7 @@ import qualified Prelude
 
 import           Control.Applicative (Applicative (..), Alternative (many))
 import qualified Data.List                        as List
+import qualified Data.List.Set                    as Set
 import qualified Data.Maybe                       as List (mapMaybe)
 import           GHC.Internal.Data.Foldable       hiding (length, toList)
 import qualified GHC.Internal.Data.Foldable       as Foldable
@@ -572,6 +575,18 @@ nub = nubBy (==)
 nubBy :: (a -> a -> Bool) -> NonEmpty a -> NonEmpty a
 nubBy eq (a :| as) = a :| List.nubBy eq (List.filter (\b -> not (eq a b)) as)
 
+-- | Same as 'nub', but asymptotically faster, taking only /O/(/n/ log /n/) time.
+--
+-- @since 4.23.0.0
+nubOrd :: Ord a => NonEmpty a -> NonEmpty a
+nubOrd = nubOrdBy compare
+
+-- | Overloaded version of 'Data.List.NonEmpty.nubOrd'.
+--
+-- @since 4.23.0.0
+nubOrdBy :: (a -> a -> Ordering) -> NonEmpty a -> NonEmpty a
+nubOrdBy cmp (y :| ys) = y :| foldr (\x acc seen -> if Set.member cmp x seen then acc seen else x : acc (Set.insert cmp x seen)) (const []) ys (Set.insert cmp y Set.empty)
+
 -- | 'transpose' for 'NonEmpty', behaves the same as 'GHC.Internal.Data.List.transpose'
 -- The rows/columns need not be the same length, in which case
 -- > transpose . transpose /= id


=====================================
testsuite/tests/interface-stability/base-exports.stdout
=====================================
@@ -1377,6 +1377,8 @@ module Data.List where
   notElem :: forall (t :: * -> *) a. (GHC.Internal.Data.Foldable.Foldable t, GHC.Internal.Classes.Eq a) => a -> t a -> GHC.Internal.Types.Bool
   nub :: forall a. GHC.Internal.Classes.Eq a => [a] -> [a]
   nubBy :: forall a. (a -> a -> GHC.Internal.Types.Bool) -> [a] -> [a]
+  nubOrd :: forall a. GHC.Internal.Classes.Ord a => [a] -> [a]
+  nubOrdBy :: forall a. (a -> a -> GHC.Internal.Types.Ordering) -> [a] -> [a]
   null :: forall (t :: * -> *) a. GHC.Internal.Data.Foldable.Foldable t => t a -> GHC.Internal.Types.Bool
   or :: forall (t :: * -> *). GHC.Internal.Data.Foldable.Foldable t => t GHC.Internal.Types.Bool -> GHC.Internal.Types.Bool
   partition :: forall a. (a -> GHC.Internal.Types.Bool) -> [a] -> ([a], [a])
@@ -1471,6 +1473,8 @@ module Data.List.NonEmpty where
   nonEmpty :: forall a. [a] -> GHC.Internal.Maybe.Maybe (NonEmpty a)
   nub :: forall a. GHC.Internal.Classes.Eq a => NonEmpty a -> NonEmpty a
   nubBy :: forall a. (a -> a -> GHC.Internal.Types.Bool) -> NonEmpty a -> NonEmpty a
+  nubOrd :: forall a. GHC.Internal.Classes.Ord a => NonEmpty a -> NonEmpty a
+  nubOrdBy :: forall a. (a -> a -> GHC.Internal.Types.Ordering) -> NonEmpty a -> NonEmpty a
   partition :: forall a. (a -> GHC.Internal.Types.Bool) -> NonEmpty a -> ([a], [a])
   permutations :: forall a. [a] -> NonEmpty [a]
   permutations1 :: forall a. NonEmpty a -> NonEmpty (NonEmpty a)


=====================================
testsuite/tests/interface-stability/base-exports.stdout-javascript-unknown-ghcjs
=====================================
@@ -1377,6 +1377,8 @@ module Data.List where
   notElem :: forall (t :: * -> *) a. (GHC.Internal.Data.Foldable.Foldable t, GHC.Internal.Classes.Eq a) => a -> t a -> GHC.Internal.Types.Bool
   nub :: forall a. GHC.Internal.Classes.Eq a => [a] -> [a]
   nubBy :: forall a. (a -> a -> GHC.Internal.Types.Bool) -> [a] -> [a]
+  nubOrd :: forall a. GHC.Internal.Classes.Ord a => [a] -> [a]
+  nubOrdBy :: forall a. (a -> a -> GHC.Internal.Types.Ordering) -> [a] -> [a]
   null :: forall (t :: * -> *) a. GHC.Internal.Data.Foldable.Foldable t => t a -> GHC.Internal.Types.Bool
   or :: forall (t :: * -> *). GHC.Internal.Data.Foldable.Foldable t => t GHC.Internal.Types.Bool -> GHC.Internal.Types.Bool
   partition :: forall a. (a -> GHC.Internal.Types.Bool) -> [a] -> ([a], [a])
@@ -1471,6 +1473,8 @@ module Data.List.NonEmpty where
   nonEmpty :: forall a. [a] -> GHC.Internal.Maybe.Maybe (NonEmpty a)
   nub :: forall a. GHC.Internal.Classes.Eq a => NonEmpty a -> NonEmpty a
   nubBy :: forall a. (a -> a -> GHC.Internal.Types.Bool) -> NonEmpty a -> NonEmpty a
+  nubOrd :: forall a. GHC.Internal.Classes.Ord a => NonEmpty a -> NonEmpty a
+  nubOrdBy :: forall a. (a -> a -> GHC.Internal.Types.Ordering) -> NonEmpty a -> NonEmpty a
   partition :: forall a. (a -> GHC.Internal.Types.Bool) -> NonEmpty a -> ([a], [a])
   permutations :: forall a. [a] -> NonEmpty [a]
   permutations1 :: forall a. NonEmpty a -> NonEmpty (NonEmpty a)


=====================================
testsuite/tests/interface-stability/base-exports.stdout-mingw32
=====================================
@@ -1377,6 +1377,8 @@ module Data.List where
   notElem :: forall (t :: * -> *) a. (GHC.Internal.Data.Foldable.Foldable t, GHC.Internal.Classes.Eq a) => a -> t a -> GHC.Internal.Types.Bool
   nub :: forall a. GHC.Internal.Classes.Eq a => [a] -> [a]
   nubBy :: forall a. (a -> a -> GHC.Internal.Types.Bool) -> [a] -> [a]
+  nubOrd :: forall a. GHC.Internal.Classes.Ord a => [a] -> [a]
+  nubOrdBy :: forall a. (a -> a -> GHC.Internal.Types.Ordering) -> [a] -> [a]
   null :: forall (t :: * -> *) a. GHC.Internal.Data.Foldable.Foldable t => t a -> GHC.Internal.Types.Bool
   or :: forall (t :: * -> *). GHC.Internal.Data.Foldable.Foldable t => t GHC.Internal.Types.Bool -> GHC.Internal.Types.Bool
   partition :: forall a. (a -> GHC.Internal.Types.Bool) -> [a] -> ([a], [a])
@@ -1471,6 +1473,8 @@ module Data.List.NonEmpty where
   nonEmpty :: forall a. [a] -> GHC.Internal.Maybe.Maybe (NonEmpty a)
   nub :: forall a. GHC.Internal.Classes.Eq a => NonEmpty a -> NonEmpty a
   nubBy :: forall a. (a -> a -> GHC.Internal.Types.Bool) -> NonEmpty a -> NonEmpty a
+  nubOrd :: forall a. GHC.Internal.Classes.Ord a => NonEmpty a -> NonEmpty a
+  nubOrdBy :: forall a. (a -> a -> GHC.Internal.Types.Ordering) -> NonEmpty a -> NonEmpty a
   partition :: forall a. (a -> GHC.Internal.Types.Bool) -> NonEmpty a -> ([a], [a])
   permutations :: forall a. [a] -> NonEmpty [a]
   permutations1 :: forall a. NonEmpty a -> NonEmpty (NonEmpty a)


=====================================
testsuite/tests/interface-stability/base-exports.stdout-ws-32
=====================================
@@ -1377,6 +1377,8 @@ module Data.List where
   notElem :: forall (t :: * -> *) a. (GHC.Internal.Data.Foldable.Foldable t, GHC.Internal.Classes.Eq a) => a -> t a -> GHC.Internal.Types.Bool
   nub :: forall a. GHC.Internal.Classes.Eq a => [a] -> [a]
   nubBy :: forall a. (a -> a -> GHC.Internal.Types.Bool) -> [a] -> [a]
+  nubOrd :: forall a. GHC.Internal.Classes.Ord a => [a] -> [a]
+  nubOrdBy :: forall a. (a -> a -> GHC.Internal.Types.Ordering) -> [a] -> [a]
   null :: forall (t :: * -> *) a. GHC.Internal.Data.Foldable.Foldable t => t a -> GHC.Internal.Types.Bool
   or :: forall (t :: * -> *). GHC.Internal.Data.Foldable.Foldable t => t GHC.Internal.Types.Bool -> GHC.Internal.Types.Bool
   partition :: forall a. (a -> GHC.Internal.Types.Bool) -> [a] -> ([a], [a])
@@ -1471,6 +1473,8 @@ module Data.List.NonEmpty where
   nonEmpty :: forall a. [a] -> GHC.Internal.Maybe.Maybe (NonEmpty a)
   nub :: forall a. GHC.Internal.Classes.Eq a => NonEmpty a -> NonEmpty a
   nubBy :: forall a. (a -> a -> GHC.Internal.Types.Bool) -> NonEmpty a -> NonEmpty a
+  nubOrd :: forall a. GHC.Internal.Classes.Ord a => NonEmpty a -> NonEmpty a
+  nubOrdBy :: forall a. (a -> a -> GHC.Internal.Types.Ordering) -> NonEmpty a -> NonEmpty a
   partition :: forall a. (a -> GHC.Internal.Types.Bool) -> NonEmpty a -> ([a], [a])
   permutations :: forall a. [a] -> NonEmpty [a]
   permutations1 :: forall a. NonEmpty a -> NonEmpty (NonEmpty a)



View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/commit/ba4a22630ee96e9246aa67e5d60e88d2...

-- 
View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/commit/ba4a22630ee96e9246aa67e5d60e88d2...
You're receiving this email because of your account on gitlab.haskell.org.

    

Bodigrim (＠Bodigrim)

tags

participants (1)