Nominal.Permutation

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.

The monoid of permutations

newtype Perm

The monoid of finitely supported permutations on atoms.

Constructors

Perm (Map Atom Atom)

Instances

Eq Perm

Methods

(==) :: Perm -> Perm -> Bool

(/=) :: Perm -> Perm -> Bool

Show Perm

Methods

showsPrec :: Int -> Perm -> ShowS

show :: Perm -> String

showList :: [Perm] -> ShowS

p_identity :: Perm

The identity permutation. O(1).

p_composeR :: Perm -> Perm -> Perm

Compose two permutations. O(m) where m is the size of the right permutation.

p_composeL :: Perm -> Perm -> Perm -> Perm

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.

p_apply_atom :: Perm -> Atom -> Atom

Apply a permutation to an atom. O(1).

p_swap :: Atom -> Atom -> Perm

Swap a and b. O(1).

p_domain :: Perm -> [Atom]

Return the domain of a permutation. O(n).

The group of permutations

data NominalPermutation

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 Perm directly, inverting a permutation would be O(n). We make inverting O(1) by storing a permutation together with its inverse. Because of laziness, the inverse will not be computed unless it is used.

Instances

Eq NominalPermutation

Methods

(==) :: NominalPermutation -> NominalPermutation -> Bool

(/=) :: NominalPermutation -> NominalPermutation -> Bool

type Permutation = NominalPermutation

A type synonym.

perm_identity :: Permutation

The identity permutation. O(1).

perm_composeR :: Permutation -> Permutation -> Permutation

Compose two permutations. O(m) where m is the size of the right permutation.

perm_composeL :: Permutation -> Permutation -> Permutation

Compose two permutations. O(n) where n is the size of the left permutation.

perm_invert :: Permutation -> Permutation

Invert a permutation. O(1).

perm_apply_atom :: Permutation -> Atom -> Atom

Apply a permutation to an atom. O(1).

perm_swap :: Atom -> Atom -> Permutation

Swap a and b. O(1).

perm_swaps :: [(Atom, Atom)] -> Permutation

Swap the given pairs of atoms.

perm_domain :: Permutation -> [Atom]

The domain of a permutation. O(n).

perm_of_swaps :: [(Atom, Atom)] -> Permutation

Make a permutation from a list of swaps. This is mostly useful for testing. O(n).

swaps_of_perm :: Permutation -> [(Atom, Atom)]

Turn a permutation into a list of swaps. This is mostly useful for testing. O(n).