group-theory-0.2.1.0: The theory of groups
Copyright (c) 2020-2021 Emily Pillmore BSD-style Reed Mullanix , Emily Pillmore stable non-portable Safe Haskell2010

Data.Group.Permutation

Description

This module provides definitions for Permutations along with useful combinators.

Synopsis

# Permutation groups

data Permutation a Source #

Isomorphism of a type onto itself. Each entry consists of one half of the isomorphism.

Note: It is the responsibility of the user to provide inverse proofs for to and from. Be responsible!

### Examples:

Expand
>>> p1 = permute succ pred :: Permutation Integer
>>> p2 = permute negate negate :: Permutation Integer
>>> to (p1 <> p2) 2
-1
>>> from (p1 <> p2) (-1)
2
>>> to (p2 <> p1) 2
-3


Permutations on a finite set a (, indicated by satisfying (Bounded a, Enum a) constraint,) can be tested their equality and computed their orders.

>>> c1 = permute not not :: Permutation Bool
>>> equalPermutation (c1 <> c1) mempty
True
>>> orderOfPermutation c1
2


Constructors

 Permutation Fieldsto :: a -> aThe forward half of the bijectionfrom :: a -> aThe inverse half of the bijection

#### Instances

Instances details
 Source # Instance detailsDefined in Data.Group.Permutation Methods(<>) :: Permutation a -> Permutation a -> Permutation a #stimes :: Integral b => b -> Permutation a -> Permutation a # Source # Instance detailsDefined in Data.Group.Permutation Methodsmappend :: Permutation a -> Permutation a -> Permutation a #mconcat :: [Permutation a] -> Permutation a # Source # Instance detailsDefined in Data.Group.Permutation Methods(~~) :: Permutation a -> Permutation a -> Permutation a #pow :: Integral x => Permutation a -> x -> Permutation a #

## Permutation group combinators

equalPermutation :: (Enum a, Bounded a) => Permutation a -> Permutation a -> Bool Source #

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.

comparePermutation :: (Enum a, Bounded a) => Permutation a -> Permutation a -> Ordering Source #

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.

orderOfPermutation :: forall a. (Enum a, Bounded a) => Permutation a -> Natural Source #

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.

permute :: (a -> a) -> (a -> a) -> Permutation a Source #

Build a Permutation from a bijective pair.

pairwise :: Permutation a -> (a -> a, a -> a) Source #

Destroy a Permutation, producing the underlying pair of bijections.

(-$) :: Permutation a -> a -> a infixr 0 Source # Infix alias for the to half of Permutation bijection ($-) :: Permutation a -> a -> a infixr 0 Source #

Infix alias for the from half of Permutation bijection

embed :: Group g => g -> Permutation g Source #

Embed a Group into the Permutation group on it's underlying set.

retract :: Group g => Permutation g -> g Source #

Get a group element out of the permutation group. This is a left inverse to embed, i.e.

   retract . embed = id


## Permutation patterns

pattern Permute :: Group g => Permutation g -> g Source #

Bidirectional pattern synonym for embedding/retraction of groups into their permutation groups.