group-theory 0.2.0.0 → 0.2.1.0

raw patch · 16 files changed

+135/−99 lines, 16 filesdep −doctestdep −group-theoryPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

Dependencies removed: doctest, group-theory

API changes (from Hackage documentation)

Files

• README.md +1/−1
• group-theory.cabal +21/−37
• src/Control/Applicative/Cancellative.hs +3/−2
• src/Data/Group.hs +5/−4
• src/Data/Group/Additive.hs +4/−3
• src/Data/Group/Cyclic.hs +4/−4
• src/Data/Group/Finite.hs +4/−4
• src/Data/Group/Foldable.hs +5/−4
• src/Data/Group/Free.hs +5/−4
• src/Data/Group/Free/Church.hs +1/−1
• src/Data/Group/Free/Internal.hs +5/−4
• src/Data/Group/Free/Product.hs +1/−1
• src/Data/Group/Multiplicative.hs +5/−3
• src/Data/Group/Order.hs +10/−1
• src/Data/Group/Permutation.hs +61/−19
• test/doctests.hs +0/−7

@@ -1,7 +1,7 @@ group-theory ========== -[![Hackage](https://img.shields.io/hackage/v/group-theory.svg)](https://hackage.haskell.org/package/group-theory) ![Build Status](https://github.com/emilypi/group-theory/workflows/ci/badge.svg)+[![Hackage](https://img.shields.io/hackage/v/group-theory.svg)](https://hackage.haskell.org/package/group-theory) ![Build Status](https://github.com/emilypi/group-theory/workflows/Haskell-CI/badge.svg)  This is a package for exploring constructive group theory in Haskell. 

@@ -1,7 +1,7 @@-cabal-version:   2.0-name:            group-theory-version:         0.2.0.0-synopsis:        The theory of groups+cabal-version:      2.0+name:               group-theory+version:            0.2.1.0+synopsis:           The theory of groups description:   This package includes definitions for Groups (Monoids with invertibility), including order calculations   as well as finite, free, cyclic, and permutation groups. Additionally, we add the concept@@ -17,31 +17,28 @@   .   This package, @group-theory@, tries to combine the best parts, while focusing on usability and intuitiveness. -homepage:        https://github.com/emilypi/group-theory-bug-reports:     https://github.com/emilypi/group-theory/issues-license:         BSD3-license-file:    LICENSE-author:          Emily Pillmore-maintainer:      Emily Pillmore <emilypi@cohomolo.gy>, Reed Mullanix <reedmullanix@gmail.com>-copyright:       (c) 2020 Emily Pillmore <emilypi@cohomolo.gy>-category:        Algebra, Math, Permutations, Groups-build-type:      Custom-extra-doc-files:+homepage:           https://github.com/emilypi/group-theory+bug-reports:        https://github.com/emilypi/group-theory/issues+license:            BSD3+license-file:       LICENSE+author:             Emily Pillmore+maintainer:+  Emily Pillmore <emilypi@cohomolo.gy>, Reed Mullanix <reedmullanix@gmail.com>++copyright:          (c) 2020-2021 Emily Pillmore <emilypi@cohomolo.gy>+category:           Algebra, Math, Permutations, Groups+build-type:         Simple+extra-source-files:   CHANGELOG.md   README.md -tested-with:     GHC ==8.4.4 || ==8.6.5 || ==8.8.4 || ==8.10.2+tested-with:+  GHC ==8.4.4 || ==8.6.5 || ==8.8.4 || ==8.10.4 || ==9.0.1  source-repository head   type:     git   location: https://github.com/emilypi/group-theory.git -custom-setup-  setup-depends:-      base           >=4.11 && <5-    , Cabal-    , cabal-doctest- library   exposed-modules:     Control.Applicative.Cancellative@@ -51,31 +48,18 @@     Data.Group.Finite     Data.Group.Foldable     Data.Group.Free-    Data.Group.Free.Internal     Data.Group.Free.Church+    Data.Group.Free.Internal     Data.Group.Free.Product     Data.Group.Multiplicative     Data.Group.Order     Data.Group.Permutation    build-depends:-      base        >=4.11 && <5-    , containers  >=0.5  && <0.7+      base        >=4.11  && <5+    , containers  >=0.5   && <0.7     , groups      ^>=0.5.2    hs-source-dirs:   src   default-language: Haskell2010   ghc-options:      -Wall--test-suite doctests-  default-language:  Haskell2010-  type:              exitcode-stdio-1.0-  main-is:           doctests.hs-  build-depends:-      base          >=4.11 && <5-    , doctest-    , group-theory--  hs-source-dirs:    test-  ghc-options:       -Wall -threaded-  x-doctest-options: --fast

@@ -31,8 +31,9 @@  -- $setup ----- >>> import qualified Prelude--- >>> import Data.Group+-- >>> :set -XPackageImports+-- >>> import Prelude+-- >>> import "group-theory" Data.Group -- >>> import Data.Monoid -- >>> import Data.Semigroup -- >>> import Data.Word

@@ -10,7 +10,7 @@ {-# language ViewPatterns #-} -- | -- Module       : Data.Group--- Copyright    : (c) 2020 Emily Pillmore+-- Copyright    : (c) 2020-2021 Emily Pillmore -- License      : BSD-style -- -- Maintainer   : Emily Pillmore <emilypi@cohomolo.gy>,@@ -56,8 +56,9 @@  -- $setup --+-- >>> :set -XPackageImports -- >>> import qualified Prelude--- >>> import Data.Group+-- >>> import "group-theory" Data.Group -- >>> import Data.Monoid -- >>> import Data.Semigroup -- >>> import Data.Word@@ -230,11 +231,11 @@   Commuted a <> Commuted b = Commuted (a <> b)  instance Monoid g => Monoid (Abelianizer g) where-  -- Normally we'd say 'Quot' but these are the same.-  mempty = Commuted mempty+  mempty = Quot  instance (Eq g, Group g) => Group (Abelianizer g) where   invert Quot = Quot+  invert (Commuted IdentityElem) = Quot   invert (Commuted a) = Commuted (invert a)  -- | Take the commutator of two elements of a group.

@@ -3,7 +3,7 @@ {-# language Safe #-} -- | -- Module       : Data.Group.Additive--- Copyright    : (c) 2020 Emily Pillmore+-- Copyright    : (c) 2020-2021 Emily Pillmore -- License      : BSD-style -- -- Maintainer   : Emily Pillmore <emilypi@cohomolo.gy>,@@ -43,9 +43,10 @@ infixl 7 ×  -- $setup---+-- >>> :set -XPackageImports+-- >>> import Prelude (Int) -- >>> import qualified Prelude--- >>> import Data.Group+-- >>> import "group-theory" Data.Group -- >>> import Data.Monoid -- >>> import Data.Semigroup -- >>> :set -XTypeApplications

@@ -3,7 +3,7 @@ {-# language Safe #-} -- | -- Module       : Data.Group.Cyclic--- Copyright    : (c) 2020 Emily Pillmore+-- Copyright    : (c) 2020-2021 Emily Pillmore -- License      : BSD-style -- -- Maintainer   : Emily Pillmore <emilypi@cohomolo.gy>,@@ -26,9 +26,9 @@ import "groups" Data.Group as G  -- $setup------ >>> import qualified Prelude--- >>> import Data.Group+-- >>> :set -XPackageImports+-- >>> import Prelude+-- >>> import "group-theory" Data.Group -- >>> import Data.Monoid -- >>> import Data.Semigroup -- >>> import Data.Word

@@ -4,7 +4,7 @@ {-# language Safe #-} -- | -- Module       : Data.Group.Finite--- Copyright    : (c) 2020 Emily Pillmore+-- Copyright    : (c) 2020-2021 Emily Pillmore -- License      : BSD-style -- -- Maintainer   : Emily Pillmore <emilypi@cohomolo.gy>,@@ -35,9 +35,9 @@ import Numeric.Natural (Natural)  -- $setup------ >>> import qualified Prelude--- >>> import Data.Group+-- >>> :set -XPackageImports+-- >>> import Prelude+-- >>> import "group-theory" Data.Group -- >>> import Data.Monoid -- >>> import Data.Semigroup -- >>> import Data.Word

@@ -6,7 +6,7 @@ #endif -- | -- Module       : Data.Group--- Copyright    : (c) 2020 Reed Mullanix, Emily Pillmore+-- Copyright    : (c) 2020-2021 Reed Mullanix, Emily Pillmore -- License      : BSD-style -- -- Maintainer   : Reed Mullanix <reedmullanix@gmail.com>,@@ -43,9 +43,10 @@   -- $setup------ >>> import qualified Prelude--- >>> import Data.Group+-- >>> :set -XPackageImports+-- >>> import Prelude+-- >>> import "group-theory" Data.Group+-- >>> import Data.Group.Free -- >>> import Data.Monoid -- >>> import Data.Semigroup -- >>> import Data.Word

@@ -2,7 +2,7 @@ {-# language Trustworthy #-} -- | -- Module       : Data.Group.Free--- Copyright    : (c) 2020 Reed Mullanix, Emily Pillmore+-- Copyright    : (c) 2020-2021 Reed Mullanix, Emily Pillmore -- License      : BSD-style -- -- Maintainer   : Reed Mullanix <reedmullanix@gmail.com>,@@ -46,12 +46,13 @@ import Data.Group import Data.Group.Free.Internal import Data.Group.Order-import Data.Semigroup(Semigroup(..)) + -- $setup ----- >>> import qualified Prelude--- >>> import Data.Group+-- >>> :set -XPackageImports+-- >>> import Prelude+-- >>> import "group-theory" Data.Group -- >>> import Data.Monoid -- >>> import Data.Semigroup -- >>> import Data.Word

@@ -2,7 +2,7 @@ {-# language Safe #-} -- | -- Module       : Data.Group--- Copyright    : (c) 2020 Reed Mullanix, Emily Pillmore+-- Copyright    : (c) 2020-2021 Reed Mullanix, Emily Pillmore -- License      : BSD-style -- -- Maintainer   : Reed Mullanix <reedmullanix@gmail.com>,

@@ -1,7 +1,7 @@ {-# language Unsafe #-} -- | -- Module       : Data.Group.Free.Internal--- Copyright    : (c) 2020 Reed Mullanix, Emily Pillmore, Koji Miyazato+-- Copyright    : (c) 2020-2021 Reed Mullanix, Emily Pillmore, Koji Miyazato -- License      : BSD-style -- -- Maintainer   : Reed Mullanix <reedmullanix@gmail.com>,@@ -28,12 +28,13 @@   -- $setup------ >>> import qualified Prelude--- >>> import Data.Group+-- >>> :set -XPackageImports+-- >>> import Prelude+-- >>> import "group-theory" Data.Group -- >>> import Data.Monoid -- >>> import Data.Semigroup -- >>> import Data.Word+-- >>> import qualified Data.Map as Map -- >>> :set -XTypeApplications -- >>> :set -XFlexibleContexts 

@@ -1,6 +1,6 @@ -- | -- Module       : Data.Group.Free.Product--- Copyright    : (c) 2020 Reed Mullanix, Emily Pillmore+-- Copyright    : (c) 2020-2021 Reed Mullanix, Emily Pillmore -- License      : BSD-style -- -- Maintainer   : Reed Mullanix <reedmullanix@gmail.com>,

@@ -2,7 +2,7 @@ {-# language Safe #-} -- | -- Module       : Data.Group.Multiplicative--- Copyright    : (c) 2020 Emily Pillmore+-- Copyright    : (c) 2020-2021 Emily Pillmore -- License      : BSD-style -- -- Maintainer   : Emily Pillmore <emilypi@cohomolo.gy>,@@ -39,8 +39,10 @@  -- $setup ----- >>> import qualified Prelude--- >>> import Data.Group+-- >>> :set -XPackageImports+-- >>> import Prelude (Int, Rational)+-- >>> import qualified Prelude as P+-- >>> import "group-theory" Data.Group -- >>> import Data.Monoid -- >>> import Data.Semigroup -- >>> :set -XTypeApplications

@@ -4,7 +4,7 @@ {-# language ViewPatterns #-} -- | -- Module       : Data.Group.Order--- Copyright    : (c) 2020 Emily Pillmore+-- Copyright    : (c) 2020-2021 Emily Pillmore, --                Koji Miyazato <viercc@gmail.com> -- License      : BSD-style --@@ -42,6 +42,15 @@  import Numeric.Natural (Natural) +-- $setup+--+-- >>> :set -XPackageImports+-- >>> import "group-theory" Data.Group+-- >>> import Data.Monoid+-- >>> import Data.Semigroup+-- >>> import Data.Word+-- >>> :set -XTypeApplications+-- >>> :set -XFlexibleContexts  -- -------------------------------------------------------------------- -- -- Group order

@@ -6,7 +6,7 @@ {-# language ViewPatterns #-} -- | -- Module       : Data.Group--- Copyright    : (c) 2020 Emily Pillmore+-- Copyright    : (c) 2020-2021 Emily Pillmore -- License      : BSD-style -- -- Maintainer   : Reed Mullanix <reedmullanix@gmail.com>,@@ -22,6 +22,9 @@ ( -- * Permutation groups   Permutation(..)   -- ** Permutation group combinators+, equalPermutation+, comparePermutation+, orderOfPermutation , permute , pairwise , (-$)@@ -34,7 +37,6 @@   import Data.Group-import Data.Group.Order  import qualified Data.IntSet as ISet import Data.Function (on)@@ -67,10 +69,10 @@ -- and computed their 'order's. -- -- >>> c1 = permute not not :: Permutation Bool--- >>> c1 <> c1 == mempty+-- >>> equalPermutation (c1 <> c1) mempty -- True--- >>> order c1--- Finite 2+-- >>> orderOfPermutation c1+-- 2 data Permutation a = Permutation   { to :: a -> a     -- ^ The forward half of the bijection@@ -90,14 +92,59 @@ instance Group (Permutation a) where   invert (Permutation t f) = Permutation f t -instance (Enum a, Bounded a) => Eq (Permutation a) where-  (==) = (==) `on` (functionRepr . to)+-- | Equality test for permutations on a finite type 'a'+--+-- This module /intentionally omits/ the following instance, albeit+-- 'equalPermutation' is suitable implementation of+-- @(==)@ operator for many types.+--+-- > instance (Enum a, Bounded a) => Eq (Permutation a) where+-- >   (==) = equalPermutation+--+-- This is because some type satisfying @(Enum a, Bounded a)@ are+-- actually finite but too large to use @equalPermutation@ on.+-- For example, you can call @equalPermutation@ on @Permutation Int@,+-- but it takes too much computation to be considered usable.+equalPermutation+  :: (Enum a, Bounded a) => Permutation a -> Permutation a -> Bool+equalPermutation = (==) `on` (functionRepr . to) -instance (Enum a, Bounded a) => Ord (Permutation a) where-  compare = compare `on` (functionRepr . to)+-- | Comparison for permutations on a finite type 'a'+--+-- This module /intentionally omits/ the following instance, albeit+-- 'comparePermutation' is suitable implementation of+-- @compare@ method for many types.+--+-- > instance (Enum a, Bounded a) => Eq (Permutation a) where+-- >   compare = comparePermutation+--+-- This is because some type satisfying @(Enum a, Bounded a)@ are+-- actually finite but too large to use @comparePermutation@ on.+-- For example, you can call @comparePermutation@ on @Permutation Int@,+-- but it takes too much computation to be considered usable.+comparePermutation+  :: (Enum a, Bounded a) => Permutation a -> Permutation a -> Ordering+comparePermutation = compare `on` (functionRepr . to) -instance (Enum a, Bounded a) => GroupOrder (Permutation a) where-  order Permutation{to = f} = Finite (go 1 fullSet)+functionRepr :: (Enum a, Bounded a) => (a -> a) -> [Int]+functionRepr f = fromEnum . f <$> [minBound .. maxBound]++-- | Order counting for a permutation on a finite type 'a'+--+-- This module /intentionally omits/ the following instance, albeit+-- 'orderOfPermutation' is suitable implementation of+-- @order@ method for many types.+--+-- > instance (Enum a, Bounded a) => GroupOrder (Permutation a) where+-- >   order a = Finite (orderOfPermutation a)+--+-- This is because some type satisfying @(Enum a, Bounded a)@ are+-- actually finite but too large to use @orderOfPermutation@ on.+-- For example, you can call @orderOfPermutation@ on @Permutation Int@,+-- but it takes too much computation to be considered usable.+orderOfPermutation+  :: forall a. (Enum a, Bounded a) => Permutation a -> Natural+orderOfPermutation Permutation{to = f} = go 1 fullSet     where       n = 1 + fromEnum (maxBound @a)       fullSet = ISet.fromDistinctAscList [0 .. n - 1]@@ -107,7 +154,7 @@        go :: Natural -> ISet.IntSet -> Natural       go !ord elements = case ISet.minView elements of-        Nothing -> ord+        Nothing             -> ord         Just (k, elements') ->           let (period, elements'') = takeCycle k elements'           in go (lcm period ord) elements''@@ -116,14 +163,9 @@       takeCycle k = loop 1 (f' k)         where           loop !period j elements-            | j `ISet.member` elements = loop (succ period) (f' j) (ISet.delete j elements)+            | j `ISet.member` elements      = loop (succ period) (f' j) (ISet.delete j elements)             | {- j ∉ elements && -} j == k = (period, elements)-            | otherwise = error $ "Non-bijective: witness=toEnum " ++ show j---- | Apply a function to all enumerated elements of a bounded enumerable type----functionRepr :: (Enum a, Bounded a) => (a -> a) -> [Int]-functionRepr f = fromEnum . f <$> [minBound .. maxBound]+            | otherwise                     = error $ "Non-bijective: witness=toEnum " ++ show j  -- -------------------------------------------------------------------- -- -- Permutation group combinators

@@ -1,7 +0,0 @@-module Main where--import Build_doctests (flags, pkgs, module_sources)-import Test.DocTest (doctest)--main :: IO ()-main = doctest $ flags ++ pkgs ++ module_sources