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 +8/−0
- components/monoidmap-test/Data/MonoidMap/ClassSpec.hs +12/−0
- components/monoidmap-test/Data/MonoidMap/ComparisonSpec.hs +247/−1
- components/monoidmap-test/Data/MonoidMap/ExampleSpec.hs +41/−0
- components/monoidmap-test/Test/Combinators/NonZero.hs +1/−1
- components/monoidmap-test/Test/Common.hs +57/−0
- components/monoidmap/Data/MonoidMap.hs +122/−1
- monoidmap.cabal +1/−1
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