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 |

This module provides definitions for `Permutation`

s
along with useful combinators.

## Synopsis

- data Permutation a = Permutation {}
- 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:

`>>>`

`p1 = permute succ pred :: Permutation Integer`

`>>>`

`p2 = permute negate negate :: Permutation Integer`

`>>>`

-1`to (p1 <> p2) 2`

`>>>`

2`from (p1 <> p2) (-1)`

`>>>`

-3`to (p2 <> p1) 2`

Permutations on a finite set `a`

(, indicated by satisfying
`(Bounded a, Enum a)`

constraint,) can be tested their equality
and computed their `order`

s.

`>>>`

`c1 = permute not not :: Permutation Bool`

`>>>`

True`equalPermutation (c1 <> c1) mempty`

`>>>`

2`orderOfPermutation c1`

#### Instances

Semigroup (Permutation a) Source # | |

Defined in Data.Group.Permutation (<>) :: Permutation a -> Permutation a -> Permutation a # sconcat :: NonEmpty (Permutation a) -> Permutation a # stimes :: Integral b => b -> Permutation a -> Permutation a # | |

Monoid (Permutation a) Source # | |

Defined in Data.Group.Permutation mempty :: Permutation a # mappend :: Permutation a -> Permutation a -> Permutation a # mconcat :: [Permutation a] -> Permutation a # | |

Group (Permutation a) Source # | |

Defined in Data.Group.Permutation 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.