Bodigrim pushed to branch wip/nubOrd at Glasgow Haskell Compiler / GHC
Commits:
-
7bb832f1
by Andrew Lelechenko at 2025-07-21T21:03:41+01:00
9 changed files:
- libraries/base/base.cabal.in
- libraries/base/changelog.md
- libraries/base/src/Data/List.hs
- libraries/base/src/Data/List/NonEmpty.hs
- + libraries/base/src/Data/List/Set.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:
| ... | ... | @@ -305,6 +305,7 @@ Library |
| 305 | 305 | , GHC.JS.Foreign.Callback
|
| 306 | 306 | |
| 307 | 307 | other-modules:
|
| 308 | + Data.List.Set
|
|
| 308 | 309 | System.CPUTime.Unsupported
|
| 309 | 310 | System.CPUTime.Utils
|
| 310 | 311 | if os(windows)
|
| ... | ... | @@ -2,6 +2,7 @@ |
| 2 | 2 | |
| 3 | 3 | ## 4.23.0.0 *TBA*
|
| 4 | 4 | * Add `Data.List.NonEmpty.mapMaybe`. ([CLC proposal #337](https://github.com/haskell/core-libraries-committee/issues/337))
|
| 5 | + * Add `nubOrd` / `nubOrdBy` to `Data.List` and `Data.List.NonEmpty`. ([CLC proposal #336](https://github.com/haskell/core-libraries-committee/issues/336))
|
|
| 5 | 6 | |
| 6 | 7 | ## 4.22.0.0 *TBA*
|
| 7 | 8 | * Shipped with GHC 9.14.1
|
| ... | ... | @@ -137,6 +137,7 @@ module Data.List |
| 137 | 137 | unwords,
|
| 138 | 138 | -- ** \"Set\" operations
|
| 139 | 139 | nub,
|
| 140 | + nubOrd,
|
|
| 140 | 141 | delete,
|
| 141 | 142 | (\\),
|
| 142 | 143 | union,
|
| ... | ... | @@ -157,6 +158,7 @@ module Data.List |
| 157 | 158 | -- *** User-supplied equality (replacing an @Eq@ context)
|
| 158 | 159 | -- | The predicate is assumed to define an equivalence.
|
| 159 | 160 | nubBy,
|
| 161 | + nubOrdBy,
|
|
| 160 | 162 | deleteBy,
|
| 161 | 163 | deleteFirstsBy,
|
| 162 | 164 | unionBy,
|
| ... | ... | @@ -180,12 +182,14 @@ module Data.List |
| 180 | 182 | ) where
|
| 181 | 183 | |
| 182 | 184 | import GHC.Internal.Data.Bool (otherwise)
|
| 185 | +import GHC.Internal.Data.Function (const, flip)
|
|
| 183 | 186 | import GHC.Internal.Data.List
|
| 184 | 187 | import GHC.Internal.Data.List.NonEmpty (NonEmpty(..))
|
| 185 | -import GHC.Internal.Data.Ord (Ordering(..), (<), (>))
|
|
| 188 | +import GHC.Internal.Data.Ord (Ord, compare, Ordering(..), (<), (>))
|
|
| 186 | 189 | import GHC.Internal.Int (Int)
|
| 187 | 190 | import GHC.Internal.Num ((-))
|
| 188 | 191 | import GHC.List (build)
|
| 192 | +import qualified Data.List.Set as Set
|
|
| 189 | 193 | |
| 190 | 194 | inits1, tails1 :: [a] -> [NonEmpty a]
|
| 191 | 195 | |
| ... | ... | @@ -282,3 +286,15 @@ compareLength xs n |
| 282 | 286 | (\m -> if m > 0 then LT else EQ)
|
| 283 | 287 | xs
|
| 284 | 288 | n
|
| 289 | + |
|
| 290 | +-- | Same as 'nub', but asymptotically faster, taking only /O/(/n/ log /n/) time.
|
|
| 291 | +--
|
|
| 292 | +-- @since 4.23.0.0
|
|
| 293 | +nubOrd :: Ord a => [a] -> [a]
|
|
| 294 | +nubOrd = nubOrdBy compare
|
|
| 295 | + |
|
| 296 | +-- | Overloaded version of 'Data.List.nubOrd'.
|
|
| 297 | +--
|
|
| 298 | +-- @since 4.23.0.0
|
|
| 299 | +nubOrdBy :: (a -> a -> Ordering) -> [a] -> [a]
|
|
| 300 | +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 |
| ... | ... | @@ -94,7 +94,9 @@ module Data.List.NonEmpty ( |
| 94 | 94 | , isPrefixOf -- :: Eq a => [a] -> NonEmpty a -> Bool
|
| 95 | 95 | -- * \"Set\" operations
|
| 96 | 96 | , nub -- :: Eq a => NonEmpty a -> NonEmpty a
|
| 97 | + , nubOrd -- :: Ord a => NonEmpty a -> NonEmpty a
|
|
| 97 | 98 | , nubBy -- :: (a -> a -> Bool) -> NonEmpty a -> NonEmpty a
|
| 99 | + , nubOrdBy -- :: (a -> a -> Ordering) -> NonEmpty a -> NonEmpty a
|
|
| 98 | 100 | -- * Indexing streams
|
| 99 | 101 | , (!!) -- :: NonEmpty a -> Int -> a
|
| 100 | 102 | -- * Zipping and unzipping streams
|
| ... | ... | @@ -119,6 +121,7 @@ import qualified Prelude |
| 119 | 121 | |
| 120 | 122 | import Control.Applicative (Applicative (..), Alternative (many))
|
| 121 | 123 | import qualified Data.List as List
|
| 124 | +import qualified Data.List.Set as Set
|
|
| 122 | 125 | import qualified Data.Maybe as List (mapMaybe)
|
| 123 | 126 | import GHC.Internal.Data.Foldable hiding (length, toList)
|
| 124 | 127 | import qualified GHC.Internal.Data.Foldable as Foldable
|
| ... | ... | @@ -572,6 +575,18 @@ nub = nubBy (==) |
| 572 | 575 | nubBy :: (a -> a -> Bool) -> NonEmpty a -> NonEmpty a
|
| 573 | 576 | nubBy eq (a :| as) = a :| List.nubBy eq (List.filter (\b -> not (eq a b)) as)
|
| 574 | 577 | |
| 578 | +-- | Same as 'nub', but asymptotically faster, taking only /O/(/n/ log /n/) time.
|
|
| 579 | +--
|
|
| 580 | +-- @since 4.23.0.0
|
|
| 581 | +nubOrd :: Ord a => NonEmpty a -> NonEmpty a
|
|
| 582 | +nubOrd = nubOrdBy compare
|
|
| 583 | + |
|
| 584 | +-- | Overloaded version of 'Data.List.NonEmpty.nubOrd'.
|
|
| 585 | +--
|
|
| 586 | +-- @since 4.23.0.0
|
|
| 587 | +nubOrdBy :: (a -> a -> Ordering) -> NonEmpty a -> NonEmpty a
|
|
| 588 | +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)
|
|
| 589 | + |
|
| 575 | 590 | -- | 'transpose' for 'NonEmpty', behaves the same as 'GHC.Internal.Data.List.transpose'
|
| 576 | 591 | -- The rows/columns need not be the same length, in which case
|
| 577 | 592 | -- > transpose . transpose /= id
|
| 1 | +-- This is an internal module with a naive Set implementation,
|
|
| 2 | +-- solely for the purposes of `Data.List.{,NonEmpty.}nubOrd{,By}`.
|
|
| 3 | +-- Copied from https://hackage.haskell.org/package/infinite-list-0.1.2/src/src/Data/List/Infinite/Set.hs
|
|
| 4 | + |
|
| 5 | +{-# LANGUAGE BangPatterns #-}
|
|
| 6 | +{-# LANGUAGE LambdaCase #-}
|
|
| 7 | + |
|
| 8 | +module Data.List.Set (
|
|
| 9 | + Set,
|
|
| 10 | + empty,
|
|
| 11 | + member,
|
|
| 12 | + insert,
|
|
| 13 | +) where
|
|
| 14 | + |
|
| 15 | +import GHC.Internal.Data.Bool (Bool(..))
|
|
| 16 | +import GHC.Internal.Data.Function ((.))
|
|
| 17 | +import GHC.Internal.Data.Ord (Ordering(..))
|
|
| 18 | + |
|
| 19 | +data Color = Red | Black
|
|
| 20 | + |
|
| 21 | +-- | Okasaki red-black tree.
|
|
| 22 | +data Set a = Empty | Node !Color !(Set a) !a !(Set a)
|
|
| 23 | + |
|
| 24 | +empty :: Set a
|
|
| 25 | +empty = Empty
|
|
| 26 | + |
|
| 27 | +member :: (a -> a -> Ordering) -> a -> Set a -> Bool
|
|
| 28 | +member cmp = member'
|
|
| 29 | + where
|
|
| 30 | + member' !x = go
|
|
| 31 | + where
|
|
| 32 | + go = \case
|
|
| 33 | + Empty -> False
|
|
| 34 | + Node _ left center right -> case cmp x center of
|
|
| 35 | + LT -> go left
|
|
| 36 | + EQ -> True
|
|
| 37 | + GT -> go right
|
|
| 38 | + |
|
| 39 | +insert :: (a -> a -> Ordering) -> a -> Set a -> Set a
|
|
| 40 | +insert cmp = insert'
|
|
| 41 | + where
|
|
| 42 | + insert' !x = blacken . go
|
|
| 43 | + where
|
|
| 44 | + go = \case
|
|
| 45 | + Empty -> Node Red Empty x Empty
|
|
| 46 | + Node color left center right -> case cmp x center of
|
|
| 47 | + LT -> balance color (go left) center right
|
|
| 48 | + EQ -> Node color left center right
|
|
| 49 | + GT -> balance color left center (go right)
|
|
| 50 | + |
|
| 51 | + blacken = \case
|
|
| 52 | + Empty -> Empty
|
|
| 53 | + Node _ left center right -> Node Black left center right
|
|
| 54 | + |
|
| 55 | +balance :: Color -> Set a -> a -> Set a -> Set a
|
|
| 56 | +balance Black (Node Red (Node Red a b c) d e) f g =
|
|
| 57 | + Node Red (Node Black a b c) d (Node Black e f g)
|
|
| 58 | +balance Black (Node Red a b (Node Red c d e)) f g =
|
|
| 59 | + Node Red (Node Black a b c) d (Node Black e f g)
|
|
| 60 | +balance Black a b (Node Red (Node Red c d e) f g) =
|
|
| 61 | + Node Red (Node Black a b c) d (Node Black e f g)
|
|
| 62 | +balance Black a b (Node Red c d (Node Red e f g)) =
|
|
| 63 | + Node Red (Node Black a b c) d (Node Black e f g)
|
|
| 64 | +balance color left center right =
|
|
| 65 | + Node color left center right |
| ... | ... | @@ -1377,6 +1377,8 @@ module Data.List where |
| 1377 | 1377 | notElem :: forall (t :: * -> *) a. (GHC.Internal.Data.Foldable.Foldable t, GHC.Internal.Classes.Eq a) => a -> t a -> GHC.Internal.Types.Bool
|
| 1378 | 1378 | nub :: forall a. GHC.Internal.Classes.Eq a => [a] -> [a]
|
| 1379 | 1379 | nubBy :: forall a. (a -> a -> GHC.Internal.Types.Bool) -> [a] -> [a]
|
| 1380 | + nubOrd :: forall a. GHC.Internal.Classes.Ord a => [a] -> [a]
|
|
| 1381 | + nubOrdBy :: forall a. (a -> a -> GHC.Internal.Types.Ordering) -> [a] -> [a]
|
|
| 1380 | 1382 | null :: forall (t :: * -> *) a. GHC.Internal.Data.Foldable.Foldable t => t a -> GHC.Internal.Types.Bool
|
| 1381 | 1383 | or :: forall (t :: * -> *). GHC.Internal.Data.Foldable.Foldable t => t GHC.Internal.Types.Bool -> GHC.Internal.Types.Bool
|
| 1382 | 1384 | partition :: forall a. (a -> GHC.Internal.Types.Bool) -> [a] -> ([a], [a])
|
| ... | ... | @@ -1471,6 +1473,8 @@ module Data.List.NonEmpty where |
| 1471 | 1473 | nonEmpty :: forall a. [a] -> GHC.Internal.Maybe.Maybe (NonEmpty a)
|
| 1472 | 1474 | nub :: forall a. GHC.Internal.Classes.Eq a => NonEmpty a -> NonEmpty a
|
| 1473 | 1475 | nubBy :: forall a. (a -> a -> GHC.Internal.Types.Bool) -> NonEmpty a -> NonEmpty a
|
| 1476 | + nubOrd :: forall a. GHC.Internal.Classes.Ord a => NonEmpty a -> NonEmpty a
|
|
| 1477 | + nubOrdBy :: forall a. (a -> a -> GHC.Internal.Types.Ordering) -> NonEmpty a -> NonEmpty a
|
|
| 1474 | 1478 | partition :: forall a. (a -> GHC.Internal.Types.Bool) -> NonEmpty a -> ([a], [a])
|
| 1475 | 1479 | permutations :: forall a. [a] -> NonEmpty [a]
|
| 1476 | 1480 | permutations1 :: forall a. NonEmpty a -> NonEmpty (NonEmpty a)
|
| ... | ... | @@ -1377,6 +1377,8 @@ module Data.List where |
| 1377 | 1377 | notElem :: forall (t :: * -> *) a. (GHC.Internal.Data.Foldable.Foldable t, GHC.Internal.Classes.Eq a) => a -> t a -> GHC.Internal.Types.Bool
|
| 1378 | 1378 | nub :: forall a. GHC.Internal.Classes.Eq a => [a] -> [a]
|
| 1379 | 1379 | nubBy :: forall a. (a -> a -> GHC.Internal.Types.Bool) -> [a] -> [a]
|
| 1380 | + nubOrd :: forall a. GHC.Internal.Classes.Ord a => [a] -> [a]
|
|
| 1381 | + nubOrdBy :: forall a. (a -> a -> GHC.Internal.Types.Ordering) -> [a] -> [a]
|
|
| 1380 | 1382 | null :: forall (t :: * -> *) a. GHC.Internal.Data.Foldable.Foldable t => t a -> GHC.Internal.Types.Bool
|
| 1381 | 1383 | or :: forall (t :: * -> *). GHC.Internal.Data.Foldable.Foldable t => t GHC.Internal.Types.Bool -> GHC.Internal.Types.Bool
|
| 1382 | 1384 | partition :: forall a. (a -> GHC.Internal.Types.Bool) -> [a] -> ([a], [a])
|
| ... | ... | @@ -1471,6 +1473,8 @@ module Data.List.NonEmpty where |
| 1471 | 1473 | nonEmpty :: forall a. [a] -> GHC.Internal.Maybe.Maybe (NonEmpty a)
|
| 1472 | 1474 | nub :: forall a. GHC.Internal.Classes.Eq a => NonEmpty a -> NonEmpty a
|
| 1473 | 1475 | nubBy :: forall a. (a -> a -> GHC.Internal.Types.Bool) -> NonEmpty a -> NonEmpty a
|
| 1476 | + nubOrd :: forall a. GHC.Internal.Classes.Ord a => NonEmpty a -> NonEmpty a
|
|
| 1477 | + nubOrdBy :: forall a. (a -> a -> GHC.Internal.Types.Ordering) -> NonEmpty a -> NonEmpty a
|
|
| 1474 | 1478 | partition :: forall a. (a -> GHC.Internal.Types.Bool) -> NonEmpty a -> ([a], [a])
|
| 1475 | 1479 | permutations :: forall a. [a] -> NonEmpty [a]
|
| 1476 | 1480 | permutations1 :: forall a. NonEmpty a -> NonEmpty (NonEmpty a)
|
| ... | ... | @@ -1377,6 +1377,8 @@ module Data.List where |
| 1377 | 1377 | notElem :: forall (t :: * -> *) a. (GHC.Internal.Data.Foldable.Foldable t, GHC.Internal.Classes.Eq a) => a -> t a -> GHC.Internal.Types.Bool
|
| 1378 | 1378 | nub :: forall a. GHC.Internal.Classes.Eq a => [a] -> [a]
|
| 1379 | 1379 | nubBy :: forall a. (a -> a -> GHC.Internal.Types.Bool) -> [a] -> [a]
|
| 1380 | + nubOrd :: forall a. GHC.Internal.Classes.Ord a => [a] -> [a]
|
|
| 1381 | + nubOrdBy :: forall a. (a -> a -> GHC.Internal.Types.Ordering) -> [a] -> [a]
|
|
| 1380 | 1382 | null :: forall (t :: * -> *) a. GHC.Internal.Data.Foldable.Foldable t => t a -> GHC.Internal.Types.Bool
|
| 1381 | 1383 | or :: forall (t :: * -> *). GHC.Internal.Data.Foldable.Foldable t => t GHC.Internal.Types.Bool -> GHC.Internal.Types.Bool
|
| 1382 | 1384 | partition :: forall a. (a -> GHC.Internal.Types.Bool) -> [a] -> ([a], [a])
|
| ... | ... | @@ -1471,6 +1473,8 @@ module Data.List.NonEmpty where |
| 1471 | 1473 | nonEmpty :: forall a. [a] -> GHC.Internal.Maybe.Maybe (NonEmpty a)
|
| 1472 | 1474 | nub :: forall a. GHC.Internal.Classes.Eq a => NonEmpty a -> NonEmpty a
|
| 1473 | 1475 | nubBy :: forall a. (a -> a -> GHC.Internal.Types.Bool) -> NonEmpty a -> NonEmpty a
|
| 1476 | + nubOrd :: forall a. GHC.Internal.Classes.Ord a => NonEmpty a -> NonEmpty a
|
|
| 1477 | + nubOrdBy :: forall a. (a -> a -> GHC.Internal.Types.Ordering) -> NonEmpty a -> NonEmpty a
|
|
| 1474 | 1478 | partition :: forall a. (a -> GHC.Internal.Types.Bool) -> NonEmpty a -> ([a], [a])
|
| 1475 | 1479 | permutations :: forall a. [a] -> NonEmpty [a]
|
| 1476 | 1480 | permutations1 :: forall a. NonEmpty a -> NonEmpty (NonEmpty a)
|
| ... | ... | @@ -1377,6 +1377,8 @@ module Data.List where |
| 1377 | 1377 | notElem :: forall (t :: * -> *) a. (GHC.Internal.Data.Foldable.Foldable t, GHC.Internal.Classes.Eq a) => a -> t a -> GHC.Internal.Types.Bool
|
| 1378 | 1378 | nub :: forall a. GHC.Internal.Classes.Eq a => [a] -> [a]
|
| 1379 | 1379 | nubBy :: forall a. (a -> a -> GHC.Internal.Types.Bool) -> [a] -> [a]
|
| 1380 | + nubOrd :: forall a. GHC.Internal.Classes.Ord a => [a] -> [a]
|
|
| 1381 | + nubOrdBy :: forall a. (a -> a -> GHC.Internal.Types.Ordering) -> [a] -> [a]
|
|
| 1380 | 1382 | null :: forall (t :: * -> *) a. GHC.Internal.Data.Foldable.Foldable t => t a -> GHC.Internal.Types.Bool
|
| 1381 | 1383 | or :: forall (t :: * -> *). GHC.Internal.Data.Foldable.Foldable t => t GHC.Internal.Types.Bool -> GHC.Internal.Types.Bool
|
| 1382 | 1384 | partition :: forall a. (a -> GHC.Internal.Types.Bool) -> [a] -> ([a], [a])
|
| ... | ... | @@ -1471,6 +1473,8 @@ module Data.List.NonEmpty where |
| 1471 | 1473 | nonEmpty :: forall a. [a] -> GHC.Internal.Maybe.Maybe (NonEmpty a)
|
| 1472 | 1474 | nub :: forall a. GHC.Internal.Classes.Eq a => NonEmpty a -> NonEmpty a
|
| 1473 | 1475 | nubBy :: forall a. (a -> a -> GHC.Internal.Types.Bool) -> NonEmpty a -> NonEmpty a
|
| 1476 | + nubOrd :: forall a. GHC.Internal.Classes.Ord a => NonEmpty a -> NonEmpty a
|
|
| 1477 | + nubOrdBy :: forall a. (a -> a -> GHC.Internal.Types.Ordering) -> NonEmpty a -> NonEmpty a
|
|
| 1474 | 1478 | partition :: forall a. (a -> GHC.Internal.Types.Bool) -> NonEmpty a -> ([a], [a])
|
| 1475 | 1479 | permutations :: forall a. [a] -> NonEmpty [a]
|
| 1476 | 1480 | permutations1 :: forall a. NonEmpty a -> NonEmpty (NonEmpty a)
|