Copyright	(c) 2020 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
}
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
>>> c1 <> c1 == mempty
True
>>> order c1
Finite 2

Constructors

Permutation
Fields to :: a -> a The forward half of the bijection from :: a -> a The inverse half of the bijection

Instances

(Enum a, Bounded a) => Eq (Permutation a) Source #
Instance details Defined in Data.Group.Permutation Methods (==) :: Permutation a -> Permutation a -> Bool # (/=) :: Permutation a -> Permutation a -> Bool #
(Enum a, Bounded a) => Ord (Permutation a) Source #
Instance details Defined in Data.Group.Permutation Methods compare :: Permutation a -> Permutation a -> Ordering # (<) :: Permutation a -> Permutation a -> Bool # (<=) :: Permutation a -> Permutation a -> Bool # (>) :: Permutation a -> Permutation a -> Bool # (>=) :: Permutation a -> Permutation a -> Bool # max :: Permutation a -> Permutation a -> Permutation a # min :: Permutation a -> Permutation a -> Permutation a #
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 #
(Enum a, Bounded a) => GroupOrder (Permutation a) Source #
Instance details Defined in Data.Group.Permutation Methods order :: Permutation a -> Order Source #

Permutation group combinators

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.