    module Data.Group where

    import Data.Monoid

    -- |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
      -- |@'pow' a n == a \<> a \<> ... \<> a @
      --
      -- @ (n lots of a) @
      --
      -- If n is negative, the result is inverted.
      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)

    -- |An 'Abelian' group is a 'Group' that follows the rule:
    --
    -- @a \<> b == b \<> a@
    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)