Copyright	(c) 2011 Stephanie Weirich <sweirich@cis.upenn.edu>
License	BSD-like (see PermM.hs)
Maintainer	Aleksey Kliger
Portability	portable
Safe Haskell	Safe
Language	Haskell2010

Unbound.Generics.PermM

Description

A slow, but hopefully correct implementation of permutations.

Synopsis

Documentation

newtype Perm a Source #

A permutation is a bijective function from names to names which is the identity on all but a finite set of names. They form the basis for nominal approaches to binding, but can also be useful in general.

Constructors

Perm (Map a a)

Instances

Ord a => Eq (Perm a) Source #
Methods (==) :: Perm a -> Perm a -> Bool # (/=) :: Perm a -> Perm a -> Bool #
Show a => Show (Perm a) Source #
Methods showsPrec :: Int -> Perm a -> ShowS # show :: Perm a -> String # showList :: [Perm a] -> ShowS #
Ord a => Semigroup (Perm a) Source #	Permutations form a semigroup under `compose`. @since 0.3.2
Methods (<>) :: Perm a -> Perm a -> Perm a # sconcat :: NonEmpty (Perm a) -> Perm a # stimes :: Integral b => b -> Perm a -> Perm a #
Ord a => Monoid (Perm a) Source #	Permutations form a monoid with identity `empty`.
Methods mempty :: Perm a # mappend :: Perm a -> Perm a -> Perm a # mconcat :: [Perm a] -> Perm a #

permValid :: Ord a => Perm a -> Bool Source #

permValid p returns True iff the perumation is valid: if each value in the range of the permutation is also a key.

single :: Ord a => a -> a -> Perm a Source #

Create a permutation which swaps two elements.

compose :: Ord a => Perm a -> Perm a -> Perm a Source #

Compose two permutations. The right-hand permutation will be applied first.

apply :: Ord a => Perm a -> a -> a Source #

Apply a permutation to an element of the domain.

support :: Ord a => Perm a -> [a] Source #

The support of a permutation is the set of elements which are not fixed.

isid :: Ord a => Perm a -> Bool Source #

Is this the identity permutation?

join :: Ord a => Perm a -> Perm a -> Maybe (Perm a) Source #

Join two permutations by taking the union of their relation graphs. Fail if they are inconsistent, i.e. map the same element to two different elements.

empty :: Perm a Source #

The empty (identity) permutation.

restrict :: Ord a => Perm a -> [a] -> Perm a Source #

Restrict a permutation to a certain domain.

mkPerm :: Ord a => [a] -> [a] -> Maybe (Perm a) Source #

mkPerm l1 l2 creates a permutation that sends l1 to l2. Fail if there is no such permutation, either because the lists have different lengths or because they are inconsistent (which can only happen if l1 or l2 have repeated elements).