{-# language BangPatterns #-}
{-# language FlexibleInstances #-}
{-# language Safe #-}
-- |
-- Module       : Data.Group.Cyclic
-- Copyright    : (c) 2020 Emily Pillmore
-- License      : BSD-style
--
-- Maintainer   : Emily Pillmore <emilypi@cohomolo.gy>,
--                Reed Mullanix <reedmullanix@gmail.com>
-- Stability    : stable
-- Portability  : non-portable
--
-- This module contains definitions for 'CyclicGroup'
-- along with the relevant combinators.
--
module Data.Group.Cyclic
( -- * Cyclic groups
  CyclicGroup(..)
  -- ** Combinators
, generate
, classify
) where

import Data.Functor.Const
import Data.Functor.Identity
import Data.Group
import Data.Int
import Data.List
import Data.Monoid
import Data.Ord
import Data.Proxy
import Data.Word

-- $setup
--
-- >>> import qualified Prelude
-- >>> import Data.Group
-- >>> import Data.Monoid
-- >>> import Data.Semigroup
-- >>> :set -XTypeApplications

-- -------------------------------------------------------------------- --
-- Cyclic groups

-- | A 'CyclicGroup' is a 'Group' that is generated by a single element.
-- This element is called a /generator/ of the group. There can be many
-- generators for a group, e.g., any representative of an equivalence
-- class of prime numbers of the integers modulo @n@, but to make things
-- easy, we ask for only one generator.
--
class Group g => CyclicGroup g where
  generator :: g
  {-# minimal generator #-}

instance CyclicGroup () where
  generator :: ()
generator = ()
  {-# inline generator #-}

-- instance CyclicGroup b => CyclicGroup (a -> b) where
--   generator = const generator
--   {-# inlinable generator #-}

instance CyclicGroup a => CyclicGroup (Dual a) where
  generator :: Dual a
generator = a -> Dual a
forall a. a -> Dual a
Dual (a -> a
forall a. Group a => a -> a
invert a
forall g. CyclicGroup g => g
generator)
  {-# inlinable generator #-}

instance CyclicGroup (Sum Integer) where
  generator :: Sum Integer
generator = Sum Integer
1
  {-# inline generator #-}

instance CyclicGroup (Sum Rational) where
  generator :: Sum Rational
generator = Sum Rational
1
  {-# inline generator #-}

instance CyclicGroup (Sum Int) where
  generator :: Sum Int
generator = Sum Int
1
  {-# inline generator #-}

instance CyclicGroup (Sum Int8) where
  generator :: Sum Int8
generator = Sum Int8
1
  {-# inline generator #-}

instance CyclicGroup (Sum Int16) where
  generator :: Sum Int16
generator = Sum Int16
1
  {-# inline generator #-}

instance CyclicGroup (Sum Int32) where
  generator :: Sum Int32
generator = Sum Int32
1
  {-# inline generator #-}

instance CyclicGroup (Sum Int64) where
  generator :: Sum Int64
generator = Sum Int64
1
  {-# inline generator #-}

instance CyclicGroup (Sum Word) where
  generator :: Sum Word
generator = Sum Word
1
  {-# inline generator #-}

instance CyclicGroup (Sum Word8) where
  generator :: Sum Word8
generator = Sum Word8
1
  {-# inline generator #-}

instance CyclicGroup (Sum Word16) where
  generator :: Sum Word16
generator = Sum Word16
1
  {-# inline generator #-}

instance CyclicGroup (Sum Word32) where
  generator :: Sum Word32
generator = Sum Word32
1
  {-# inline generator #-}

instance CyclicGroup (Sum Word64) where
  generator :: Sum Word64
generator = Sum Word64
1
  {-# inline generator #-}

instance CyclicGroup a => CyclicGroup (Const a b) where
  generator :: Const a b
generator = a -> Const a b
forall k a (b :: k). a -> Const a b
Const a
forall g. CyclicGroup g => g
generator
  {-# inlinable generator #-}

instance CyclicGroup a => CyclicGroup (Identity a) where
  generator :: Identity a
generator = a -> Identity a
forall a. a -> Identity a
Identity a
forall g. CyclicGroup g => g
generator
  {-# inlinable generator #-}

instance CyclicGroup a => CyclicGroup (Proxy a) where
  generator :: Proxy a
generator = Proxy a
forall k (t :: k). Proxy t
Proxy
  {-# inlinable generator #-}

instance (CyclicGroup a, CyclicGroup b) => CyclicGroup (a,b) where
  generator :: (a, b)
generator = (a
forall g. CyclicGroup g => g
generator, b
forall g. CyclicGroup g => g
generator)
  {-# inlinable generator #-}

instance (CyclicGroup a, CyclicGroup b, CyclicGroup c) => CyclicGroup (a,b,c) where
  generator :: (a, b, c)
generator = (a
forall g. CyclicGroup g => g
generator, b
forall g. CyclicGroup g => g
generator, c
forall g. CyclicGroup g => g
generator)
  {-# inlinable generator #-}

instance (CyclicGroup a, CyclicGroup b, CyclicGroup c, CyclicGroup d) => CyclicGroup (a,b,c,d)  where
  generator :: (a, b, c, d)
generator = (a
forall g. CyclicGroup g => g
generator, b
forall g. CyclicGroup g => g
generator, c
forall g. CyclicGroup g => g
generator, d
forall g. CyclicGroup g => g
generator)
  {-# inlinable generator #-}

instance (CyclicGroup a, CyclicGroup b, CyclicGroup c, CyclicGroup d, CyclicGroup e) => CyclicGroup (a,b,c,d,e) where
  generator :: (a, b, c, d, e)
generator = (a
forall g. CyclicGroup g => g
generator, b
forall g. CyclicGroup g => g
generator, c
forall g. CyclicGroup g => g
generator, d
forall g. CyclicGroup g => g
generator, e
forall g. CyclicGroup g => g
generator)
  {-# inlinable generator #-}

instance CyclicGroup a => CyclicGroup (Down a) where
  generator :: Down a
generator = a -> Down a
forall a. a -> Down a
Down a
forall g. CyclicGroup g => g
generator
  {-# inline generator #-}

instance CyclicGroup a => CyclicGroup (Endo a) where
  generator :: Endo a
generator = (a -> a) -> Endo a
forall a. (a -> a) -> Endo a
Endo ((a -> a) -> Endo a) -> (a -> a) -> Endo a
forall a b. (a -> b) -> a -> b
$ a -> a -> a
forall a b. a -> b -> a
const a
forall g. CyclicGroup g => g
generator
  {-# inline generator #-}

-- -------------------------------------------------------------------- --
-- Cyclic group combinators

-- | Lazily generate all elements of a 'CyclicGroup' from its generator.
--
-- /Note/: fuses.
--
generate :: (Eq a, CyclicGroup a) => [a]
generate :: [a]
generate = ((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.
(Ord b, Num b, CyclicGroup a, Enum b, Eq a) =>
(a, b) -> Maybe (a, (a, b))
go (a
forall g. CyclicGroup g => g
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. Monoid a => a
mempty, 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 g. CyclicGroup g => g
generator, b -> b
forall a. Enum a => a -> a
succ b
n))
{-# noinline generate #-}

-- | Classify elements of a 'CyclicGroup'.
--
-- Apply a classifying function @a -> Bool@ to the elements
-- of a 'CyclicGroup' as generated by its designated generator.
--
-- === __Examples__:
--
-- >>> classify (< (3 :: Sum Word8))
-- [Sum {getSum = 1},Sum {getSum = 2}]
--
classify :: (Eq a, CyclicGroup a) => (a -> Bool) -> [a]
classify :: (a -> Bool) -> [a]
classify a -> Bool
p = (a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
filter a -> Bool
p [a]
forall a. (Eq a, CyclicGroup a) => [a]
generate
{-# inline classify #-}