nominal-0.2.0.0: Binders and alpha-equivalence made easy

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.

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.

Synopsis

# The monoid of permutations

newtype Perm Source #

The monoid of finitely supported permutations on atoms.

Constructors

 Perm (Map Atom Atom)

Instances

 Source # Methods(==) :: Perm -> Perm -> Bool #(/=) :: Perm -> Perm -> Bool # Source # MethodsshowsPrec :: Int -> Perm -> ShowS #show :: Perm -> String #showList :: [Perm] -> ShowS #

The identity permutation. O(1).

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

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.

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

Swap a and b. O(1).

p_domain :: Perm -> [Atom] Source #

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

# The group of permutations

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

 Source # Methods

A type synonym.

The identity permutation. O(1).

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

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

Invert a permutation. O(1).

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

Swap a and b. O(1).

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

Swap the given pairs of atoms.

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