    {-# 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 \<> 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
      m
    x ~~ m
    y = m
    x m -> m -> m
    forall a. Monoid a => a -> a -> a
    `mappend` m -> m
    forall m. Group m => m -> m
    invert m
    y

      -- |@'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 m
    x0 x
    n0 = case x -> x -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare x
    n0 x
    0 of
        Ordering
    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} {t}. (Integral a, Monoid t) => t -> a -> t
    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
        Ordering
    EQ -> m
    forall a. Monoid a => a
    mempty
        Ordering
    GT -> m -> x -> m
    forall {a} {t}. (Integral a, Monoid t) => t -> a -> t
    f m
    x0 x
    n0
        where
          f :: t -> a -> t
    f t
    x a
    n
            | a -> Bool
    forall a. Integral a => a -> Bool
    even a
    n = t -> a -> t
    f (t
    x t -> t -> t
    forall a. Monoid a => a -> a -> a
    `mappend` t
    x) (a
    n a -> a -> a
    forall a. Integral a => a -> a -> a
    `quot` a
    2)
            | a
    n a -> a -> Bool
    forall a. Eq a => a -> a -> Bool
    == a
    1 = t
    x
            | Bool
    otherwise = t -> a -> t -> t
    forall {a} {t}. (Integral a, Monoid t) => t -> a -> t -> t
    g (t
    x t -> t -> t
    forall a. Monoid a => a -> a -> a
    `mappend` t
    x) (a
    n a -> a -> a
    forall a. Integral a => a -> a -> a
    `quot` a
    2) t
    x
          g :: t -> a -> t -> t
    g t
    x a
    n t
    c
            | a -> Bool
    forall a. Integral a => a -> Bool
    even a
    n = t -> a -> t -> t
    g (t
    x t -> t -> t
    forall a. Monoid a => a -> a -> a
    `mappend` t
    x) (a
    n a -> a -> a
    forall a. Integral a => a -> a -> a
    `quot` a
    2) t
    c
            | a
    n a -> a -> Bool
    forall a. Eq a => a -> a -> Bool
    == a
    1 = t
    x t -> t -> t
    forall a. Monoid a => a -> a -> a
    `mappend` t
    c
            | Bool
    otherwise = t -> a -> t -> t
    g (t
    x t -> t -> t
    forall a. Monoid a => a -> a -> a
    `mappend` t
    x) (a
    n a -> a -> a
    forall a. Integral a => a -> a -> a
    `quot` a
    2) (t
    x t -> t -> t
    forall a. Monoid a => a -> a -> a
    `mappend` t
    c)

    infixl 7 ~~

    instance Group () where
      invert :: () -> ()
    invert () = ()
      pow :: forall x. Integral x => () -> x -> ()
    pow ()
    _ x
    _ = ()

    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 :: forall x. Integral x => Sum a -> x -> Sum a
    pow (Sum a
    a) 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 :: forall x. Integral x => Product a -> x -> Product a
    pow (Product a
    a) 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 :: forall x. Integral x => Dual a -> x -> Dual a
    pow (Dual a
    a) x
    n = a -> Dual a
    forall a. a -> Dual a
    Dual (a -> x -> a
    forall x. Integral x => 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 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 :: forall x. Integral x => (a -> b) -> x -> a -> b
    pow a -> b
    f x
    n a
    e = b -> x -> b
    forall x. Integral x => 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, 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 :: forall x. Integral x => (a, b) -> x -> (a, b)
    pow (a
    a, b
    b) x
    n = (a -> x -> a
    forall x. Integral x => a -> x -> a
    forall m x. (Group m, Integral x) => m -> x -> m
    pow a
    a x
    n, b -> x -> b
    forall x. Integral x => 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, b
    b, 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 :: forall x. Integral x => (a, b, c) -> x -> (a, b, c)
    pow (a
    a, b
    b, c
    c) x
    n = (a -> x -> a
    forall x. Integral x => a -> x -> a
    forall m x. (Group m, Integral x) => m -> x -> m
    pow a
    a x
    n, b -> x -> b
    forall x. Integral x => b -> x -> b
    forall m x. (Group m, Integral x) => m -> x -> m
    pow b
    b x
    n, c -> x -> c
    forall x. Integral x => 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, b
    b, c
    c, 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 :: forall x. Integral x => (a, b, c, d) -> x -> (a, b, c, d)
    pow (a
    a, b
    b, c
    c, d
    d) x
    n = (a -> x -> a
    forall x. Integral x => a -> x -> a
    forall m x. (Group m, Integral x) => m -> x -> m
    pow a
    a x
    n, b -> x -> b
    forall x. Integral x => b -> x -> b
    forall m x. (Group m, Integral x) => m -> x -> m
    pow b
    b x
    n, c -> x -> c
    forall x. Integral x => c -> x -> c
    forall m x. (Group m, Integral x) => m -> x -> m
    pow c
    c x
    n, d -> x -> d
    forall x. Integral x => 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, b
    b, c
    c, d
    d, 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 :: forall x. Integral x => (a, b, c, d, e) -> x -> (a, b, c, d, e)
    pow (a
    a, b
    b, c
    c, d
    d, e
    e) x
    n = (a -> x -> a
    forall x. Integral x => a -> x -> a
    forall m x. (Group m, Integral x) => m -> x -> m
    pow a
    a x
    n, b -> x -> b
    forall x. Integral x => b -> x -> b
    forall m x. (Group m, Integral x) => m -> x -> m
    pow b
    b x
    n, c -> x -> c
    forall x. Integral x => c -> x -> c
    forall m x. (Group m, Integral x) => m -> x -> m
    pow c
    c x
    n, d -> x -> d
    forall x. Integral x => d -> x -> d
    forall m x. (Group m, Integral x) => m -> x -> m
    pow d
    d x
    n, e -> x -> e
    forall x. Integral x => e -> x -> e
    forall m x. (Group m, Integral x) => m -> x -> m
    pow e
    e x
    n)

    #if MIN_VERSION_base(4,11,0)
    instance Group a => Group (Down a) where
      invert :: Down a -> Down a
    invert (Down a
    a) = a -> Down a
    forall a. a -> Down a
    Down (a -> a
    forall m. Group m => m -> m
    invert a
    a)
    #endif

    -- |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)

    #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 :: forall a. Cyclic a => [a]
    generated =
      (a -> a) -> a -> [a]
    forall a. (a -> a) -> a -> [a]
    iterate (a -> a -> a
    forall a. Monoid a => a -> a -> a
    mappend a
    forall a. Cyclic a => a
    generator) a
    forall a. Monoid a => a
    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' :: forall a. (Eq a, Cyclic a) => [a]
    generated' = ((a, Integer) -> Maybe (a, (a, Integer))) -> (a, Integer) -> [a]
    forall b a. (b -> Maybe (a, b)) -> b -> [a]
    unfoldr (a, Integer) -> Maybe (a, (a, Integer))
    forall {a} {b}.
    (Cyclic a, Ord b, Num b, Enum b, Eq a) =>
    (a, b) -> Maybe (a, (a, b))
    go (a
    forall a. Cyclic a => a
    generator, Integer
    0 :: Integer)
      where
        go :: (a, b) -> Maybe (a, (a, b))
    go (a
    a, b
    n)
          | a
    a a -> a -> Bool
    forall a. Eq a => a -> a -> Bool
    == a
    forall a. Cyclic a => a
    generator, b
    n b -> b -> Bool
    forall a. Ord a => a -> a -> Bool
    > b
    0 = Maybe (a, (a, b))
    forall a. Maybe a
    Nothing
          | Bool
    otherwise = (a, (a, b)) -> Maybe (a, (a, b))
    forall a. a -> Maybe a
    Just (a
    a, (a
    a a -> a -> a
    forall a. Semigroup a => a -> a -> a
    <> a
    forall a. Cyclic a => a
    generator, b -> b
    forall a. Enum a => a -> a
    succ b
    n))

    instance Cyclic () where
      generator :: ()
    generator = ()

    instance Integral a => Cyclic (Sum a) where
      generator :: Sum a
    generator = a -> Sum a
    forall a. a -> Sum a
    Sum a
    1
    #if MIN_VERSION_base(4,7,0)
    -- | Trivial group, Functor style.
    instance Group (Proxy x) where
      invert :: Proxy x -> Proxy x
    invert Proxy x
    _ = Proxy x
    forall {k} (t :: k). Proxy t
    Proxy
      Proxy x
    _ ~~ :: Proxy x -> Proxy x -> Proxy x
    ~~ Proxy x
    _ = Proxy x
    forall {k} (t :: k). Proxy t
    Proxy
      pow :: forall x. Integral x => Proxy x -> x -> Proxy x
    pow Proxy x
    _ x
    _ = Proxy x
    forall {k} (t :: k). Proxy t
    Proxy

    instance Abelian (Proxy x)

    instance Cyclic (Proxy x) where
      generator :: Proxy x
    generator = Proxy x
    forall {k} (t :: k). Proxy t
    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 x -> Const a x
    invert (Const a
    a) = a -> Const a x
    forall {k} a (b :: k). a -> Const a b
    Const (a -> a
    forall m. Group m => m -> m
    invert a
    a)
      Const a
    a ~~ :: Const a x -> Const a x -> Const a x
    ~~ Const a
    b = a -> Const a x
    forall {k} a (b :: k). a -> Const a b
    Const (a
    a a -> a -> a
    forall m. Group m => m -> m -> m
    ~~ a
    b)

    -- | 'Identity' lifts groups pointwise (at only one point).
    instance Group a => Group (Identity a) where
      invert :: Identity a -> Identity a
    invert (Identity a
    a) = a -> Identity a
    forall a. a -> Identity a
    Identity (a -> a
    forall m. Group m => m -> m
    invert a
    a)
      Identity a
    a ~~ :: Identity a -> Identity a -> Identity a
    ~~ Identity a
    b = a -> Identity a
    forall a. a -> Identity a
    Identity (a
    a a -> a -> a
    forall m. Group m => m -> m -> m
    ~~ 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 a x
    generator = a -> Const a x
    forall {k} a (b :: k). a -> Const a b
    Const a
    forall a. Cyclic a => a
    generator

    instance Cyclic a => Cyclic (Identity a) where
      generator :: Identity a
    generator = a -> Identity a
    forall a. a -> Identity a
    Identity a
    forall a. Cyclic a => a
    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 :: (:*:) f g a -> (:*:) f g a
    invert (f a
    a :*: g a
    b) = f a -> f a
    forall m. Group m => m -> m
    invert f a
    a f a -> g a -> (:*:) f g a
    forall k (f :: k -> *) (g :: k -> *) (p :: k).
    f p -> g p -> (:*:) f g p
    :*: g a -> g a
    forall m. Group m => m -> m
    invert g a
    b
      (f a
    a :*: g a
    b) ~~ :: (:*:) f g a -> (:*:) f g a -> (:*:) f g a
    ~~ (f a
    c :*: g a
    d) = (f a
    a f a -> f a -> f a
    forall m. Group m => m -> m -> m
    ~~ f a
    c) f a -> g a -> (:*:) f g a
    forall k (f :: k -> *) (g :: k -> *) (p :: k).
    f p -> g p -> (:*:) f g p
    :*: (g a
    b g a -> g a -> g a
    forall m. Group m => m -> m -> m
    ~~ g a
    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 :: (:.:) f g a -> (:.:) f g a
    invert (Comp1 f (g a)
    xs) = f (g a) -> (:.:) f g a
    forall k2 k1 (f :: k2 -> *) (g :: k1 -> k2) (p :: k1).
    f (g p) -> (:.:) f g p
    Comp1 (f (g a) -> f (g a)
    forall m. Group m => m -> m
    invert f (g a)
    xs)
      Comp1 f (g a)
    xs ~~ :: (:.:) f g a -> (:.:) f g a -> (:.:) f g a
    ~~ Comp1 f (g a)
    ys = f (g a) -> (:.:) f g a
    forall k2 k1 (f :: k2 -> *) (g :: k1 -> k2) (p :: k1).
    f (g p) -> (:.:) f g p
    Comp1 (f (g a)
    xs f (g a) -> f (g a) -> f (g a)
    forall m. Group m => m -> m -> m
    ~~ f (g a)
    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 a b -> Op a b
    invert (Op b -> a
    f) = (b -> a) -> Op a b
    forall a b. (b -> a) -> Op a b
    Op ((b -> a) -> b -> a
    forall m. Group m => m -> m
    invert b -> a
    f)
      pow :: forall x. Integral x => Op a b -> x -> Op a b
    pow (Op b -> a
    f) x
    n = (b -> a) -> Op a b
    forall a b. (b -> a) -> Op a b
    Op (\b
    e -> a -> x -> a
    forall x. Integral x => a -> x -> a
    forall m x. (Group m, Integral x) => m -> x -> m
    pow (b -> a
    f b
    e) x
    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 a
    generator = a -> Down a
    forall a. a -> Down a
    Down a
    forall a. Cyclic a => a
    generator
    #endif