groups 0.4.1.0 → 0.5.3
raw patch · 2 files changed
Files
- groups.cabal +13/−8
- src/Data/Group.hs +142/−7
groups.cabal view
@@ -1,19 +1,24 @@+cabal-version: 2.4 name: groups-version: 0.4.1.0-synopsis: Haskell 98 groups-description: - Haskell 98 groups. A group is a monoid with invertibility.-license: BSD3+version: 0.5.3+synopsis: Groups+description:+ A group is a monoid with invertibility.+license: BSD-3-Clause license-file: LICENSE author: Nathan "Taneb" van Doorn maintainer: nvd1234@gmail.com copyright: Copyright (C) 2013 Nathan van Doorn category: Algebra, Data, Math build-type: Simple-cabal-version: >=1.8 +source-repository head+ type: git+ location: https://github.com/Taneb/groups.git+ library exposed-modules: Data.Group- -- other-modules: - build-depends: base <5+ -- other-modules:+ build-depends: base >= 4.6 && < 5 hs-source-dirs: src+ default-language: Haskell2010
src/Data/Group.hs view
@@ -1,14 +1,37 @@+{-# LANGUAGE CPP #-}+#if MIN_VERSION_base(4,12,0)+{-# LANGUAGE TypeOperators #-}+#endif+ module Data.Group where import Data.Monoid+import Data.Ord+import Data.List (unfoldr)+#if MIN_VERSION_base(4,7,0)+import Data.Proxy+#endif+#if MIN_VERSION_base(4,9,0)+import Data.Functor.Const+import Data.Functor.Identity+#endif+#if MIN_VERSION_base(4,12,0)+import Data.Functor.Contravariant (Op(Op))+import GHC.Generics+#endif --- |A 'Group' is a 'Monoid' plus a function, 'invert', such that: +-- |A 'Group' is a 'Monoid' plus a function, 'invert', such that: -- -- @a \<> invert a == mempty@ -- -- @invert a \<> a == mempty@ class Monoid m => Group m where invert :: m -> m++ -- | Group subtraction: @x ~~ y == x \<> invert y@+ (~~) :: m -> m -> m+ x ~~ y = x `mappend` invert y+ -- |@'pow' a n == a \<> a \<> ... \<> a @ -- -- @ (n lots of a) @@@ -20,7 +43,7 @@ EQ -> mempty GT -> f x0 n0 where- f x n + f x n | even n = f (x `mappend` x) (n `quot` 2) | n == 1 = x | otherwise = g (x `mappend` x) (n `quot` 2) x@@ -28,16 +51,18 @@ | even n = g (x `mappend` x) (n `quot` 2) c | n == 1 = x `mappend` c | otherwise = g (x `mappend` x) (n `quot` 2) (x `mappend` c)- ++infixl 7 ~~+ instance Group () where invert () = ()- pow () _ = ()+ pow _ _ = () instance Num a => Group (Sum a) where invert = Sum . negate . getSum {-# INLINE invert #-} pow (Sum a) b = Sum (a * fromIntegral b)- + instance Fractional a => Group (Product a) where invert = Product . recip . getProduct {-# INLINE invert #-}@@ -55,7 +80,7 @@ instance (Group a, Group b) => Group (a, b) where invert (a, b) = (invert a, invert b) pow (a, b) n = (pow a n, pow b n)- + instance (Group a, Group b, Group c) => Group (a, b, c) where invert (a, b, c) = (invert a, invert b, invert c) pow (a, b, c) n = (pow a n, pow b n, pow c n)@@ -68,8 +93,13 @@ invert (a, b, c, d, e) = (invert a, invert b, invert c, invert d, invert e) pow (a, b, c, d, e) n = (pow a n, pow b n, pow c n, pow d n, pow e n) +#if MIN_VERSION_base(4,11,0)+instance Group a => Group (Down a) where+ invert (Down a) = Down (invert a)+#endif+ -- |An 'Abelian' group is a 'Group' that follows the rule:--- +-- -- @a \<> b == b \<> a@ class Group g => Abelian g @@ -90,3 +120,108 @@ instance (Abelian a, Abelian b, Abelian c, Abelian d) => Abelian (a, b, c, d) instance (Abelian a, Abelian b, Abelian c, Abelian d, Abelian e) => Abelian (a, b, c, d, e)++#if MIN_VERSION_base(4,11,0)+instance Abelian a => Abelian (Down a)+#endif++-- | A 'Group' G is 'Cyclic' if there exists an element x of G such that for all y in G, there exists an n, such that+--+-- @y = pow x n@+class Group a => Cyclic a where+ -- | The generator of the 'Cyclic' group.+ generator :: a++-- | Generate all elements of a 'Cyclic' group using its 'generator'.+--+-- /Note:/ Fuses, does not terminate even for finite groups.+--+generated :: Cyclic a => [a]+generated =+ iterate (mappend generator) mempty++-- | Lazily generate all elements of a 'Cyclic' group using its 'generator'.+--+-- /Note:/ Fuses, terminates if the underlying group is finite.+--+generated' :: (Eq a, Cyclic a) => [a]+generated' = unfoldr go (generator, 0 :: Integer)+ where+ go (a, n)+ | a == generator, n > 0 = Nothing+ | otherwise = Just (a, (a <> generator, succ n))++instance Cyclic () where+ generator = ()++instance Integral a => Cyclic (Sum a) where+ generator = Sum 1+#if MIN_VERSION_base(4,7,0)+-- | Trivial group, Functor style.+instance Group (Proxy x) where+ invert _ = Proxy+ _ ~~ _ = Proxy+ pow _ _ = Proxy++instance Abelian (Proxy x)++instance Cyclic (Proxy x) where+ generator = Proxy+#endif++-- 'Const' has existed for a long time, but the Monoid instance+-- arrives in base-4.9.0.0. Similarly, 'Identity' was defined in+-- base-4.8.0.0 but doesn't get the Monoid instance until base-4.9.0.0+#if MIN_VERSION_base(4,9,0)+-- | 'Const' lifts groups into a functor.+instance Group a => Group (Const a x) where+ invert (Const a) = Const (invert a)+ Const a ~~ Const b = Const (a ~~ b)++-- | 'Identity' lifts groups pointwise (at only one point).+instance Group a => Group (Identity a) where+ invert (Identity a) = Identity (invert a)+ Identity a ~~ Identity b = Identity (a ~~ b)++instance Abelian a => Abelian (Const a x)++instance Abelian a => Abelian (Identity a)++instance Cyclic a => Cyclic (Const a x) where+ generator = Const generator++instance Cyclic a => Cyclic (Identity a) where+ generator = Identity generator+#endif++-- (:*:) and (:.:) exist since base-4.6.0.0 but the Monoid instances+-- arrive in base-4.12.0.0.+-- Also, contravariant was moved into base in this version.+#if MIN_VERSION_base(4,12,0)+-- | Product of groups, Functor style.+instance (Group (f a), Group (g a)) => Group ((f :*: g) a) where+ invert (a :*: b) = invert a :*: invert b+ (a :*: b) ~~ (c :*: d) = (a ~~ c) :*: (b ~~ d)++-- See https://gitlab.haskell.org/ghc/ghc/issues/11135#note_111802 for the reason Compose is not also provided.+-- Base does not define Monoid (Compose f g a) so this is the best we can+-- really do for functor composition.+instance Group (f (g a)) => Group ((f :.: g) a) where+ invert (Comp1 xs) = Comp1 (invert xs)+ Comp1 xs ~~ Comp1 ys = Comp1 (xs ~~ ys)++instance (Abelian (f a), Abelian (g a)) => Abelian ((f :*: g) a)++instance Abelian (f (g a)) => Abelian ((f :.: g) a)++instance Group a => Group (Op a b) where+ invert (Op f) = Op (invert f)+ pow (Op f) n = Op (\e -> pow (f e) n)++instance Abelian a => Abelian (Op a b)+#endif++#if MIN_VERSION_base(4,11,0)+instance Cyclic a => Cyclic (Down a) where+ generator = Down generator+#endif