Copyright | (c) 2020 Emily Pillmore |
---|---|

License | BSD-style |

Maintainer | Emily Pillmore <emilypi@cohomolo.gy>, Reed Mullanix <reedmullanix@gmail.com> |

Stability | stable |

Portability | non-portable |

Safe Haskell | Safe |

Language | Haskell2010 |

This module contains definitions for `Group`

and `AbelianGroup`

,
along with the relevant combinators.

## Synopsis

- class Monoid a => Group a where
- (><) :: Group a => a -> a -> a
- conjugate :: Group a => a -> a -> a
- unconjugate :: Group a => a -> a -> a
- pattern Conjugate :: Group a => (a, a) -> (a, a)
- data Order
- pattern Infinitary :: (Eq g, Group g) => g
- pattern Finitary :: (Eq g, Group g) => Natural -> g
- order :: (Eq g, Group g) => g -> Order
- data Abelianizer a
- abelianize :: (Eq g, Group g) => g -> g -> Abelianizer g
- commutate :: Group g => g -> g -> g
- pattern Abelianized :: (Eq g, Group g) => g -> (g, g)
- pattern Quotiented :: (Eq g, Group g) => (g, g)
- class Group a => AbelianGroup a

# Groups

class Monoid a => Group a where Source #

The typeclass of groups (types with an associative binary operation that
has an identity, and all inverses, i.e. a `Monoid`

with all inverses),
representing the structural symmetries of a mathematical object.

Instances should satisfy the following:

- Right identity
`x`

`<>`

`mempty`

= x- Left identity
`mempty`

`<>`

x = x- Associativity
`x`

`<>`

(y`<>`

z) = (x`<>`

y)`<>`

z- Concatenation
`mconcat`

=`foldr`

(`<>`

)`mempty`

- Right inverses
`x`

`<>`

`invert`

x =`mempty`

- Left inverses
`invert`

x`<>`

x =`mempty`

Some types can be viewed as a group in more than one way,
e.g. both addition and multiplication on numbers.
In such cases we often define `newtype`

s and make those instances
of `Group`

, e.g. `Sum`

and `Product`

.
Often in practice such differences between addition and
multiplication-like operations matter (e.g. when defining rings), and
so, classes "additive" (the underlying operation is addition-like) and
"multiplicative" group classes are provided in vis `AdditiveGroup`

and
`MultiplicativeGroup`

.

Categorically, `Group`

s may be viewed single-object groupoids.

#### Instances

# Group combinators

(><) :: Group a => a -> a -> a infixr 6 Source #

Apply `(`

, commuting its arguments. When the group is abelian,
`<>`

)`a <> b`

is identically `b <> a`

.

## Conjugation

conjugate :: Group a => a -> a -> a Source #

Conjugate an element of a group by another element. When the group is abelian, conjugation is the identity.

Symbolically, this is \( (g,a) \mapsto gag^{-1} \).

**Examples**:

`>>>`

`let x = Sum (3 :: Int)`

`>>>`

Sum {getSum = 3}`conjugate x x`

`>>>`

`let x = All True`

`>>>`

All {getAll = False}`conjugate (All False) x`

unconjugate :: Group a => a -> a -> a Source #

Apply an inverse conjugate to a conjugated element.

unconjugate . conjugate = id conjugate . unconjugate = id

**Examples**:

`>>>`

`let x = Sum (3 :: Int)`

`>>>`

Sum {getSum = 3}`unconjugate x (conjugate x x)`

pattern Conjugate :: Group a => (a, a) -> (a, a) Source #

Bidirectional pattern for conjugation by a group element

**Note:** When the underlying `Group`

is abelian, this
pattern is the identity.

## Order

The order of a group element.

The order of a group element can either be infinite,
as in the case of `All False`

, or finite, as in the
case of `All True`

.

pattern Infinitary :: (Eq g, Group g) => g Source #

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

pattern Finitary :: (Eq g, Group g) => Natural -> g Source #

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

order :: (Eq g, Group g) => g -> Order Source #

Calculate the exponent of a particular element in a group.

**Warning:** If `order`

expects a `FiniteGroup`

, this is gauranteed
to terminate. However, this is not true of groups in general. This will
spin forever if you give it something like non-zero `Sum Integer`

.

**Examples**:

`>>>`

Finite 255`order @(Sum Word8) 3`

`>>>`

Finite 1`order (Any False)`

`>>>`

Infinite`order (All False)`

## Abelianization

data Abelianizer a Source #

Quotient a pair of group elements by their commutator.

The of the quotient \( G / [G,G] \) forms an abelian group, and `Abelianizer`

forms a functor from the category of groups to the category of Abelian groups.
This functor is left adjoint to the inclusion functor \( Ab \rightarrow Grp \),
forming a monad in \( Grp \).

#### Instances

abelianize :: (Eq g, Group g) => g -> g -> Abelianizer g Source #

Quotient a pair of group elements by their commutator.

Ranging over the entire group, this operation constructs the quotient of the group by its commutator sub-group \( G / [G,G] \).

pattern Abelianized :: (Eq g, Group g) => g -> (g, g) Source #

A unidirectional pattern synonym for elements of a group
modulo commutators which are **not** the identity.

pattern Quotiented :: (Eq g, Group g) => (g, g) Source #

A unidirectional pattern synonym for elements of a group modulo commutators which are the identity.

# Abelian groups

class Group a => AbelianGroup a Source #

Commutative `Group`

s.

Instances of `AbelianGroup`

satisfy the following laws:

- Commutativity
`x <> y = y <> x`