Data.Group.Permutation

This module provides definitions for Permutations along with useful combinators.

Permutation groups

data Permutation a

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:

>>> 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

Fields

• to :: a -> a

  The forward half of the bijection

• from :: a -> a

  The inverse half of the bijection

Instances

Semigroup (Permutation a)

Defined in Data.Group.Permutation

Methods

(<>) :: Permutation a -> Permutation a -> Permutation a

sconcat :: NonEmpty (Permutation a) -> Permutation a

stimes :: Integral b => b -> Permutation a -> Permutation a

Monoid (Permutation a)

Defined in Data.Group.Permutation

Methods

mempty :: Permutation a

mappend :: Permutation a -> Permutation a -> Permutation a

mconcat :: [Permutation a] -> Permutation a

Group (Permutation a)

Defined in Data.Group.Permutation

Methods

invert :: Permutation a -> Permutation a

(~~) :: 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

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

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

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

Build a Permutation from a bijective pair.

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

Destroy a Permutation, producing the underlying pair of bijections.

(-$) :: Permutation a -> a -> a infixr 0

Infix alias for the to half of Permutation bijection

($-) :: Permutation a -> a -> a infixr 0

Infix alias for the from half of Permutation bijection

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

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

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

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

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