monoid-subclasses 1.2.2 → 1.2.3
raw patch · 6 files changed
+622/−76 lines, 6 files
Files
- CHANGELOG.md +4/−0
- Test/TestMonoidSubclasses.hs +283/−34
- monoid-subclasses.cabal +17/−7
- src/Data/Monoid/GCD.hs +249/−14
- src/Data/Monoid/LCM.hs +51/−21
- src/Data/Monoid/Monus.hs +18/−0
CHANGELOG.md view
@@ -1,3 +1,7 @@+Version 1.2.3+---------------+* Add `DistributiveGCDMonoid` and `DistributiveLCMMonoid` type class by Jonathan Knowles+ Version 1.2.2 --------------- * Add `Data.Monoid.LCM` module with `LCMMonoid` type class by Jonathan Knowles
Test/TestMonoidSubclasses.hs view
@@ -71,10 +71,24 @@ import Data.Monoid.Null (MonoidNull, PositiveMonoid, null) import Data.Monoid.Factorial (FactorialMonoid, splitPrimePrefix, splitPrimeSuffix, inits, tails, span, spanMaybe, split, splitAt)-import Data.Monoid.GCD (GCDMonoid, LeftGCDMonoid, RightGCDMonoid, gcd,- commonPrefix, stripCommonPrefix,- commonSuffix, stripCommonSuffix)-import Data.Monoid.LCM (LCMMonoid, lcm)+import Data.Monoid.GCD+ ( GCDMonoid+ , LeftGCDMonoid+ , RightGCDMonoid+ , DistributiveGCDMonoid+ , LeftDistributiveGCDMonoid+ , RightDistributiveGCDMonoid+ , commonPrefix+ , commonSuffix+ , gcd+ , stripCommonPrefix+ , stripCommonSuffix+ )+import Data.Monoid.LCM+ ( LCMMonoid+ , DistributiveLCMMonoid+ , lcm+ ) import Data.Monoid.Monus (OverlappingGCDMonoid, Monus, (<\>), overlap, stripOverlap, stripPrefixOverlap, stripSuffixOverlap) import Data.Monoid.Textual (TextualMonoid)@@ -97,8 +111,11 @@ | LeftGCDTest (LeftGCDMonoidInstance -> Property) | RightGCDTest (RightGCDMonoidInstance -> Property) | GCDTest (GCDMonoidInstance -> Property)- | CancellativeGCDTest (CancellativeGCDMonoidInstance -> Property)+ | DistributiveGCDTest (DistributiveGCDMonoidInstance -> Property)+ | LeftDistributiveGCDTest (LeftDistributiveGCDMonoidInstance -> Property)+ | RightDistributiveGCDTest (RightDistributiveGCDMonoidInstance -> Property) | LCMTest (LCMMonoidInstance -> Property)+ | DistributiveLCMTest (DistributiveLCMMonoidInstance -> Property) data CommutativeMonoidInstance = forall a. (Arbitrary a, Show a, Eq a, Commutative a, Monoid a) => CommutativeMonoidInstance a@@ -139,11 +156,27 @@ RightGCDMonoidInstance a data GCDMonoidInstance = forall a. (Arbitrary a, Show a, Eq a, GCDMonoid a) => GCDMonoidInstance a-data CancellativeGCDMonoidInstance = forall a. (Arbitrary a, Show a, Eq a, Monoid a, Cancellative a, GCDMonoid a) =>- CancellativeGCDMonoidInstance a-data LCMMonoidInstance = forall a. (Arbitrary a, Show a, Eq a, LCMMonoid a) =>- LCMMonoidInstance a +data DistributiveGCDMonoidInstance =+ forall a. (Arbitrary a, Show a, Eq a, DistributiveGCDMonoid a)+ => DistributiveGCDMonoidInstance a++data LeftDistributiveGCDMonoidInstance =+ forall a. (Arbitrary a, Show a, Eq a, LeftDistributiveGCDMonoid a)+ => LeftDistributiveGCDMonoidInstance a++data RightDistributiveGCDMonoidInstance =+ forall a. (Arbitrary a, Show a, Eq a, RightDistributiveGCDMonoid a)+ => RightDistributiveGCDMonoidInstance a++data LCMMonoidInstance =+ forall a. (Arbitrary a, Show a, Eq a, LCMMonoid a)+ => LCMMonoidInstance a++data DistributiveLCMMonoidInstance =+ forall a. (Arbitrary a, Show a, Eq a, DistributiveLCMMonoid a)+ => DistributiveLCMMonoidInstance a+ commutativeInstances :: [CommutativeMonoidInstance] commutativeInstances = map upcast reductiveInstances ++ [CommutativeMonoidInstance (mempty :: Product Double)]@@ -324,9 +357,7 @@ RightCancellativeMonoidInstance (mempty :: Vector Int)] where upcast (CancellativeMonoidInstance i) = RightCancellativeMonoidInstance i -cancellativeInstances = map upcast cancellativeGCDInstances- ++ []- where upcast (CancellativeGCDMonoidInstance i) = CancellativeMonoidInstance i+cancellativeInstances = [CancellativeMonoidInstance ()] leftGCDInstances = map upcast gcdInstances ++ [LeftGCDMonoidInstance (mempty :: String),@@ -365,15 +396,88 @@ RightGCDMonoidInstance (mempty :: Concat (Dual Text))] where upcast (GCDMonoidInstance i) = RightGCDMonoidInstance i -gcdInstances = map upcast cancellativeGCDInstances- ++ [GCDMonoidInstance (mempty :: Product Natural),- GCDMonoidInstance (mempty :: Dual (Product Natural)),- GCDMonoidInstance (mempty :: IntSet),- GCDMonoidInstance (mempty :: Set String)]- where upcast (CancellativeGCDMonoidInstance i) = GCDMonoidInstance i+gcdInstances =+ [ GCDMonoidInstance (mempty :: ())+ , GCDMonoidInstance (mempty :: Product Natural)+ , GCDMonoidInstance (mempty :: Dual (Product Natural))+ , GCDMonoidInstance (mempty :: IntSet)+ , GCDMonoidInstance (mempty :: Set String)+ ] -cancellativeGCDInstances = [CancellativeGCDMonoidInstance ()]+distributiveGCDMonoidInstances :: [DistributiveGCDMonoidInstance]+distributiveGCDMonoidInstances =+ [ DistributiveGCDMonoidInstance (mempty :: ())+ , DistributiveGCDMonoidInstance (mempty :: Product Natural)+ , DistributiveGCDMonoidInstance (mempty :: Sum Natural)+ , DistributiveGCDMonoidInstance (mempty :: IntSet)+ , DistributiveGCDMonoidInstance (mempty :: Set ())+ , DistributiveGCDMonoidInstance (mempty :: Set Bool)+ , DistributiveGCDMonoidInstance (mempty :: Set Word)+ , DistributiveGCDMonoidInstance (mempty :: Dual (Set ()))+ , DistributiveGCDMonoidInstance (mempty :: Dual (Set Bool))+ , DistributiveGCDMonoidInstance (mempty :: Dual (Set Word))+ ] +leftDistributiveGCDMonoidInstances :: [LeftDistributiveGCDMonoidInstance]+leftDistributiveGCDMonoidInstances =+ [ -- Instances for non-commutative monoids:+ LeftDistributiveGCDMonoidInstance (mempty :: [()])+ , LeftDistributiveGCDMonoidInstance (mempty :: [Bool])+ , LeftDistributiveGCDMonoidInstance (mempty :: [Word])+ , LeftDistributiveGCDMonoidInstance (mempty :: Seq ())+ , LeftDistributiveGCDMonoidInstance (mempty :: Seq Bool)+ , LeftDistributiveGCDMonoidInstance (mempty :: Seq Word)+ , LeftDistributiveGCDMonoidInstance (mempty :: Vector ())+ , LeftDistributiveGCDMonoidInstance (mempty :: Vector Bool)+ , LeftDistributiveGCDMonoidInstance (mempty :: Vector Word)+ , LeftDistributiveGCDMonoidInstance (mempty :: ByteString)+ , LeftDistributiveGCDMonoidInstance (mempty :: Lazy.ByteString)+ , LeftDistributiveGCDMonoidInstance (mempty :: Text)+ , LeftDistributiveGCDMonoidInstance (mempty :: Lazy.Text)+ -- Instances for commutative monoids:+ , LeftDistributiveGCDMonoidInstance (mempty :: ())+ , LeftDistributiveGCDMonoidInstance (mempty :: Product Natural)+ , LeftDistributiveGCDMonoidInstance (mempty :: Sum Natural)+ , LeftDistributiveGCDMonoidInstance (mempty :: IntSet)+ , LeftDistributiveGCDMonoidInstance (mempty :: Set ())+ , LeftDistributiveGCDMonoidInstance (mempty :: Set Bool)+ , LeftDistributiveGCDMonoidInstance (mempty :: Set Word)+ -- Instances for monoid transformers:+ , LeftDistributiveGCDMonoidInstance (mempty :: Dual [()])+ , LeftDistributiveGCDMonoidInstance (mempty :: Dual [Bool])+ , LeftDistributiveGCDMonoidInstance (mempty :: Dual [Word])+ ]++rightDistributiveGCDMonoidInstances :: [RightDistributiveGCDMonoidInstance]+rightDistributiveGCDMonoidInstances =+ [ -- Instances for non-commutative monoids:+ RightDistributiveGCDMonoidInstance (mempty :: [()])+ , RightDistributiveGCDMonoidInstance (mempty :: [Bool])+ , RightDistributiveGCDMonoidInstance (mempty :: [Word])+ , RightDistributiveGCDMonoidInstance (mempty :: Seq ())+ , RightDistributiveGCDMonoidInstance (mempty :: Seq Bool)+ , RightDistributiveGCDMonoidInstance (mempty :: Seq Word)+ , RightDistributiveGCDMonoidInstance (mempty :: Vector ())+ , RightDistributiveGCDMonoidInstance (mempty :: Vector Bool)+ , RightDistributiveGCDMonoidInstance (mempty :: Vector Word)+ , RightDistributiveGCDMonoidInstance (mempty :: ByteString)+ , RightDistributiveGCDMonoidInstance (mempty :: Lazy.ByteString)+ , RightDistributiveGCDMonoidInstance (mempty :: Text)+ , RightDistributiveGCDMonoidInstance (mempty :: Lazy.Text)+ -- Instances for commutative monoids:+ , RightDistributiveGCDMonoidInstance (mempty :: ())+ , RightDistributiveGCDMonoidInstance (mempty :: Product Natural)+ , RightDistributiveGCDMonoidInstance (mempty :: Sum Natural)+ , RightDistributiveGCDMonoidInstance (mempty :: IntSet)+ , RightDistributiveGCDMonoidInstance (mempty :: Set ())+ , RightDistributiveGCDMonoidInstance (mempty :: Set Bool)+ , RightDistributiveGCDMonoidInstance (mempty :: Set Word)+ -- Instances for monoid transformers:+ , RightDistributiveGCDMonoidInstance (mempty :: Dual [()])+ , RightDistributiveGCDMonoidInstance (mempty :: Dual [Bool])+ , RightDistributiveGCDMonoidInstance (mempty :: Dual [Word])+ ]+ lcmInstances = [LCMMonoidInstance (mempty :: Product Natural), LCMMonoidInstance (mempty :: Sum Natural),@@ -390,6 +494,18 @@ LCMMonoidInstance (mempty :: Set Ordering), LCMMonoidInstance (mempty :: Set Word8)] +distributiveLCMInstances =+ [ DistributiveLCMMonoidInstance (mempty :: ())+ , DistributiveLCMMonoidInstance (mempty :: Product Natural)+ , DistributiveLCMMonoidInstance (mempty :: Sum Natural)+ , DistributiveLCMMonoidInstance (mempty :: IntSet)+ , DistributiveLCMMonoidInstance (mempty :: Set ())+ , DistributiveLCMMonoidInstance (mempty :: Set Bool)+ , DistributiveLCMMonoidInstance (mempty :: Set Word)+ , DistributiveLCMMonoidInstance (mempty :: Dual (Product Natural))+ , DistributiveLCMMonoidInstance (mempty :: Dual (Sum Natural))+ ]+ main = defaultMain (testGroup "MonoidSubclasses" $ map expand tests) where expand (name, test) = testProperty name (foldr1 (.&&.) $ checkInstances test) @@ -411,8 +527,11 @@ checkInstances (LeftGCDTest checkType) = (map checkType leftGCDInstances) checkInstances (RightGCDTest checkType) = (map checkType rightGCDInstances) checkInstances (GCDTest checkType) = (map checkType gcdInstances) -checkInstances (CancellativeGCDTest checkType) = (map checkType cancellativeGCDInstances) +checkInstances (DistributiveGCDTest checkType) = (map checkType distributiveGCDMonoidInstances)+checkInstances (LeftDistributiveGCDTest checkType) = (map checkType leftDistributiveGCDMonoidInstances)+checkInstances (RightDistributiveGCDTest checkType) = (map checkType rightDistributiveGCDMonoidInstances) checkInstances (LCMTest checkType) = (map checkType lcmInstances)+checkInstances (DistributiveLCMTest checkType) = (map checkType distributiveLCMInstances) tests :: [(String, Test)] tests = [("CommutativeMonoid", CommutativeTest checkCommutative),@@ -484,6 +603,9 @@ ("overlap law 1", OverlappingGCDTest checkOverlapLaw1), ("overlap law 2", OverlappingGCDTest checkOverlapLaw2), ("overlap law 3", OverlappingGCDTest checkOverlapLaw3),+ ("overlap idempotence", OverlappingGCDTest checkOverlap_idempotence),+ ("overlap identity (left)", OverlappingGCDTest checkOverlap_identity_left),+ ("overlap identity (right)", OverlappingGCDTest checkOverlap_identity_right), ("isPrefixOf", LeftReductiveTest checkIsPrefixOf), ("stripSuffix", RightReductiveTest checkStripSuffix), ("isSuffixOf", RightReductiveTest checkIsSuffixOf),@@ -500,7 +622,26 @@ ("stripCommonSuffix 3", RightGCDTest checkStripCommonSuffix3), ("stripCommonSuffix 4", RightGCDTest checkStripCommonSuffix4), ("gcd", GCDTest checkGCD),- ("cancellative gcd", CancellativeGCDTest checkCancellativeGCD),+ ("gcd uniqueness", GCDTest checkGCD_uniqueness),+ ("gcd idempotence", GCDTest checkGCD_idempotence),+ ("gcd identity (left)", GCDTest checkGCD_identity_left),+ ("gcd identity (right)", GCDTest checkGCD_identity_right),+ ("gcd commutativity", GCDTest checkGCD_commutativity),+ ("gcd associativity", GCDTest checkGCD_associativity),+ ("gcd distributivity (left)", DistributiveGCDTest checkGCD_distributivity_left),+ ("gcd distributivity (right)", DistributiveGCDTest checkGCD_distributivity_right),+ ("commonPrefix idempotence", LeftGCDTest checkCommonPrefix_idempotence),+ ("commonPrefix identity (left)", LeftGCDTest checkCommonPrefix_identity_left),+ ("commonPrefix identity (right)", LeftGCDTest checkCommonPrefix_identity_right),+ ("commonPrefix commutativity", LeftGCDTest checkCommonPrefix_commutativity),+ ("commonPrefix associativity", LeftGCDTest checkCommonPrefix_associativity),+ ("commonPrefix distributivity", LeftDistributiveGCDTest checkCommonPrefix_distributivity),+ ("commonSuffix idempotence", RightGCDTest checkCommonSuffix_idempotence),+ ("commonSuffix identity (left)", RightGCDTest checkCommonSuffix_identity_left),+ ("commonSuffix identity (right)", RightGCDTest checkCommonSuffix_identity_right),+ ("commonSuffix commutativity", RightGCDTest checkCommonSuffix_commutativity),+ ("commonSuffix associativity", RightGCDTest checkCommonSuffix_associativity),+ ("commonSuffix distributivity", RightDistributiveGCDTest checkCommonSuffix_distributivity), ("lcm reductivity (left)", LCMTest checkLCM_reductivity_left), ("lcm reductivity (right)", LCMTest checkLCM_reductivity_right), ("lcm uniqueness", LCMTest checkLCM_uniqueness),@@ -511,10 +652,10 @@ ("lcm associativity", LCMTest checkLCM_associativity), ("lcm absorption (gcd-lcm)", LCMTest checkLCM_absorption_gcd_lcm), ("lcm absorption (lcm-gcd)", LCMTest checkLCM_absorption_lcm_gcd),- ("lcm distributivity (left)", LCMTest checkLCM_distributivity_left),- ("lcm distributivity (right)", LCMTest checkLCM_distributivity_right),- ("lcm distributivity (gcd-lcm)", LCMTest checkLCM_distributivity_gcd_lcm),- ("lcm distributivity (lcm-gcd)", LCMTest checkLCM_distributivity_lcm_gcd)+ ("lcm distributivity (left)", DistributiveLCMTest checkLCM_distributivity_left),+ ("lcm distributivity (right)", DistributiveLCMTest checkLCM_distributivity_right),+ ("lcm distributivity (gcd-lcm)", DistributiveLCMTest checkLCM_distributivity_gcd_lcm),+ ("lcm distributivity (lcm-gcd)", DistributiveLCMTest checkLCM_distributivity_lcm_gcd) ] checkCommutative (CommutativeMonoidInstance (e :: a)) = forAll (arbitrary :: Gen (a, a)) (\(a, b)-> a <> b == b <> a)@@ -829,6 +970,15 @@ checkOverlapLaw3 (OverlappingGCDMonoidInstance (_ :: a)) = forAll (arbitrary :: Gen (a, a)) check where check (a, b) = overlap a b <> stripPrefixOverlap a b == b +checkOverlap_idempotence (OverlappingGCDMonoidInstance (_ :: a)) =+ forAll (arbitrary :: Gen a) $ \a -> overlap a a === a++checkOverlap_identity_left (OverlappingGCDMonoidInstance (_ :: a)) =+ forAll (arbitrary :: Gen a) $ \a -> overlap mempty a === mempty++checkOverlap_identity_right (OverlappingGCDMonoidInstance (_ :: a)) =+ forAll (arbitrary :: Gen a) $ \a -> overlap a mempty === mempty+ checkStripPrefixOverlap1 (OverlappingGCDMonoidInstance (_ :: a)) = forAll (arbitrary :: Gen (a, a)) check where check (a, b) = o `isSuffixOf` b && b `isSuffixOf` (a <> o) where o = stripPrefixOverlap a b@@ -914,12 +1064,111 @@ && isJust (b </> d) where d = gcd a b -checkCancellativeGCD (CancellativeGCDMonoidInstance (_ :: a)) = forAll (arbitrary :: Gen (a, a, a)) check- where check (a, b, c) = commonPrefix (a <> b) (a <> c) == a <> (commonPrefix b c)- && commonSuffix (a <> c) (b <> c) == (commonSuffix a b) <> c- && gcd (a <> b) (a <> c) == a <> gcd b c- && gcd (a <> c) (b <> c) == gcd a b <> c+checkGCD_uniqueness+ (GCDMonoidInstance (_ :: a)) =+ forAll (arbitrary :: Gen (a, a, a)) $+ \(a, b, c) ->+ all isJust [a </> c, b </> c, c </> gcd a b] === (gcd a b == c) +checkGCD_idempotence+ (GCDMonoidInstance (_ :: a)) =+ forAll (arbitrary :: Gen a) $+ \a -> gcd a a === a++checkGCD_identity_left+ (GCDMonoidInstance (_ :: a)) =+ forAll (arbitrary :: Gen a) $+ \a -> gcd mempty a === mempty++checkGCD_identity_right+ (GCDMonoidInstance (_ :: a)) =+ forAll (arbitrary :: Gen a) $+ \a -> gcd a mempty === mempty++checkGCD_commutativity+ (GCDMonoidInstance (_ :: a)) =+ forAll (arbitrary :: Gen (a, a)) $+ \a b -> gcd a b === gcd b a++checkGCD_associativity+ (GCDMonoidInstance (_ :: a)) =+ forAll (arbitrary :: Gen (a, a, a)) $+ \a b c -> gcd a (gcd b c) === gcd (gcd a b) c++checkGCD_distributivity_left+ (DistributiveGCDMonoidInstance (_ :: a)) =+ forAll (arbitrary :: Gen (a, a, a)) $+ \(a, b, c) -> gcd (a <> b) (a <> c) == a <> gcd b c++checkGCD_distributivity_right+ (DistributiveGCDMonoidInstance (_ :: a)) =+ forAll (arbitrary :: Gen (a, a, a)) $+ \(a, b, c) -> gcd (a <> c) (b <> c) == gcd a b <> c++checkCommonPrefix_idempotence+ (LeftGCDMonoidInstance (_ :: a)) =+ forAll (arbitrary :: Gen a) $+ \a -> commonPrefix a a === a++checkCommonPrefix_identity_left+ (LeftGCDMonoidInstance (_ :: a)) =+ forAll (arbitrary :: Gen a) $+ \a -> commonPrefix mempty a === mempty++checkCommonPrefix_identity_right+ (LeftGCDMonoidInstance (_ :: a)) =+ forAll (arbitrary :: Gen a) $+ \a -> commonPrefix a mempty === mempty++checkCommonPrefix_commutativity+ (LeftGCDMonoidInstance (_ :: a)) =+ forAll (arbitrary :: Gen (a, a)) $+ \a b -> commonPrefix a b === commonPrefix b a++checkCommonPrefix_associativity+ (LeftGCDMonoidInstance (_ :: a)) =+ forAll (arbitrary :: Gen (a, a, a)) $+ \a b c ->+ (commonPrefix a (commonPrefix b c)) ===+ (commonPrefix (commonPrefix a b) c)++checkCommonPrefix_distributivity+ (LeftDistributiveGCDMonoidInstance (_ :: a)) =+ forAll (arbitrary :: Gen (a, a, a)) $+ \(a, b, c) -> commonPrefix (a <> b) (a <> c) == a <> commonPrefix b c++checkCommonSuffix_idempotence+ (RightGCDMonoidInstance (_ :: a)) =+ forAll (arbitrary :: Gen a) $+ \a -> commonSuffix a a === a++checkCommonSuffix_identity_left+ (RightGCDMonoidInstance (_ :: a)) =+ forAll (arbitrary :: Gen a) $+ \a -> commonSuffix mempty a === mempty++checkCommonSuffix_identity_right+ (RightGCDMonoidInstance (_ :: a)) =+ forAll (arbitrary :: Gen a) $+ \a -> commonSuffix a mempty === mempty++checkCommonSuffix_commutativity+ (RightGCDMonoidInstance (_ :: a)) =+ forAll (arbitrary :: Gen (a, a)) $+ \a b -> commonSuffix a b === commonSuffix b a++checkCommonSuffix_associativity+ (RightGCDMonoidInstance (_ :: a)) =+ forAll (arbitrary :: Gen (a, a, a)) $+ \a b c ->+ (commonSuffix a (commonSuffix b c)) ===+ (commonSuffix (commonSuffix a b) c)++checkCommonSuffix_distributivity+ (RightDistributiveGCDMonoidInstance (_ :: a)) =+ forAll (arbitrary :: Gen (a, a, a)) $+ \(a, b, c) -> commonSuffix (a <> c) (b <> c) == commonSuffix a b <> c+ checkLCM_reductivity_left (LCMMonoidInstance (_ :: a)) = forAll (arbitrary :: Gen (a, a)) check where@@ -971,22 +1220,22 @@ where check a b = gcd a (lcm a b) === a -checkLCM_distributivity_left (LCMMonoidInstance (_ :: a)) =+checkLCM_distributivity_left (DistributiveLCMMonoidInstance (_ :: a)) = forAll (arbitrary :: Gen (a, a, a)) check where check a b c = lcm (a <> b) (a <> c) === a <> lcm b c -checkLCM_distributivity_right (LCMMonoidInstance (_ :: a)) =+checkLCM_distributivity_right (DistributiveLCMMonoidInstance (_ :: a)) = forAll (arbitrary :: Gen (a, a, a)) check where check a b c = lcm (a <> c) (b <> c) === lcm a b <> c -checkLCM_distributivity_gcd_lcm (LCMMonoidInstance (_ :: a)) =+checkLCM_distributivity_gcd_lcm (DistributiveLCMMonoidInstance (_ :: a)) = forAll (arbitrary :: Gen (a, a, a)) check where check a b c = lcm a (gcd b c) === gcd (lcm a b) (lcm a c) -checkLCM_distributivity_lcm_gcd (LCMMonoidInstance (_ :: a)) =+checkLCM_distributivity_lcm_gcd (DistributiveLCMMonoidInstance (_ :: a)) = forAll (arbitrary :: Gen (a, a, a)) check where check a b c = gcd a (lcm b c) === lcm (gcd a b) (gcd a c)
monoid-subclasses.cabal view
@@ -1,5 +1,5 @@ Name: monoid-subclasses-Version: 1.2.2+Version: 1.2.3 Cabal-Version: >= 1.10 Build-Type: Simple Synopsis: Subclasses of Monoid@@ -23,12 +23,22 @@ Library hs-source-dirs: src- Exposed-Modules: Data.Semigroup.Cancellative, Data.Semigroup.Factorial,- Data.Monoid.Cancellative, Data.Monoid.GCD, Data.Monoid.LCM, Data.Monoid.Monus,- Data.Monoid.Factorial, Data.Monoid.Null, Data.Monoid.Textual,- Data.Monoid.Instances.ByteString.UTF8, Data.Monoid.Instances.CharVector,- Data.Monoid.Instances.Concat, Data.Monoid.Instances.Measured, Data.Monoid.Instances.Positioned,- Data.Monoid.Instances.Stateful+ Exposed-Modules:+ Data.Monoid.Cancellative+ , Data.Monoid.Factorial+ , Data.Monoid.GCD+ , Data.Monoid.Instances.ByteString.UTF8+ , Data.Monoid.Instances.CharVector+ , Data.Monoid.Instances.Concat+ , Data.Monoid.Instances.Measured+ , Data.Monoid.Instances.Positioned+ , Data.Monoid.Instances.Stateful+ , Data.Monoid.LCM+ , Data.Monoid.Monus+ , Data.Monoid.Null+ , Data.Monoid.Textual+ , Data.Semigroup.Cancellative+ , Data.Semigroup.Factorial Build-Depends: base >= 4.9 && < 5, bytestring >= 0.9 && < 1.0, containers >= 0.5.7.0 && < 0.7,
src/Data/Monoid/GCD.hs view
@@ -9,22 +9,57 @@ -- The 'GCDMonoid' subclass adds the 'gcd' operation which takes two monoidal arguments and finds their greatest -- common divisor, or (more generally) the greatest monoid that can be extracted with the '</>' operation from both. ----- The 'GCDMonoid' class is for Abelian, /i.e./, 'Commutative' monoids. Since most practical monoids in Haskell are not--- Abelian, there are also its three symmetric superclasses:--- +-- The 'GCDMonoid' class is for Abelian, /i.e./, 'Commutative' monoids.+--+-- == Non-commutative GCD monoids+--+-- Since most practical monoids in Haskell are not Abelian, the 'GCDMonoid'+-- class has three symmetric superclasses:+-- -- * 'LeftGCDMonoid'--- +--+-- Class of monoids for which it is possible to find the greatest common+-- /prefix/ of two monoidal values.+-- -- * 'RightGCDMonoid'--- +--+-- Class of monoids for which it is possible to find the greatest common+-- /suffix/ of two monoidal values.+-- -- * 'OverlappingGCDMonoid'-+--+-- Class of monoids for which it is possible to find the greatest common+-- /overlap/ of two monoidal values.+--+-- == Distributive GCD monoids+--+-- Since some (but not all) GCD monoids are also distributive, there are three+-- subclasses that add distributivity:+--+-- * 'DistributiveGCDMonoid'+--+-- Subclass of 'GCDMonoid' with /symmetric/ distributivity.+--+-- * 'LeftDistributiveGCDMonoid'+--+-- Subclass of 'LeftGCDMonoid' with /left/-distributivity.+--+-- * 'RightDistributiveGCDMonoid'+--+-- Subclass of 'RightGCDMonoid' with /right/-distributivity.+-- {-# LANGUAGE CPP, Haskell2010, FlexibleInstances, Trustworthy #-} -module Data.Monoid.GCD (- GCDMonoid(..),- LeftGCDMonoid(..), RightGCDMonoid(..), OverlappingGCDMonoid(..)- )-where+module Data.Monoid.GCD+ ( GCDMonoid (..)+ , LeftGCDMonoid (..)+ , RightGCDMonoid (..)+ , OverlappingGCDMonoid (..)+ , DistributiveGCDMonoid+ , LeftDistributiveGCDMonoid+ , RightDistributiveGCDMonoid+ )+ where import qualified Prelude @@ -54,6 +89,9 @@ import Data.Semigroup.Cancellative import Data.Monoid.Monus +-- These imports are marked as redundant, but are actually required by haddock:+import Data.Maybe (isJust)+ import Prelude hiding (gcd) -- | Class of Abelian monoids that allow the greatest common divisor to be found for any two given values. The@@ -63,10 +101,47 @@ -- > Just a' = a </> p && Just b' = b </> p -- > where p = gcd a b ----- If a 'GCDMonoid' happens to also be 'Cancellative', it should additionally satisfy the following laws:+-- In addition, the 'gcd' operation must satisfy the following properties: ----- > gcd (a <> b) (a <> c) == a <> gcd b c--- > gcd (a <> c) (b <> c) == gcd a b <> c+-- __/Uniqueness/__+--+-- @+-- 'all' 'isJust'+-- [ a '</>' c+-- , b '</>' c+-- , c '</>' 'gcd' a b+-- ]+-- ==>+-- (c '==' 'gcd' a b)+-- @+--+-- __/Idempotence/__+--+-- @+-- 'gcd' a a '==' a+-- @+--+-- __/Identity/__+--+-- @+-- 'gcd' 'mempty' a '==' 'mempty'+-- @+-- @+-- 'gcd' a 'mempty' '==' 'mempty'+-- @+--+-- __/Commutativity/__+--+-- @+-- 'gcd' a b '==' 'gcd' b a+-- @+--+-- __/Associativity/__+--+-- @+-- 'gcd' ('gcd' a b) c '==' 'gcd' a ('gcd' b c)+-- @+-- class (Monoid m, Commutative m, Reductive m, LeftGCDMonoid m, RightGCDMonoid m, OverlappingGCDMonoid m) => GCDMonoid m where gcd :: m -> m -> m @@ -88,6 +163,39 @@ -- and it cannot itself be a suffix of any other common prefix @y@ of both values: -- -- > not (y `isPrefixOf` a && y `isPrefixOf` b && commonPrefix a b `isSuffixOf` y)+--+-- In addition, the 'commonPrefix' operation must satisfy the following+-- properties:+--+-- __/Idempotence/__+--+-- @+-- 'commonPrefix' a a '==' a+-- @+--+-- __/Identity/__+--+-- @+-- 'commonPrefix' 'mempty' a '==' 'mempty'+-- @+-- @+-- 'commonPrefix' a 'mempty' '==' 'mempty'+-- @+--+-- __/Commutativity/__+--+-- @+-- 'commonPrefix' a b '==' 'commonPrefix' b a+-- @+--+-- __/Associativity/__+--+-- @+-- 'commonPrefix' ('commonPrefix' a b) c+-- '=='+-- 'commonPrefix' a ('commonPrefix' b c)+-- @+-- class (Monoid m, LeftReductive m) => LeftGCDMonoid m where commonPrefix :: m -> m -> m stripCommonPrefix :: m -> m -> (m, m, m)@@ -118,6 +226,39 @@ -- and it cannot itself be a prefix of any other common suffix @y@ of both values: -- -- > not (y `isSuffixOf` a && y `isSuffixOf` b && commonSuffix a b `isPrefixOf` y)+--+-- In addition, the 'commonSuffix' operation must satisfy the following+-- properties:+--+-- __/Idempotence/__+--+-- @+-- 'commonSuffix' a a '==' a+-- @+--+-- __/Identity/__+--+-- @+-- 'commonSuffix' 'mempty' a '==' 'mempty'+-- @+-- @+-- 'commonSuffix' a 'mempty' '==' 'mempty'+-- @+--+-- __/Commutativity/__+--+-- @+-- 'commonSuffix' a b '==' 'commonSuffix' b a+-- @+--+-- __/Associativity/__+--+-- @+-- 'commonSuffix' ('commonSuffix' a b) c+-- '=='+-- 'commonSuffix' a ('commonSuffix' b c)+-- @+-- class (Monoid m, RightReductive m) => RightGCDMonoid m where commonSuffix :: m -> m -> m stripCommonSuffix :: m -> m -> (m, m, m)@@ -455,3 +596,97 @@ stripCommonSuffix (LazyEncoding.encodeUtf8 x) (LazyEncoding.encodeUtf8 y) in (LazyEncoding.decodeUtf8 xlist, LazyEncoding.decodeUtf8 ylist, LazyEncoding.decodeUtf8 slist) #endif++--------------------------------------------------------------------------------+-- DistributiveGCDMonoid+--------------------------------------------------------------------------------++-- | Class of /commutative/ GCD monoids with /symmetric/ distributivity.+--+-- In addition to the general 'GCDMonoid' laws, instances of this class+-- must also satisfy the following laws:+--+-- @+-- 'gcd' (a '<>' b) (a '<>' c) '==' a '<>' 'gcd' b c+-- @+-- @+-- 'gcd' (a '<>' c) (b '<>' c) '==' 'gcd' a b '<>' c+-- @+--+class (LeftDistributiveGCDMonoid m, RightDistributiveGCDMonoid m, GCDMonoid m)+ => DistributiveGCDMonoid m++instance DistributiveGCDMonoid ()+instance DistributiveGCDMonoid (Product Natural)+instance DistributiveGCDMonoid (Sum Natural)+instance DistributiveGCDMonoid IntSet.IntSet+instance DistributiveGCDMonoid a => DistributiveGCDMonoid (Dual a)+instance Ord a => DistributiveGCDMonoid (Set.Set a)++-------------------------------------------------------------------------------+-- LeftDistributiveGCDMonoid+--------------------------------------------------------------------------------++-- | Class of /left/ GCD monoids with /left/-distributivity.+--+-- In addition to the general 'LeftGCDMonoid' laws, instances of this class+-- must also satisfy the following law:+--+-- @+-- 'commonPrefix' (a '<>' b) (a '<>' c) '==' a '<>' 'commonPrefix' b c+-- @+--+class LeftGCDMonoid m => LeftDistributiveGCDMonoid m++-- Instances for non-commutative monoids:+instance Eq a => LeftDistributiveGCDMonoid [a]+instance Eq a => LeftDistributiveGCDMonoid (Sequence.Seq a)+instance Eq a => LeftDistributiveGCDMonoid (Vector.Vector a)+instance LeftDistributiveGCDMonoid ByteString.ByteString+instance LeftDistributiveGCDMonoid LazyByteString.ByteString+instance LeftDistributiveGCDMonoid Text.Text+instance LeftDistributiveGCDMonoid LazyText.Text++-- Instances for commutative monoids:+instance LeftDistributiveGCDMonoid ()+instance LeftDistributiveGCDMonoid (Product Natural)+instance LeftDistributiveGCDMonoid (Sum Natural)+instance LeftDistributiveGCDMonoid IntSet.IntSet+instance Ord a => LeftDistributiveGCDMonoid (Set.Set a)++-- Instances for monoid transformers:+instance RightDistributiveGCDMonoid a => LeftDistributiveGCDMonoid (Dual a)++--------------------------------------------------------------------------------+-- RightDistributiveGCDMonoid+--------------------------------------------------------------------------------++-- | Class of /right/ GCD monoids with /right/-distributivity.+--+-- In addition to the general 'RightGCDMonoid' laws, instances of this class+-- must also satisfy the following law:+--+-- @+-- 'commonSuffix' (a '<>' c) (b '<>' c) '==' 'commonSuffix' a b '<>' c+-- @+--+class RightGCDMonoid m => RightDistributiveGCDMonoid m++-- Instances for non-commutative monoids:+instance Eq a => RightDistributiveGCDMonoid [a]+instance Eq a => RightDistributiveGCDMonoid (Sequence.Seq a)+instance Eq a => RightDistributiveGCDMonoid (Vector.Vector a)+instance RightDistributiveGCDMonoid ByteString.ByteString+instance RightDistributiveGCDMonoid LazyByteString.ByteString+instance RightDistributiveGCDMonoid Text.Text+instance RightDistributiveGCDMonoid LazyText.Text++-- Instances for commutative monoids:+instance RightDistributiveGCDMonoid ()+instance RightDistributiveGCDMonoid (Product Natural)+instance RightDistributiveGCDMonoid (Sum Natural)+instance RightDistributiveGCDMonoid IntSet.IntSet+instance Ord a => RightDistributiveGCDMonoid (Set.Set a)++-- Instances for monoid transformers:+instance LeftDistributiveGCDMonoid a => RightDistributiveGCDMonoid (Dual a)
src/Data/Monoid/LCM.hs view
@@ -7,19 +7,23 @@ -- least monoid from which either argument can be subtracted with the '</>' -- operation. ----- The 'LCMMonoid' class is for Abelian, /i.e./, 'Commutative' monoids.+-- For LCM monoids that are distributive, this module also provides the+-- 'DistributiveLCMMonoid' subclass of 'LCMMonoid'. ---module Data.Monoid.LCM (- LCMMonoid (..)+-- All classes in this module are for Abelian, /i.e./, 'Commutative' monoids.+--+module Data.Monoid.LCM+ ( LCMMonoid (..)+ , DistributiveLCMMonoid )-where+ where -import Prelude hiding (lcm, max)+import Prelude hiding (gcd, lcm, max) import qualified Prelude import Data.IntSet (IntSet) import Data.Monoid (Dual (..), Product (..), Sum (..))-import Data.Monoid.GCD (GCDMonoid)+import Data.Monoid.GCD (GCDMonoid (..), DistributiveGCDMonoid) import Data.Set (Set) import Numeric.Natural (Natural) import qualified Data.IntSet as IntSet@@ -30,6 +34,10 @@ import Data.Semigroup.Cancellative (Reductive ((</>))) import Data.Semigroup.Commutative (Commutative) +--------------------------------------------------------------------------------+-- LCMMonoid+--------------------------------------------------------------------------------+ -- | Class of Abelian monoids that allow the /least common multiple/ to be -- found for any two given values. --@@ -92,21 +100,6 @@ -- 'gcd' a ('lcm' a b) '==' a -- @ ----- __/Distributivity/__------ @--- 'lcm' (a '<>' b) (a '<>' c) '==' a '<>' 'lcm' b c--- @--- @--- 'lcm' (a '<>' c) (b '<>' c) '==' 'lcm' a b '<>' c--- @--- @--- 'lcm' a ('gcd' b c) '==' 'gcd' ('lcm' a b) ('lcm' a c)--- @--- @--- 'gcd' a ('lcm' b c) '==' 'lcm' ('gcd' a b) ('gcd' a c)--- @--- class GCDMonoid m => LCMMonoid m where lcm :: m -> m -> m @@ -141,3 +134,40 @@ where lcm (a0, a1, a2, a3) (b0, b1, b2, b3) = (lcm a0 b0, lcm a1 b1, lcm a2 b2, lcm a3 b3)++--------------------------------------------------------------------------------+-- DistributiveLCMMonoid+--------------------------------------------------------------------------------++-- | Class of /commutative/ LCM monoids with /distributivity/.+--+-- In addition to the general 'LCMMonoid' laws, instances of this class+-- must also satisfy the following laws:+--+-- The 'lcm' operation itself must be /both/ left-distributive /and/+-- right-distributive:+--+-- @+-- 'lcm' (a '<>' b) (a '<>' c) '==' a '<>' 'lcm' b c+-- @+-- @+-- 'lcm' (a '<>' c) (b '<>' c) '==' 'lcm' a b '<>' c+-- @+--+-- The 'lcm' and 'gcd' operations must distribute over one another:+--+-- @+-- 'lcm' a ('gcd' b c) '==' 'gcd' ('lcm' a b) ('lcm' a c)+-- @+-- @+-- 'gcd' a ('lcm' b c) '==' 'lcm' ('gcd' a b) ('gcd' a c)+-- @+--+class (DistributiveGCDMonoid m, LCMMonoid m) => DistributiveLCMMonoid m++instance DistributiveLCMMonoid ()+instance DistributiveLCMMonoid (Product Natural)+instance DistributiveLCMMonoid (Sum Natural)+instance DistributiveLCMMonoid IntSet+instance Ord a => DistributiveLCMMonoid (Set a)+instance DistributiveLCMMonoid a => DistributiveLCMMonoid (Dual a)
src/Data/Monoid/Monus.hs view
@@ -67,6 +67,24 @@ -- > ∀y. ((∀x. (x `isPrefixOf` b && x `isSuffixOf` a) => x `isPrefixOf` y && x `isSuffixOf` y) => y == overlap a b) -- -- @since 1.0+--+-- In addition, the 'overlap' operation must satisfy the following properties:+--+-- __/Idempotence/__+--+-- @+-- 'overlap' a a '==' a+-- @+--+-- __/Identity/__+--+-- @+-- 'overlap' 'mempty' a '==' 'mempty'+-- @+-- @+-- 'overlap' a 'mempty' '==' 'mempty'+-- @+-- class (Monoid m, LeftReductive m, RightReductive m) => OverlappingGCDMonoid m where stripPrefixOverlap :: m -> m -> m stripSuffixOverlap :: m -> m -> m