| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Nominal.Permutation
Description
This module provides an efficient implementation of finitely
supported permutations of atoms. Compositions and inverses can
both be computed with O(n) Map lookup operations.
- newtype Perm = Perm (Map Atom Atom)
- p_identity :: Perm
- p_composeR :: Perm -> Perm -> Perm
- p_composeL :: Perm -> Perm -> Perm -> Perm
- p_apply_atom :: Perm -> Atom -> Atom
- p_swap :: Atom -> Atom -> Perm
- p_domain :: Perm -> [Atom]
- data NominalPermutation = Permutation Perm Perm
- type Permutation = NominalPermutation
- perm_identity :: Permutation
- perm_composeR :: Permutation -> Permutation -> Permutation
- perm_composeL :: Permutation -> Permutation -> Permutation
- perm_invert :: Permutation -> Permutation
- perm_apply_atom :: Permutation -> Atom -> Atom
- perm_swap :: Atom -> Atom -> Permutation
- perm_swaps :: [(Atom, Atom)] -> Permutation
- perm_domain :: Permutation -> [Atom]
- perm_of_swaps :: [(Atom, Atom)] -> Permutation
- swaps_of_perm :: Permutation -> [(Atom, Atom)]
The monoid of permutations
The monoid of finitely supported permutations on atoms.
p_identity :: Perm Source #
The identity permutation. O(1).
p_composeR :: Perm -> Perm -> Perm Source #
Compose two permutations. O(m) where m is the size of the right permutation.
p_composeL :: Perm -> Perm -> Perm -> Perm Source #
Compose two permutations. O(n) where n is the size of the left permutation. This also requires the inverse of the right permutation as an input.
The group of permutations
data NominalPermutation Source #
The group of finitely supported permutations on atoms. This is an abstract type with no exposed structure.
Constructors
| Permutation Perm Perm | Implementation note: If we used |
Instances
type Permutation = NominalPermutation Source #
A type synonym.
perm_identity :: Permutation Source #
The identity permutation. O(1).
perm_composeR :: Permutation -> Permutation -> Permutation Source #
Compose two permutations. O(m) where m is the size of the right permutation.
perm_composeL :: Permutation -> Permutation -> Permutation Source #
Compose two permutations. O(n) where n is the size of the left permutation.
perm_invert :: Permutation -> Permutation Source #
Invert a permutation. O(1).
perm_apply_atom :: Permutation -> Atom -> Atom Source #
Apply a permutation to an atom. O(1).
perm_swaps :: [(Atom, Atom)] -> Permutation Source #
Swap the given pairs of atoms.
perm_domain :: Permutation -> [Atom] Source #
The domain of a permutation. O(n).
perm_of_swaps :: [(Atom, Atom)] -> Permutation Source #
Make a permutation from a list of swaps. This is mostly useful for testing. O(n).
swaps_of_perm :: Permutation -> [(Atom, Atom)] Source #
Turn a permutation into a list of swaps. This is mostly useful for testing. O(n).