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

Commits:

8 changed files:

Changes:

  • libraries/base/base.cabal.in
    ... ... @@ -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)

  • libraries/base/changelog.md
    ... ... @@ -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

  • libraries/base/src/Data/List.hs
    ... ... @@ -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

  • libraries/base/src/Data/List/NonEmpty.hs
    ... ... @@ -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

  • testsuite/tests/interface-stability/base-exports.stdout
    ... ... @@ -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)

  • testsuite/tests/interface-stability/base-exports.stdout-javascript-unknown-ghcjs
    ... ... @@ -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)

  • testsuite/tests/interface-stability/base-exports.stdout-mingw32
    ... ... @@ -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)

  • testsuite/tests/interface-stability/base-exports.stdout-ws-32
    ... ... @@ -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)

    • —
    View it on GitLab.
    You're receiving this email because of your account on gitlab.haskell.org. Manage all notifications · Help