group-theory-0.2.2: The theory of groups
Copyright(c) 2020-2021 Emily Pillmore
Koji Miyazato <viercc@gmail.com>
LicenseBSD-style
MaintainerEmily Pillmore <emilypi@cohomolo.gy>, Reed Mullanix <reedmullanix@gmail.com>
Stabilitystable
Portabilitynon-portable
Safe HaskellSafe
LanguageHaskell2010

Data.Group.Order

Description

This module contains definitions for GroupOrder.

Synopsis

Group order

class (Eq g, Group g) => GroupOrder g where Source #

The typeclass of groups, equipped with the function computing the order of a specific element of a group.

The order of x is the smallest positive integer k such that gtimes k x == mempty. If there are no such integers, the order of x is defined to be infinity.

Note: For any valid instances of GroupOrder, order x == Finite 1 holds if and only if x == mempty.

Examples:

>>> order (3 :: Sum Word8)
Finite 256
>>> order (16 :: Sum Word8)
Finite 16
>>> order (0 :: Sum Integer)
Finite 1
>>> order (1 :: Sum Integer)
Infinite

Methods

order :: g -> Order Source #

The order of an element of a group.

order x must be Finite k if the order of x is finite k, and must be Infinite otherwise.

For a type which is also FiniteGroup, Finite . finiteOrder is a valid implementation of order, if not efficient.

Instances

Instances details
GroupOrder () Source # 
Instance details

Defined in Data.Group.Order

Methods

order :: () -> Order Source #

GroupOrder a => GroupOrder (Identity a) Source # 
Instance details

Defined in Data.Group.Order

Methods

order :: Identity a -> Order Source #

GroupOrder a => GroupOrder (Dual a) Source # 
Instance details

Defined in Data.Group.Order

Methods

order :: Dual a -> Order Source #

GroupOrder (Sum Int) Source # 
Instance details

Defined in Data.Group.Order

Methods

order :: Sum Int -> Order Source #

GroupOrder (Sum Int8) Source # 
Instance details

Defined in Data.Group.Order

Methods

order :: Sum Int8 -> Order Source #

GroupOrder (Sum Int16) Source # 
Instance details

Defined in Data.Group.Order

Methods

order :: Sum Int16 -> Order Source #

GroupOrder (Sum Int32) Source # 
Instance details

Defined in Data.Group.Order

Methods

order :: Sum Int32 -> Order Source #

GroupOrder (Sum Int64) Source # 
Instance details

Defined in Data.Group.Order

Methods

order :: Sum Int64 -> Order Source #

GroupOrder (Sum Integer) Source # 
Instance details

Defined in Data.Group.Order

Methods

order :: Sum Integer -> Order Source #

GroupOrder (Sum Rational) Source # 
Instance details

Defined in Data.Group.Order

GroupOrder (Sum Word) Source # 
Instance details

Defined in Data.Group.Order

Methods

order :: Sum Word -> Order Source #

GroupOrder (Sum Word8) Source # 
Instance details

Defined in Data.Group.Order

Methods

order :: Sum Word8 -> Order Source #

GroupOrder (Sum Word16) Source # 
Instance details

Defined in Data.Group.Order

Methods

order :: Sum Word16 -> Order Source #

GroupOrder (Sum Word32) Source # 
Instance details

Defined in Data.Group.Order

Methods

order :: Sum Word32 -> Order Source #

GroupOrder (Sum Word64) Source # 
Instance details

Defined in Data.Group.Order

Methods

order :: Sum Word64 -> Order Source #

GroupOrder (Product Rational) Source # 
Instance details

Defined in Data.Group.Order

GroupOrder a => GroupOrder (Down a) Source # 
Instance details

Defined in Data.Group.Order

Methods

order :: Down a -> Order Source #

Ord a => GroupOrder (FreeAbelianGroup a) Source # 
Instance details

Defined in Data.Group.Free.Internal

Eq a => GroupOrder (FreeGroup a) Source # 
Instance details

Defined in Data.Group.Free

Methods

order :: FreeGroup a -> Order Source #

(GroupOrder a, GroupOrder b) => GroupOrder (a, b) Source # 
Instance details

Defined in Data.Group.Order

Methods

order :: (a, b) -> Order Source #

GroupOrder (Proxy a) Source # 
Instance details

Defined in Data.Group.Order

Methods

order :: Proxy a -> Order Source #

(GroupOrder g, GroupOrder h) => GroupOrder (FreeProduct g h) Source # 
Instance details

Defined in Data.Group.Free.Product

Methods

order :: FreeProduct g h -> Order Source #

(GroupOrder a, GroupOrder b, GroupOrder c) => GroupOrder (a, b, c) Source # 
Instance details

Defined in Data.Group.Order

Methods

order :: (a, b, c) -> Order Source #

GroupOrder a => GroupOrder (Const a b) Source # 
Instance details

Defined in Data.Group.Order

Methods

order :: Const a b -> Order Source #

(GroupOrder a, GroupOrder b, GroupOrder c, GroupOrder d) => GroupOrder (a, b, c, d) Source # 
Instance details

Defined in Data.Group.Order

Methods

order :: (a, b, c, d) -> Order Source #

(GroupOrder a, GroupOrder b, GroupOrder c, GroupOrder d, GroupOrder e) => GroupOrder (a, b, c, d, e) Source # 
Instance details

Defined in Data.Group.Order

Methods

order :: (a, b, c, d, e) -> Order Source #

Order

data Order Source #

The order of a group element.

The order of a group element can either be infinite, as in the case of Sum Integer, or finite, as in the case of Sum Word8.

Constructors

Infinite 
Finite !Natural 

Instances

Instances details
Eq Order Source # 
Instance details

Defined in Data.Group.Order

Methods

(==) :: Order -> Order -> Bool #

(/=) :: Order -> Order -> Bool #

Show Order Source # 
Instance details

Defined in Data.Group.Order

Methods

showsPrec :: Int -> Order -> ShowS #

show :: Order -> String #

showList :: [Order] -> ShowS #

pattern Infinitary :: GroupOrder g => g Source #

Unidirectional pattern synonym for the infinite order of a group element.

pattern Finitary :: GroupOrder g => Natural -> g Source #

Unidirectional pattern synonym for the finite order of a group element.

orderForBits :: (Integral a, FiniteBits a) => Sum a -> Order Source #

An efficient implementation of order for additive group of fixed-width integers, like Int or Word8.

lcmOrder :: Order -> Order -> Order Source #

lcmOrder x y calculates the least common multiple of two Orders.

If both x and y are finite, it returns Finite r where r is the least common multiple of them. Otherwise, it returns Infinite.

Examples:

>>> lcmOrder (Finite 2) (Finite 5)
Finite 10
>>> lcmOrder (Finite 2) (Finite 10)
Finite 10
>>> lcmOrder (Finite 1) Infinite
Infinite

class (Group g, Bounded g) => FiniteGroup g Source #

A FiniteGroup is a Group whose underlying set is finite. This is equivalently a group object in \( FinSet \).

Finite groups often arise when considering symmetry of mathematical or physical objects, when those objects admit just a finite number of structure-preserving transformations. Important examples of finite groups include cyclic groups and permutation groups.

Instances

Instances details
FiniteGroup () Source # 
Instance details

Defined in Data.Group.Finite

FiniteGroup a => FiniteGroup (Identity a) Source # 
Instance details

Defined in Data.Group.Finite

FiniteGroup a => FiniteGroup (Dual a) Source # 
Instance details

Defined in Data.Group.Finite

(Bounded a, Num a) => FiniteGroup (Sum a) Source # 
Instance details

Defined in Data.Group.Finite

(FiniteGroup a, FiniteGroup b) => FiniteGroup (a, b) Source # 
Instance details

Defined in Data.Group.Finite

FiniteGroup a => FiniteGroup (Proxy a) Source # 
Instance details

Defined in Data.Group.Finite

(FiniteGroup a, FiniteGroup b, FiniteGroup c) => FiniteGroup (a, b, c) Source # 
Instance details

Defined in Data.Group.Finite

FiniteGroup a => FiniteGroup (Const a b) Source # 
Instance details

Defined in Data.Group.Finite

(FiniteGroup a, FiniteGroup b, FiniteGroup c, FiniteGroup d) => FiniteGroup (a, b, c, d) Source # 
Instance details

Defined in Data.Group.Finite

(FiniteGroup a, FiniteGroup b, FiniteGroup c, FiniteGroup d, FiniteGroup e) => FiniteGroup (a, b, c, d, e) Source # 
Instance details

Defined in Data.Group.Finite

finiteOrder :: (Eq g, FiniteGroup g) => g -> Natural Source #

Calculate the exponent of a particular element in a finite group.

Examples:

>>> finiteOrder @(Sum Word8) 3
256