Safe Haskell | None |
---|---|

Language | Haskell2010 |

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.

This module exposes implementation details of the Nominal library, and should not normally be imported. Users of the library should only import the top-level module Nominal.

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

Permutation Perm Perm | Implementation note: If we used |

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*).