acts 0.1.0.0 → 0.2.0.0

raw patch · 6 files changed

+114/−199 lines, 6 filesdep +finitaryPVP ok

version bump matches the API change (PVP)

Dependencies added: finitary

API changes (from Hackage documentation)

Files

• acts.cabal +3/−2
• changelog.md +18/−1
• examples/Acts/Examples/MusicalIntervals.hs +24/−7
• src/Data/Act.hs +58/−13
• src/Data/Group.hs +11/−1
• src/Data/Group/Cyclic.hs +0/−175

@@ -1,6 +1,6 @@ cabal-version:  2.4
 name:           acts
-version:        0.1.0.0
+version:        0.2.0.0
 synopsis:       Semigroup actions, groups, and torsors.
 category:       Algebra, Math
 license:        BSD-3-Clause
@@ -49,6 +49,8 @@         >= 4.12 && < 4.15
     , deepseq
         ^>= 1.4.4.0
+    , finitary
+        ^>= 1.2.0.0
     , finite-typelits
         ^>= 0.1.4.2
     , generic-data
@@ -77,7 +79,6 @@   exposed-modules:
       Data.Act
     , Data.Group
-    , Data.Group.Cyclic
 
 
 library acts-examples

@@ -1,5 +1,22 @@ # Changelog for package `acts`
 
-## 0.1.0.0 ( February 2020 )
+## 0.2.0.0 ( February 14, 2020 )
+
+* Remove definition of cyclic groups.
+It is instead suggested to use a library which defines modular arithmetic.    
+For instance: `type C (n :: Nat) = Sum ( Finite n )`, using the `finite-typelits` library.
+
+* `CyclicEnum` newtype changed to `Finitely` newtype, which uses `Finitary` instead of `Bounded + Enum`.
+This ensures that the action is by a semigroup of the right cardinality.
+
+* Remove `Act` instances for `Max`, `Min` to avoid possible overlap with user defined instances.
+
+* Add `anti :: Group g => g -> Dual g` function to construct elements in the opposite _group_.    
+Obsoletes the `Act` instance for `Dual` (now removed).
+
+* Address a limitation of GHC < 8.10 with `DerivingVia` and `MultiParamTypeClasses`,
+by manually writing some instances.
+
+## 0.1.0.0 ( February 13, 2020 )
 
 * Initial release.

@@ -1,5 +1,6 @@ {-# LANGUAGE
     DataKinds
+  , DeriveAnyClass
   , DeriveGeneric
   , DerivingVia
   , MultiParamTypeClasses
@@ -34,11 +35,22 @@ -- base
 import Data.Monoid
   ( Sum(..) )
+import GHC.Generics
+  ( Generic )
 
+-- finitary
+import Data.Finitary
+  ( Finitary )
+
+-- finite-typelits
+import Data.Finite
+  ( Finite )
+
 -- acts
 import Data.Act
+  ( Act(..), Torsor(..), Finitely(..) )
 import Data.Group
-import Data.Group.Cyclic
+  ( Group(..) )
 
 -----------------------------------------------------------------
 -- * Musical notes
@@ -46,17 +58,21 @@ -- $notenames
 -- We begin by defining note names, which are acted upon by the cyclic group of order 7.
 
+-- | Cyclic group of order 7.
+type C7 = Sum ( Finite 7 )
+
 -- | Musical note names.
 --
 -- The enumeration starts with @C@ to conform with scientific pitch notation.
 data NoteName = C | D | E | F | G | A | B
-  deriving stock ( Eq, Ord, Show, Enum, Bounded )
-  deriving ( Act ( C 7 ), Torsor ( C 7 ) )
-    via CyclicEnum NoteName
+  deriving stock    ( Eq, Ord, Show, Enum, Bounded, Generic )
+  deriving anyclass Finitary
+  deriving ( Act C7, Torsor C7 )
+    via Finitely NoteName
 
 -- $deriving1
--- In this case we used @DerivingVia@ to derive the action of @C 7@,
--- using the 'CyclicEnum' newtype created for this exact purpose.
+-- In this case we used @DerivingVia@ to derive the action of @C7@
+-- through the 'Finitary' instance of 'NoteName' by using the 'Finitely' newtype.
 
 -- | Alterations, i.e. sharps and flats.
 --
@@ -153,8 +169,9 @@ --  * minor third up from @C@: @Eb@
 --  * minor third up from @A@: @C@.
 instance Act Interval Note where
-  act ( Steps ( Sum steps ) a ) ( Note C a' o ) = Note ( act ( Cyclic @7 r ) C ) ( a <> a' ) ( q + o )
+  act ( Steps ( Sum steps ) a ) ( Note C a' o ) = Note ( act ( fromIntegral r :: C7 ) C ) ( a <> a' ) ( q + o )
     where
+      q, r :: Int
       ( q, r ) = steps `divMod` 7
   act ival note = act ( ival <> ( Note C Natural 0 --> note ) ) ( Note C Natural 0 )
 

@@ -8,6 +8,8 @@   , MultiParamTypeClasses
   , ScopedTypeVariables
   , StandaloneDeriving
+  , TypeApplications
+  , TypeFamilies
   , UndecidableInstances
 #-}
 
@@ -44,6 +46,7 @@   , Trivial(..)
   , Torsor(..)
   , intertwiner
+  , Finitely(..)
   )
   where
 
@@ -62,7 +65,7 @@   , Ap(..), Endo(..)
   )
 import Data.Semigroup
-  ( Max(..), Min(..), Dual(..) )
+  ( Dual(..) )
 import GHC.Generics
   ( Generic, Generic1 )
 
@@ -70,9 +73,17 @@ import Control.DeepSeq
   ( NFData )
 
+-- finitary
+import Data.Finitary
+  ( Finitary(..) )
+
+-- finite-typelits
+import Data.Finite
+  ( Finite )
+
 -- acts
 import Data.Group
-  ( Group(..) )
+  ( Group(..), anti )
 
 -----------------------------------------------------------------
 
@@ -118,10 +129,10 @@ 
 deriving via Any instance Act Any Bool
 deriving via All instance Act All Bool
-deriving via ( Sum     a ) instance Num a => Act ( Sum     a ) a
-deriving via ( Product a ) instance Num a => Act ( Product a ) a
-deriving via ( Max     a ) instance Ord a => Act ( Max     a ) a
-deriving via ( Min     a ) instance Ord a => Act ( Min     a ) a
+instance Num a => Act ( Sum     a ) a where
+  act s = coerce ( act s :: Sum a -> Sum a )
+instance Num a => Act ( Product a ) a where
+  act s = coerce ( act s :: Product a -> Product a )
 
 instance {-# OVERLAPPING #-} Act () x where
   act _ = id
@@ -148,22 +159,55 @@ instance ( Act s x, Functor f ) => Act s ( Ap f x ) where
   act s = coerce ( fmap ( act s ) :: f x -> f x )
 
--- | Acting through the contravariant function arrow functor.
+-- | Acting through the contravariant function arrow functor: right action.
+--
+-- If acting by a group, use `anti :: Group g => g -> Dual g` to act by the original group
+-- instead of the opposite group.
 instance ( Semigroup s, Act s a ) => Act ( Dual s ) ( Op b a ) where
   act ( Dual s ) = coerce ( ( . act s ) :: ( a -> b ) -> ( a -> b ) )
 
 -- | Acting through a function arrow: both covariant and contravariant actions.
+--
+-- If acting by a group, use `anti :: Group g => g -> Dual g` to act by the original group
+-- instead of the opposite group.
 instance ( Semigroup s, Act s a, Act t b ) => Act ( Dual s, t ) ( a -> b ) where
   act ( Dual s, t ) p = act t . p . act s
 
--- | Action of an opposite group using inverses.
-instance {-# OVERLAPPABLE #-} ( Act g x, Group g ) => Act ( Dual g ) x where
-  act ( Dual g ) = act ( inverse g )
-
 -- | Action of a group on endomorphisms.
 instance ( Group g, Act g a ) => Act g ( Endo a ) where
-  act g = coerce ( act ( Dual g, g ) :: ( a -> a ) -> ( a -> a ) )
+  act g = coerce ( act ( anti g, g ) :: ( a -> a ) -> ( a -> a ) )
 
+-- | Newtype for the action on a type through its 'Finitary' instance.
+--
+-- > data ABCD = A | B | C | D
+-- >   deriving stock    ( Eq, Generic )
+-- >   deriving anyclass Finitary
+-- >   deriving ( Act ( Sum ( Finite 4 ) ), Torsor ( Sum ( Finite 4 ) ) )
+-- >     via Finitely ABCD
+--
+-- Sizes are checked statically. For instance if we had instead written:
+--
+-- >   deriving ( Act ( Sum ( Finite 3 ) ), Torsor ( Sum ( Finite 3 ) ) )
+-- >     via Finitely ABCD
+--
+-- we would have gotten the error messages:
+--
+-- > * No instance for (Act (Sum (Finite 3)) (Finite 4))
+-- > * No instance for (Torsor (Sum (Finite 3)) (Finite 4))
+--
+newtype Finitely a = Finitely { getFinitely :: a }
+  deriving stock   ( Show, Read, Data, Generic, Generic1 )
+  deriving newtype ( Eq, Ord, NFData )
+
+-- | Act on a type through its 'Finitary' instance.
+instance ( Semigroup s, Act    s ( Finite n ), Finitary a, n ~ Cardinality a )
+        => Act    s ( Finitely a ) where
+  act s = Finitely . fromFinite . act s . toFinite . getFinitely
+-- | Torsor for a type using its 'Finitary' instance.
+instance ( Group     g, Torsor g ( Finite n ), Finitary a, n ~ Cardinality a )
+      => Torsor g ( Finitely a ) where
+  Finitely x --> Finitely y = toFinite x --> toFinite y
+
 -----------------------------------------------------------------
 
 -- | A left __torsor__ consists of a /free/ and /transitive/ left action of a group on an inhabited type.
@@ -195,7 +239,8 @@ instance Group g => Torsor g g where
   h <-- g = h <> inverse g
 
-deriving via ( Sum a ) instance Num a => Torsor ( Sum a ) a
+instance Num a => Torsor ( Sum a ) a where
+  (<--) = coerce ( (<--) :: Sum a -> Sum a -> Sum a )
 
 -- | Given
 -- 

@@ -51,7 +51,7 @@ 
 
 module Data.Group
-  ( Group(..)
+  ( Group(..), anti, reflexive
   , Isom(..)
   )
   where
@@ -59,6 +59,8 @@ -- base
 import Control.Monad.ST
   ( ST )
+import Data.Coerce
+  ( coerce )
 import Data.Data
   ( Data )
 import Data.Functor.Const
@@ -112,6 +114,14 @@     EQ -> const mempty
     GT -> stimes n
     LT -> stimes ( negate n ) . inverse
+
+-- | The inverse anti-automorphism of a group lifts to a isomorphism with the opposite group.
+anti :: Group g => g -> Dual g
+anti g = Dual ( inverse g )
+
+-- | Reflexive property 'Dual' (should be included in base, maybe under another name).
+reflexive :: Dual ( Dual a ) -> a
+reflexive = coerce
 
 -----------------------------------------------------------------------
 -- Instances.

@@ -1,175 +0,0 @@-{-# LANGUAGE
-    DataKinds
-  , DeriveDataTypeable
-  , DeriveGeneric
-  , DerivingVia
-  , FlexibleContexts
-  , FlexibleInstances
-  , GADTs
-  , GeneralizedNewtypeDeriving
-  , MultiParamTypeClasses
-  , PatternSynonyms
-  , PolyKinds
-  , ScopedTypeVariables
-  , StandaloneDeriving
-  , TypeApplications
-  , TypeFamilies
-  , TypeOperators
-  , ViewPatterns
-#-}
-
-{-|
-Module: Data.Group.Cyclic
-
-Cyclic groups: integers modulo @n@ (clock arithmetic).
--}
-
-module Data.Group.Cyclic
-  ( Cyclic(Cyclic), getCyclic
-  , C, Z
-  , CyclicEnum(..)
-  , pattern Involution, involution
-  , rootOfUnity
-  )
-  where
-
--- base
-import Data.Coerce
-  ( coerce )
-import Data.Complex
-  ( Complex(..), conjugate, mkPolar )
-import Data.Data
-  ( Data )
-import Data.Monoid
-  ( Sum(..), Product(..) )
-import Data.Proxy
-  ( Proxy(..) )
-import GHC.Generics
-  ( Generic, Generic1 )
-import GHC.TypeNats
-  ( Nat, KnownNat, natVal
-  , type (<=)
-  )
-
--- deepseq
-import Control.DeepSeq
-  ( NFData )
-
--- finite-typelits
-import Data.Finite
-  ( Finite, getFinite )
-
--- acts
-import Data.Act
-  ( Act(..), Torsor(..) )
-import Data.Group
-  ( Group(..) )
-
------------------------------------------------------------------
-
--- | Cyclic group of order @n@: integers with addition modulo @n@.
-newtype Cyclic n = MkCyclic { runCyclic :: Finite n }
-  deriving stock   ( Show, Generic, Generic1 )
-  deriving newtype ( Eq, Ord, Enum, Bounded, NFData )
-deriving via ( Sum ( Finite n ) ) instance KnownNat n => Semigroup ( Cyclic n ) 
-deriving via ( Sum ( Finite n ) ) instance ( KnownNat n, 1 <= n ) => Monoid ( Cyclic n )
-deriving via ( Sum ( Finite n ) ) instance ( KnownNat n, 1 <= n ) => Group  ( Cyclic n )
-
-{-# COMPLETE Cyclic #-}
--- | Smart pattern and constructor for elements of cyclic groups.
-pattern Cyclic :: forall n. KnownNat n => Int -> Cyclic n
-pattern Cyclic i <- ( fromIntegral . getFinite . runCyclic -> i )
-  where
-    Cyclic i = MkCyclic ( fromIntegral ( i `mod` ( fromIntegral ( natVal ( Proxy @n ) ) ) ) )
-
--- | Obtain a representative in the range \( [0, n[ \).
-getCyclic :: forall n. KnownNat n => Cyclic n -> Int
-getCyclic ( Cyclic i ) = i
-
--- | Synonym for finite cyclic group.
-type C ( n :: Nat ) = Cyclic n
--- | Synonym for infinite cyclic group.
-type Z = Sum Int
-
-instance KnownNat n => Act ( Cyclic n ) Int where
-  act ( Cyclic f ) j
-    | r + i >= n
-    = ( i - n ) + j
-    | otherwise
-    = i + j
-    where
-      i, n, r :: Int
-      i = fromIntegral f
-      n = fromIntegral ( natVal ( Proxy @n ) )
-      r = j `mod` n
-
--- | Nontrivial element of cyclic group of order 2.
-pattern Involution :: Cyclic 2
-pattern Involution = Cyclic 1
-
--- | Act by an involution.
-involution :: Act ( Cyclic 2 ) x => x -> x
-involution = act Involution
-
-instance Act ( Cyclic 2 ) Bool where
-  act Involution = not
-  act _          = id
-
-instance Num i => Act ( Cyclic 2 ) ( Sum i ) where
-  act Involution = coerce ( negate :: i -> i )
-  act _          = id
-
-instance Fractional i => Act ( Cyclic 2 ) ( Product i ) where
-  act Involution = coerce ( recip :: i -> i )
-  act _          = id
-
-instance Num a => Act ( Cyclic 2 ) ( Complex a ) where
-  act Involution = conjugate
-  act _          = id
-
--- | Natural complex representations of finite cyclic groups as roots of unity.
-rootOfUnity :: forall a n. ( KnownNat n, Floating a ) => Cyclic n -> Complex a
-rootOfUnity ( Cyclic f ) = mkPolar 1 ( 2 * pi * i / n )
-  where
-    i, n :: a
-    i = fromIntegral f
-    n = fromIntegral ( natVal ( Proxy @n ) )
-
--- | Newtype for cycling through elements in a finite enumeration.
---
--- > data ABCD = A | B | C | D 
--- >   deriving stock ( Enum, Bounded )
--- >   deriving ( Act ( Cyclic 4 ), Torsor ( Cyclic 4 ) )
--- >     via CyclicEnum ABCD
--- 
--- > > act ( Cyclic 2 ) C
--- > A
---
--- > > act ( Cyclic (-1) ) A
--- > D
---
--- > > ( C --> B :: Cyclic 4 )
--- > Cyclic 3
---
--- __Warning__
--- It is unfortunately not checked that the size of the group
--- matches the size of the finite enumeration.
--- Please manually ensure this condition.
-newtype CyclicEnum a = CyclicEnum { getCyclicEnum :: a }
-  deriving stock   ( Show, Data, Generic, Generic1 )
-  deriving newtype ( Eq, Ord, Enum, Bounded, NFData )
-
-instance ( Enum a, Bounded a, KnownNat n ) => Act ( Cyclic n ) ( CyclicEnum a ) where
-  act ( Cyclic f ) a = toEnum j
-    where
-      b_min, b_max, i, j :: Int
-      b_min = fromEnum ( minBound @a )
-      b_max = fromEnum ( maxBound @a )
-      i = fromIntegral f
-      j = b_min + ( fromEnum a + i - b_min ) `mod` ( 1 + b_max - b_min )
-      -- Assumes n ~ ( 1 + b_max - b_min ).
-instance ( Enum a, Bounded a, KnownNat n, 1 <= n ) => Torsor ( Cyclic n ) ( CyclicEnum a ) where
-  a --> b = Cyclic . fromIntegral . ( `mod` n ) $ fromEnum b - fromEnum a
-    where
-      n :: Int
-      n = fromIntegral ( natVal ( Proxy @n ) )