module Data.Group where
import Data.Monoid
class Monoid m => Group m where
invert :: m -> m
pow :: Integral x => m -> x -> m
pow x0 :: m
x0 n0 :: x
n0 = case x -> x -> Ordering
forall a. Ord a => a -> a -> Ordering
compare x
n0 0 of
LT -> m -> m
forall m. Group m => m -> m
invert (m -> m) -> (x -> m) -> x -> m
forall b c a. (b -> c) -> (a -> b) -> a -> c
. m -> x -> m
forall a a. (Integral a, Monoid a) => a -> a -> a
f m
x0 (x -> m) -> x -> m
forall a b. (a -> b) -> a -> b
$ x -> x
forall a. Num a => a -> a
negate x
n0
EQ -> m
forall a. Monoid a => a
mempty
GT -> m -> x -> m
forall a a. (Integral a, Monoid a) => a -> a -> a
f m
x0 x
n0
where
f :: a -> a -> a
f x :: a
x n :: a
n
| a -> Bool
forall a. Integral a => a -> Bool
even a
n = a -> a -> a
f (a
x a -> a -> a
forall a. Monoid a => a -> a -> a
`mappend` a
x) (a
n a -> a -> a
forall a. Integral a => a -> a -> a
`quot` 2)
| a
n a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== 1 = a
x
| Bool
otherwise = a -> a -> a -> a
forall a a. (Integral a, Monoid a) => a -> a -> a -> a
g (a
x a -> a -> a
forall a. Monoid a => a -> a -> a
`mappend` a
x) (a
n a -> a -> a
forall a. Integral a => a -> a -> a
`quot` 2) a
x
g :: a -> a -> a -> a
g x :: a
x n :: a
n c :: a
c
| a -> Bool
forall a. Integral a => a -> Bool
even a
n = a -> a -> a -> a
g (a
x a -> a -> a
forall a. Monoid a => a -> a -> a
`mappend` a
x) (a
n a -> a -> a
forall a. Integral a => a -> a -> a
`quot` 2) a
c
| a
n a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== 1 = a
x a -> a -> a
forall a. Monoid a => a -> a -> a
`mappend` a
c
| Bool
otherwise = a -> a -> a -> a
g (a
x a -> a -> a
forall a. Monoid a => a -> a -> a
`mappend` a
x) (a
n a -> a -> a
forall a. Integral a => a -> a -> a
`quot` 2) (a
x a -> a -> a
forall a. Monoid a => a -> a -> a
`mappend` a
c)
instance Group () where
invert :: () -> ()
invert () = ()
pow :: () -> x -> ()
pow () _ = ()
instance Num a => Group (Sum a) where
invert :: Sum a -> Sum a
invert = a -> Sum a
forall a. a -> Sum a
Sum (a -> Sum a) -> (Sum a -> a) -> Sum a -> Sum a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> a
forall a. Num a => a -> a
negate (a -> a) -> (Sum a -> a) -> Sum a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Sum a -> a
forall a. Sum a -> a
getSum
{-# INLINE invert #-}
pow :: Sum a -> x -> Sum a
pow (Sum a :: a
a) b :: x
b = a -> Sum a
forall a. a -> Sum a
Sum (a
a a -> a -> a
forall a. Num a => a -> a -> a
* x -> a
forall a b. (Integral a, Num b) => a -> b
fromIntegral x
b)
instance Fractional a => Group (Product a) where
invert :: Product a -> Product a
invert = a -> Product a
forall a. a -> Product a
Product (a -> Product a) -> (Product a -> a) -> Product a -> Product a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> a
forall a. Fractional a => a -> a
recip (a -> a) -> (Product a -> a) -> Product a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Product a -> a
forall a. Product a -> a
getProduct
{-# INLINE invert #-}
pow :: Product a -> x -> Product a
pow (Product a :: a
a) b :: x
b = a -> Product a
forall a. a -> Product a
Product (a
a a -> x -> a
forall a b. (Fractional a, Integral b) => a -> b -> a
^^ x
b)
instance Group a => Group (Dual a) where
invert :: Dual a -> Dual a
invert = a -> Dual a
forall a. a -> Dual a
Dual (a -> Dual a) -> (Dual a -> a) -> Dual a -> Dual a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> a
forall m. Group m => m -> m
invert (a -> a) -> (Dual a -> a) -> Dual a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Dual a -> a
forall a. Dual a -> a
getDual
{-# INLINE invert #-}
pow :: Dual a -> x -> Dual a
pow (Dual a :: a
a) n :: x
n = a -> Dual a
forall a. a -> Dual a
Dual (a -> x -> a
forall m x. (Group m, Integral x) => m -> x -> m
pow a
a x
n)
instance Group b => Group (a -> b) where
invert :: (a -> b) -> a -> b
invert f :: a -> b
f = b -> b
forall m. Group m => m -> m
invert (b -> b) -> (a -> b) -> a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> b
f
pow :: (a -> b) -> x -> a -> b
pow f :: a -> b
f n :: x
n e :: a
e = b -> x -> b
forall m x. (Group m, Integral x) => m -> x -> m
pow (a -> b
f a
e) x
n
instance (Group a, Group b) => Group (a, b) where
invert :: (a, b) -> (a, b)
invert (a :: a
a, b :: b
b) = (a -> a
forall m. Group m => m -> m
invert a
a, b -> b
forall m. Group m => m -> m
invert b
b)
pow :: (a, b) -> x -> (a, b)
pow (a :: a
a, b :: b
b) n :: x
n = (a -> x -> a
forall m x. (Group m, Integral x) => m -> x -> m
pow a
a x
n, b -> x -> b
forall m x. (Group m, Integral x) => m -> x -> m
pow b
b x
n)
instance (Group a, Group b, Group c) => Group (a, b, c) where
invert :: (a, b, c) -> (a, b, c)
invert (a :: a
a, b :: b
b, c :: c
c) = (a -> a
forall m. Group m => m -> m
invert a
a, b -> b
forall m. Group m => m -> m
invert b
b, c -> c
forall m. Group m => m -> m
invert c
c)
pow :: (a, b, c) -> x -> (a, b, c)
pow (a :: a
a, b :: b
b, c :: c
c) n :: x
n = (a -> x -> a
forall m x. (Group m, Integral x) => m -> x -> m
pow a
a x
n, b -> x -> b
forall m x. (Group m, Integral x) => m -> x -> m
pow b
b x
n, c -> x -> c
forall m x. (Group m, Integral x) => m -> x -> m
pow c
c x
n)
instance (Group a, Group b, Group c, Group d) => Group (a, b, c, d) where
invert :: (a, b, c, d) -> (a, b, c, d)
invert (a :: a
a, b :: b
b, c :: c
c, d :: d
d) = (a -> a
forall m. Group m => m -> m
invert a
a, b -> b
forall m. Group m => m -> m
invert b
b, c -> c
forall m. Group m => m -> m
invert c
c, d -> d
forall m. Group m => m -> m
invert d
d)
pow :: (a, b, c, d) -> x -> (a, b, c, d)
pow (a :: a
a, b :: b
b, c :: c
c, d :: d
d) n :: x
n = (a -> x -> a
forall m x. (Group m, Integral x) => m -> x -> m
pow a
a x
n, b -> x -> b
forall m x. (Group m, Integral x) => m -> x -> m
pow b
b x
n, c -> x -> c
forall m x. (Group m, Integral x) => m -> x -> m
pow c
c x
n, d -> x -> d
forall m x. (Group m, Integral x) => m -> x -> m
pow d
d x
n)
instance (Group a, Group b, Group c, Group d, Group e) => Group (a, b, c, d, e) where
invert :: (a, b, c, d, e) -> (a, b, c, d, e)
invert (a :: a
a, b :: b
b, c :: c
c, d :: d
d, e :: e
e) = (a -> a
forall m. Group m => m -> m
invert a
a, b -> b
forall m. Group m => m -> m
invert b
b, c -> c
forall m. Group m => m -> m
invert c
c, d -> d
forall m. Group m => m -> m
invert d
d, e -> e
forall m. Group m => m -> m
invert e
e)
pow :: (a, b, c, d, e) -> x -> (a, b, c, d, e)
pow (a :: a
a, b :: b
b, c :: c
c, d :: d
d, e :: e
e) n :: x
n = (a -> x -> a
forall m x. (Group m, Integral x) => m -> x -> m
pow a
a x
n, b -> x -> b
forall m x. (Group m, Integral x) => m -> x -> m
pow b
b x
n, c -> x -> c
forall m x. (Group m, Integral x) => m -> x -> m
pow c
c x
n, d -> x -> d
forall m x. (Group m, Integral x) => m -> x -> m
pow d
d x
n, e -> x -> e
forall m x. (Group m, Integral x) => m -> x -> m
pow e
e x
n)
class Group g => Abelian g
instance Abelian ()
instance Num a => Abelian (Sum a)
instance Fractional a => Abelian (Product a)
instance Abelian a => Abelian (Dual a)
instance Abelian b => Abelian (a -> b)
instance (Abelian a, Abelian b) => Abelian (a, b)
instance (Abelian a, Abelian b, Abelian c) => Abelian (a, b, c)
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)