Data.Group.Order

This module contains definitions for GroupOrder.

Group order

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

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

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

GroupOrder ()

Defined in Data.Group.Order

Methods

order :: () -> Order

GroupOrder a => GroupOrder (Identity a)

Defined in Data.Group.Order

Methods

order :: Identity a -> Order

GroupOrder a => GroupOrder (Dual a)

Defined in Data.Group.Order

Methods

order :: Dual a -> Order

GroupOrder (Sum Int)

Defined in Data.Group.Order

Methods

order :: Sum Int -> Order

GroupOrder (Sum Int8)

Defined in Data.Group.Order

Methods

order :: Sum Int8 -> Order

GroupOrder (Sum Int16)

Defined in Data.Group.Order

Methods

order :: Sum Int16 -> Order

GroupOrder (Sum Int32)

Defined in Data.Group.Order

Methods

order :: Sum Int32 -> Order

GroupOrder (Sum Int64)

Defined in Data.Group.Order

Methods

order :: Sum Int64 -> Order

GroupOrder (Sum Integer)

Defined in Data.Group.Order

Methods

order :: Sum Integer -> Order

GroupOrder (Sum Rational)

Defined in Data.Group.Order

Methods

order :: Sum Rational -> Order

GroupOrder (Sum Word)

Defined in Data.Group.Order

Methods

order :: Sum Word -> Order

GroupOrder (Sum Word8)

Defined in Data.Group.Order

Methods

order :: Sum Word8 -> Order

GroupOrder (Sum Word16)

Defined in Data.Group.Order

Methods

order :: Sum Word16 -> Order

GroupOrder (Sum Word32)

Defined in Data.Group.Order

Methods

order :: Sum Word32 -> Order

GroupOrder (Sum Word64)

Defined in Data.Group.Order

Methods

order :: Sum Word64 -> Order

GroupOrder (Product Rational)

Defined in Data.Group.Order

Methods

order :: Product Rational -> Order

GroupOrder a => GroupOrder (Down a)

Defined in Data.Group.Order

Methods

order :: Down a -> Order

Ord a => GroupOrder (FreeAbelianGroup a)

Defined in Data.Group.Free.Internal

Methods

order :: FreeAbelianGroup a -> Order

Eq a => GroupOrder (FreeGroup a)

Defined in Data.Group.Free

Methods

order :: FreeGroup a -> Order

(Enum a, Bounded a) => GroupOrder (Permutation a)

Defined in Data.Group.Permutation

Methods

order :: Permutation a -> Order

(GroupOrder a, GroupOrder b) => GroupOrder (a, b)

Defined in Data.Group.Order

Methods

order :: (a, b) -> Order

GroupOrder (Proxy a)

Defined in Data.Group.Order

Methods

order :: Proxy a -> Order

(GroupOrder g, GroupOrder h) => GroupOrder (FreeProduct g h)

Defined in Data.Group.Free.Product

Methods

order :: FreeProduct g h -> Order

(GroupOrder a, GroupOrder b, GroupOrder c) => GroupOrder (a, b, c)

Defined in Data.Group.Order

Methods

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

GroupOrder a => GroupOrder (Const a b)

Defined in Data.Group.Order

Methods

order :: Const a b -> Order

(GroupOrder a, GroupOrder b, GroupOrder c, GroupOrder d) => GroupOrder (a, b, c, d)

Defined in Data.Group.Order

Methods

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

(GroupOrder a, GroupOrder b, GroupOrder c, GroupOrder d, GroupOrder e) => GroupOrder (a, b, c, d, e)

Defined in Data.Group.Order

Methods

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

Order

data Order

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

Eq Order

Defined in Data.Group.Order

Methods

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

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

Show Order

Defined in Data.Group.Order

Methods

showsPrec :: Int -> Order -> ShowS

show :: Order -> String

showList :: [Order] -> ShowS

pattern Infinitary :: GroupOrder g => g

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

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

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

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

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

lcmOrder :: Order -> Order -> Order

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

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

FiniteGroup ()

Defined in Data.Group.Finite

FiniteGroup a => FiniteGroup (Identity a)

Defined in Data.Group.Finite

FiniteGroup a => FiniteGroup (Dual a)

Defined in Data.Group.Finite

(Bounded a, Num a) => FiniteGroup (Sum a)

Defined in Data.Group.Finite

(FiniteGroup a, FiniteGroup b) => FiniteGroup (a, b)

Defined in Data.Group.Finite

FiniteGroup a => FiniteGroup (Proxy a)

Defined in Data.Group.Finite

(FiniteGroup a, FiniteGroup b, FiniteGroup c) => FiniteGroup (a, b, c)

Defined in Data.Group.Finite

FiniteGroup a => FiniteGroup (Const a b)

Defined in Data.Group.Finite

(FiniteGroup a, FiniteGroup b, FiniteGroup c, FiniteGroup d) => FiniteGroup (a, b, c, d)

Defined in Data.Group.Finite

(FiniteGroup a, FiniteGroup b, FiniteGroup c, FiniteGroup d, FiniteGroup e) => FiniteGroup (a, b, c, d, e)

Defined in Data.Group.Finite

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

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

Examples:

>>> finiteOrder @(Sum Word8) 3
256