Copyright	(c) 2020-2021 Emily Pillmore
License	BSD-style
Maintainer	Reed Mullanix <reedmullanix@gmail.com>, Emily Pillmore <emilypi@cohomolo.gy>
Stability	stable
Portability	non-portable
Safe Haskell	Safe
Language	Haskell2010

Data.Group.Permutation

Contents

Permutation groups
- Permutation group combinators
- Permutation patterns

Description

This module provides definitions for Permutations along with useful combinators.

Synopsis

data Permutation a = Permutation {
- to :: a -> a
- from :: a -> a
}
equalPermutation :: (Enum a, Bounded a) => Permutation a -> Permutation a -> Bool
comparePermutation :: (Enum a, Bounded a) => Permutation a -> Permutation a -> Ordering
orderOfPermutation :: forall a. (Enum a, Bounded a) => Permutation a -> Natural
permute :: (a -> a) -> (a -> a) -> Permutation a
pairwise :: Permutation a -> (a -> a, a -> a)
(-$) :: Permutation a -> a -> a
($-) :: Permutation a -> a -> a
embed :: Group g => g -> Permutation g
retract :: Group g => Permutation g -> g
pattern Permute :: Group g => Permutation g -> g

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
Fields to :: a -> a The forward half of the bijection from :: a -> a The inverse half of the bijection

Instances

Instances details

Semigroup (Permutation a) Source #
Instance details 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) Source #
Instance details Defined in Data.Group.Permutation Methods mempty :: Permutation a # mappend :: Permutation a -> Permutation a -> Permutation a # mconcat :: [Permutation a] -> Permutation a #
Group (Permutation a) Source #
Instance details 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 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.