packages feed

monoidmap 0.1.4.0 → 0.1.5.0

raw patch · 8 files changed

+489/−4 lines, 8 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

+ Data.MonoidMap: compare :: (Ord k, Ord v, Monoid v) => MonoidMap k v -> MonoidMap k v -> Ordering
+ Data.MonoidMap: instance (GHC.Classes.Ord k, GHC.Classes.Ord v, GHC.Base.Monoid v) => GHC.Classes.Ord (Data.MonoidMap.MonoidMap k v)

Files

CHANGELOG.md view
@@ -1,3 +1,11 @@+# 0.1.5.0++- Added an `Ord` instance for `MonoidMap`, which compares maps+  lexicographically, in ascending key order.++- Added a `compare` function for `MonoidMap`, which provides the definition of+  `compare` for the `Ord` instance.+ # 0.1.4.0  - Added `NFData1` and `NFData2` instances for `MonoidMap`.
components/monoidmap-test/Data/MonoidMap/ClassSpec.hs view
@@ -34,6 +34,7 @@     ( eqLaws     , isListLaws     , monoidLaws+    , ordLaws     , semigroupLaws     , semigroupMonoidLaws     , showReadLaws@@ -98,6 +99,7 @@             , leftReductiveLaws             , monoidLaws             , monoidNullLaws+            , ordLaws             , overlappingGCDMonoidLaws             , positiveMonoidLaws             , rightCancellativeLaws@@ -115,6 +117,7 @@             , leftReductiveLaws             , monoidLaws             , monoidNullLaws+            , ordLaws             , reductiveLaws             , rightReductiveLaws             , semigroupLaws@@ -135,6 +138,7 @@             , monoidLaws             , monoidNullLaws             , monusLaws+            , ordLaws             , overlappingGCDMonoidLaws             , positiveMonoidLaws             , reductiveLaws@@ -155,6 +159,7 @@             , isListLaws             , monoidLaws             , monoidNullLaws+            , ordLaws             , semigroupLaws             , semigroupMonoidLaws             , showReadLaws@@ -169,6 +174,7 @@             , leftReductiveLaws             , monoidLaws             , monoidNullLaws+            , ordLaws             , reductiveLaws             , rightCancellativeLaws             , rightReductiveLaws@@ -192,6 +198,7 @@             , monoidLaws             , monoidNullLaws             , monusLaws+            , ordLaws             , overlappingGCDMonoidLaws             , positiveMonoidLaws             , reductiveLaws@@ -217,6 +224,7 @@             , monoidLaws             , monoidNullLaws             , monusLaws+            , ordLaws             , overlappingGCDMonoidLaws             , positiveMonoidLaws             , reductiveLaws@@ -241,6 +249,7 @@             , monoidLaws             , monoidNullLaws             , monusLaws+            , ordLaws             , overlappingGCDMonoidLaws             , positiveMonoidLaws             , reductiveLaws@@ -265,6 +274,7 @@             , monoidLaws             , monoidNullLaws             , monusLaws+            , ordLaws             , overlappingGCDMonoidLaws             , positiveMonoidLaws             , reductiveLaws@@ -289,6 +299,7 @@             , monoidLaws             , monoidNullLaws             , monusLaws+            , ordLaws             , overlappingGCDMonoidLaws             , positiveMonoidLaws             , reductiveLaws@@ -315,6 +326,7 @@             , monoidLaws             , monoidNullLaws             , monusLaws+            , ordLaws             , overlappingGCDMonoidLaws             , positiveMonoidLaws             , reductiveLaws
components/monoidmap-test/Data/MonoidMap/ComparisonSpec.hs view
@@ -34,12 +34,24 @@     , property     , testValueTypesGCDMonoid     , testValueTypesAll+    , testValueTypesOrd+    , testValueTypesOrdLeftInvariant+    , testValueTypesOrdRightInvariant     , testValueTypesReductive     ) import Test.Hspec     ( Spec, describe, it ) import Test.QuickCheck-    ( Fun (..), Property, applyFun2, cover, expectFailure, (.||.), (===) )+    ( Fun (..)+    , Property+    , applyFun2+    , conjoin+    , cover+    , expectFailure+    , (.||.)+    , (=/=)+    , (===)+    )  import qualified Data.Monoid.GCD as GCDMonoid     ( GCDMonoid (..) )@@ -63,6 +75,18 @@         \(TestValueType p) -> specMonoidNull             (Proxy @Key) p +    forM_ testValueTypesOrd $+        \(TestValueType p) -> specOrd+            (Proxy @Key) p++    forM_ testValueTypesOrdLeftInvariant $+        \(TestValueType p) -> specOrdLeftInvariant+            (Proxy @Key) p++    forM_ testValueTypesOrdRightInvariant $+        \(TestValueType p) -> specOrdRightInvariant+            (Proxy @Key) p+ specGCDMonoid     :: forall k v. (Test k v, GCDMonoid v) => Proxy k -> Proxy v -> Spec specGCDMonoid = makeSpec $ do@@ -98,6 +122,228 @@     it "prop_isSubmapOfBy_get_total_failure" $         prop_isSubmapOfBy_get_total_failure             @k @v & property++specOrd+    :: forall k v. (Test k v, Ord v) => Proxy k -> Proxy v -> Spec+specOrd = makeSpec $ do+    it "prop_compare_filterKeys" $+        prop_compare_filterKeys+            @k @v & property+    it "prop_compare_get" $+        prop_compare_get+            @k @v & property+    it "prop_compare_singleton" $+        prop_compare_singleton+            @k @v & property+    it "prop_compare_unionWith_max" $+        prop_compare_unionWith_max+            @k @v & property+    it "prop_compare_unionWith_min" $+        prop_compare_unionWith_min+            @k @v & property++specOrdLeftInvariant+    :: forall k v. (Test k v, Ord v) => Proxy k -> Proxy v -> Spec+specOrdLeftInvariant = makeSpec $ do+    it "prop_compare_append_left" $+        prop_compare_append_left+            @k @v & property++specOrdRightInvariant+    :: forall k v. (Test k v, Ord v) => Proxy k -> Proxy v -> Spec+specOrdRightInvariant = makeSpec $ do+    it "prop_compare_append_right" $+        prop_compare_append_right+            @k @v & property++prop_compare_append_left+    :: (Test k v, Ord v)+    => MonoidMap k v+    -> MonoidMap k v+    -> MonoidMap k v+    -> Property+prop_compare_append_left m m1 m2 =+    MonoidMap.compare (m <> m1) (m <> m2)+        ===+        result+    & cover 8+        (result == LT)+        "result == LT"+    & cover 2+        (result == EQ)+        "result == EQ"+    & cover 8+        (result == GT)+        "result == GT"+    & cover 8+        (MonoidMap.nonNull m)+        "MonoidMap.nonNull m"+  where+    result = MonoidMap.compare m1 m2++prop_compare_append_right+    :: (Test k v, Ord v)+    => MonoidMap k v+    -> MonoidMap k v+    -> MonoidMap k v+    -> Property+prop_compare_append_right m m1 m2 =+    MonoidMap.compare (m1 <> m) (m2 <> m)+        ===+        result+    & cover 8+        (result == LT)+        "result == LT"+    & cover 2+        (result == EQ)+        "result == EQ"+    & cover 8+        (result == GT)+        "result == GT"+    & cover 8+        (MonoidMap.nonNull m)+        "MonoidMap.nonNull m"+  where+    result = MonoidMap.compare m1 m2++prop_compare_filterKeys+    :: (Test k v, Ord v)+    => k+    -> MonoidMap k v+    -> MonoidMap k v+    -> Property+prop_compare_filterKeys k m1 m2 =+    MonoidMap.compare m1 m2+        ===+        MonoidMap.compare m1LT m2LT <> MonoidMap.compare m1GE m2GE+    & cover 8+        (m1LT /= m2LT)+        "m1LT /= m2LT"+    & cover 8+        (m1LT == m2LT && m1GE /= m2GE)+        "m1LT == m2LT && m1GE /= m2GE"+  where+    m1LT = MonoidMap.filterKeys (<  k) m1+    m1GE = MonoidMap.filterKeys (>= k) m1+    m2LT = MonoidMap.filterKeys (<  k) m2+    m2GE = MonoidMap.filterKeys (>= k) m2++prop_compare_get+    :: (Test k v, Ord v)+    => MonoidMap k v+    -> MonoidMap k v+    -> Property+prop_compare_get m1 m2 =+    result+        ===+        foldMap+            (\k -> compare (MonoidMap.get k m1) (MonoidMap.get k m2))+            (MonoidMap.nonNullKeys m1 <> MonoidMap.nonNullKeys m2)+    & cover 4+        (result == LT)+        "result == LT"+    & cover 1+        (result == EQ)+        "result == EQ"+    & cover 4+        (result == GT)+        "result == GT"+    & cover 4+        (decidingKeyNullInL && decidingKeyNonNullInR)+        "decidingKeyNullInL && decidingKeyNonNullInR"+    & cover 4+        (decidingKeyNonNullInL && decidingKeyNullInR)+        "decidingKeyNonNullInL && decidingKeyNullInR"+    & cover 4+        (decidingKeyNonNullInL && decidingKeyNonNullInR)+        "decidingKeyNonNullInL && decidingKeyNonNullInR"+  where+    result = MonoidMap.compare m1 m2+    -- The smallest key for which the two maps have different values:+    decidingKey =+        Set.lookupMin+            $ Set.filter (\k -> MonoidMap.get k m1 /= MonoidMap.get k m2)+            $ MonoidMap.nonNullKeys m1 <> MonoidMap.nonNullKeys m2+    decidingKeyNullInL    = any (`MonoidMap.nullKey`    m1) decidingKey+    decidingKeyNullInR    = any (`MonoidMap.nullKey`    m2) decidingKey+    decidingKeyNonNullInL = any (`MonoidMap.nonNullKey` m1) decidingKey+    decidingKeyNonNullInR = any (`MonoidMap.nonNullKey` m2) decidingKey++prop_compare_singleton+    :: (Test k v, Ord v)+    => k+    -> v+    -> v+    -> Property+prop_compare_singleton k v1 v2 =+    MonoidMap.compare (MonoidMap.singleton k v1) (MonoidMap.singleton k v2)+        ===+        compare v1 v2+    & cover 1+        (v1 == mempty && v2 /= mempty)+        "v1 == mempty && v2 /= mempty"+    & cover 1+        (v1 /= mempty && v2 == mempty)+        "v1 /= mempty && v2 == mempty"+    & cover 1+        (v1 /= mempty && v2 /= mempty)+        "v1 /= mempty && v2 /= mempty"++-- If every value in map 'a' is less than or equal to the matching value in+-- map 'b', then 'a' must not be greater than 'b'.+--+-- Every such pair of maps (a, b) can be expressed as (m1, unionWith max m1 m2)+-- for some pair of maps (m1, m2), so this property covers all such pairs.+--+prop_compare_unionWith_max+    :: (Test k v, Ord v)+    => MonoidMap k v+    -> MonoidMap k v+    -> Property+prop_compare_unionWith_max m1 m2 =+    conjoin+        [ MonoidMap.compare m1 m =/= GT+        , MonoidMap.compare m2 m =/= GT+        ]+    & cover 8+        (m /= m1 && m /= m2)+        "m /= m1 && m /= m2"+    & cover 2+        (m == m1 && m /= m2)+        "m == m1 && m /= m2"+    & cover 2+        (m /= m1 && m == m2)+        "m /= m1 && m == m2"+  where+    m = MonoidMap.unionWith max m1 m2++-- If every value in map 'a' is less than or equal to the matching value in+-- map 'b', then 'a' must not be greater than 'b'.+--+-- Every such pair of maps (a, b) can be expressed as (unionWith min m1 m2, m1)+-- for some pair of maps (m1, m2), so this property covers all such pairs.+--+prop_compare_unionWith_min+    :: (Test k v, Ord v)+    => MonoidMap k v+    -> MonoidMap k v+    -> Property+prop_compare_unionWith_min m1 m2 =+    conjoin+        [ MonoidMap.compare m m1 =/= GT+        , MonoidMap.compare m m2 =/= GT+        ]+    & cover 8+        (m /= m1 && m /= m2)+        "m /= m1 && m /= m2"+    & cover 2+        (m == m1 && m /= m2)+        "m == m1 && m /= m2"+    & cover 2+        (m /= m1 && m == m2)+        "m /= m1 && m == m2"+  where+    m = MonoidMap.unionWith min m1 m2  prop_disjoint_gcd     :: (Test k v, GCDMonoid v)
components/monoidmap-test/Data/MonoidMap/ExampleSpec.hs view
@@ -67,6 +67,7 @@      describe "Comparison" $ do +        exampleSpec_compare_Sum_Natural         exampleSpec_isSubmapOf_Sum_Natural         exampleSpec_disjoint_Product_Natural         exampleSpec_disjoint_Sum_Natural@@ -196,6 +197,46 @@ -------------------------------------------------------------------------------- -- Comparison --------------------------------------------------------------------------------++exampleSpec_compare_Sum_Natural :: Spec+exampleSpec_compare_Sum_Natural = unitTestSpec+    "MonoidMap.compare (Sum Natural)"+    "MonoidMap.compare"+    (MonoidMap.compare)+    (exampleData_compare_Sum_Natural)++exampleData_compare_Sum_Natural :: UnitTestData2+    (MonoidMap LatinChar (Sum Natural))+    (MonoidMap LatinChar (Sum Natural))+    (Ordering)+exampleData_compare_Sum_Natural = unitTestData2+    [ ( m [0, 0, 0]+      , m [0, 0, 0]+      , EQ+      )+    , ( m [1, 2, 3]+      , m [1, 2, 3]+      , EQ+      )+    , ( m [1, 2, 3]+      , m [1, 3, 2]+      , LT+      )+    , ( m [1, 3, 2]+      , m [1, 2, 3]+      , GT+      )+    , ( m [1, 0, 3]+      , m [1, 2, 3]+      , LT+      )+    , ( m [1, 2, 3]+      , m [1, 0, 3]+      , GT+      )+    ]+  where+    m = MonoidMap.fromList . zip [A ..]  exampleSpec_isSubmapOf_Sum_Natural :: Spec exampleSpec_isSubmapOf_Sum_Natural = unitTestSpec
components/monoidmap-test/Test/Combinators/NonZero.hs view
@@ -26,7 +26,7 @@  -- | A combinator for non-zero values. newtype NonZero a = NonZero a-    deriving newtype (Eq, Num, Read, Show)+    deriving newtype (Eq, Num, Ord, Read, Show)     deriving newtype (Semigroup, Commutative, Monoid, MonoidNull, Group)  genNonZero :: (Eq a, Num a) => Gen a -> Gen (NonZero a)
components/monoidmap-test/Test/Common.hs view
@@ -15,6 +15,9 @@     , TestKey     , TestValueType (..)     , testValueTypesAll+    , testValueTypesOrd+    , testValueTypesOrdLeftInvariant+    , testValueTypesOrdRightInvariant     , testValueTypesGroup     , testValueTypesMonus     , testValueTypesLeftReductive@@ -198,6 +201,60 @@     , TestValueType (Proxy @[Int])     , TestValueType (Proxy @[Natural])     , TestValueType (Proxy @(MonoidMap SmallKey (Sum Int)))+    , TestValueType (Proxy @(MonoidMap SmallKey (Sum Natural)))+    ]++testValueTypesOrd :: [TestValueType Ord]+testValueTypesOrd =+    [ TestValueType (Proxy @(Dual Text))+    , TestValueType (Proxy @(Dual [Int]))+    , TestValueType (Proxy @(Dual [Natural]))+    , TestValueType (Proxy @(Product Int))+    , TestValueType (Proxy @(Product Natural))+    , TestValueType (Proxy @(Set Int))+    , TestValueType (Proxy @(Set Natural))+    , TestValueType (Proxy @(Sum Int))+    , TestValueType (Proxy @(Sum Natural))+    , TestValueType (Proxy @(Text))+    , TestValueType (Proxy @[Int])+    , TestValueType (Proxy @[Natural])+    , TestValueType (Proxy @(MonoidMap SmallKey (Sum Int)))+    , TestValueType (Proxy @(MonoidMap SmallKey (Sum Natural)))+    ]++-- Value types for which appending the same prefix @v@ to values @v1@ and @v2@+-- preserves their ordering:+--+-- @+-- ∀ v v1 v2. compare (v <> v1) (v <> v2) == compare v1 v2+-- @+--+testValueTypesOrdLeftInvariant :: [TestValueType Ord]+testValueTypesOrdLeftInvariant =+    [ TestValueType (Proxy @(Text))+    , TestValueType (Proxy @[Integer])+    , TestValueType (Proxy @[Natural])+    , TestValueType (Proxy @(Sum Integer))+    , TestValueType (Proxy @(Sum Natural))+    , TestValueType (Proxy @(MonoidMap SmallKey (Sum Integer)))+    , TestValueType (Proxy @(MonoidMap SmallKey (Sum Natural)))+    ]++-- Value types for which appending the same suffix @v@ to values @v1@ and @v2@+-- preserves their ordering:+--+-- @+-- ∀ v v1 v2. compare (v1 <> v) (v2 <> v) == compare v1 v2+-- @+--+testValueTypesOrdRightInvariant :: [TestValueType Ord]+testValueTypesOrdRightInvariant =+    [ TestValueType (Proxy @(Dual Text))+    , TestValueType (Proxy @(Dual [Integer]))+    , TestValueType (Proxy @(Dual [Natural]))+    , TestValueType (Proxy @(Sum Integer))+    , TestValueType (Proxy @(Sum Natural))+    , TestValueType (Proxy @(MonoidMap SmallKey (Sum Integer)))     , TestValueType (Proxy @(MonoidMap SmallKey (Sum Natural)))     ] 
components/monoidmap/Data/MonoidMap.hs view
@@ -120,6 +120,7 @@     , power      -- ** Comparison+    , compare     , isSubmapOf     , isSubmapOfBy     , disjoint@@ -156,7 +157,8 @@     where  import Prelude hiding-    ( drop+    ( compare+    , drop     , filter     , foldl     , foldl'@@ -255,6 +257,7 @@ import qualified Data.MonoidMap.Internal.NonNull as NonNull import qualified Data.MonoidMap.Internal.NonNullMap as NonNullMap import qualified Data.MonoidMap.Internal.NonNullMap.Merge as Merge+import qualified Data.Ord as C import qualified Data.Semigroup.Cancellative as C import qualified Data.Set as Set import qualified Data.Traversable as Traversable@@ -675,6 +678,17 @@ #endif  --------------------------------------------------------------------------------+-- Instances: Ord+--------------------------------------------------------------------------------++-- | @since 0.1.5.0+instance (Ord k, Ord v, Monoid v) =>+    Ord (MonoidMap k v)+  where+    compare = compare+    {-# INLINE compare #-}++-------------------------------------------------------------------------------- -- Instances: Semigroup and subclasses -------------------------------------------------------------------------------- @@ -1937,6 +1951,113 @@ -------------------------------------------------------------------------------- -- Comparison --------------------------------------------------------------------------------++-- | Compares a pair of maps /lexicographically/, in ascending key order.+--+-- This function provides the definition of 'C.compare' for the 'MonoidMap'+-- instance of 'Ord'.+--+-- The result of comparing maps __@m1@__ and __@m2@__ is determined by the+-- /smallest/ key __@k@__ for which the values in __@m1@__ and __@m2@__ are+-- /different/, and is equal to the result of comparing those two values. If+-- there is no such key, then the result is 'EQ'.+--+-- Satisfies the following property:+--+-- @+-- 'compare' m1 m2 '=='+--     'foldMap'+--         (\\k -> 'C.compare' ('get' k m1) ('get' k m2))+--         ('nonNullKeys' m1 '<>' 'nonNullKeys' m2)+-- @+--+-- Comparing a pair of 'singleton' maps for the same key __@k@__ is equivalent+-- to comparing their values:+--+-- @+-- 'compare' ('singleton' k v1) ('singleton' k v2) '==' 'C.compare' v1 v2+-- @+--+-- For any key __@k@__, comparing a pair of maps is equivalent to first+-- comparing their values for keys /less than/ __@k@__, and then comparing+-- their values for all remaining keys:+--+-- @+-- 'compare' m1 m2 '=='+--     'compare' ('filterKeys' ('<'  k) m1) ('filterKeys' ('<'  k) m2) '<>'+--     'compare' ('filterKeys' ('>=' k) m1) ('filterKeys' ('>=' k) m2)+-- @+--+-- === __Examples__+--+-- With 'Sum' 'Natural' values:+--+-- Maps that have the same value for every key are equal:+--+-- @+-- >>> m1 = 'fromList' [("a", 1), ("b", 2), ("c", 3)]+-- >>> m2 = 'fromList' [("a", 1), ("b", 2), ("c", 3)]+-- >>> 'compare' m1 m2+-- 'EQ'+-- @+--+-- The smallest key with different values determines the result, regardless+-- of the values for greater keys:+--+-- @+-- >>> m1 = 'fromList' [("a", 1), ("b", 2), ("c", 3)]+-- >>> m2 = 'fromList' [("a", 1), ("b", 3), ("c", 2)]+-- >>> 'compare' m1 m2+-- 'LT'+-- @+--+-- @+-- >>> m1 = 'fromList' [("a", 1), ("b", 3), ("c", 2)]+-- >>> m2 = 'fromList' [("a", 1), ("b", 2), ("c", 3)]+-- >>> 'compare' m1 m2+-- 'GT'+-- @+--+-- A value of 'mempty' is compared in the same way as any other value:+--+-- @+-- >>> m1 = 'fromList' [("a", 1),           ("c", 3)]+-- >>> m2 = 'fromList' [("a", 1), ("b", 2), ("c", 3)]+-- >>> 'compare' m1 m2+-- 'LT'+-- @+--+-- @+-- >>> m1 = 'fromList' [("a", 1), ("b", 2), ("c", 3)]+-- >>> m2 = 'fromList' [("a", 1),           ("c", 3)]+-- >>> 'compare' m1 m2+-- 'GT'+-- @+--+-- @since 0.1.5.0+--+compare+    :: (Ord k, Ord v, Monoid v)+    => MonoidMap k v+    -> MonoidMap k v+    -> Ordering+compare m1 m2 = go (toList m1) (toList m2)+  where+    go    (         [])    (         []) = EQ+    go    ((_, x) : ps)    (         []) = check (C.compare x z) ps []+    go    (         [])    ((_, y) : qs) = check (C.compare z y) [] qs+    go as@((a, x) : ps) bs@((b, y) : qs) = align (C.compare a b)+      where+        align EQ                         = check (C.compare x y) ps qs+        align LT                         = check (C.compare x z) ps bs+        align GT                         = check (C.compare z y) as qs++    check EQ ps qs = go ps qs+    check LT _  _  = LT+    check GT _  _  = GT++    z = mempty+{-# INLINE compare #-}  -- | Indicates whether or not the first map is a /submap/ of the second. --
monoidmap.cabal view
@@ -1,6 +1,6 @@ cabal-version:  3.0 name:           monoidmap-version:        0.1.4.0+version:        0.1.5.0 homepage:       https://github.com/jonathanknowles/monoidmap bug-reports:    https://github.com/jonathanknowles/monoidmap/issues license:        Apache-2.0