Sym

Documentation

class Permutation a where

The class of permutations. Minimal complete definition: st, act and idperm. The default implementation of size can be somewhat slow, so you may want to implement it as well.

Minimal complete definition

st, act, idperm

Methods

st :: a -> Perm

The standardization map. If there is an underlying linear order on a then st is determined by the unique order preserving map from [0..] to that order. In any case, the standardization map should be equivariant with respect to the group action defined below; i.e., it should hold that

st (u `act` v) == u `act` st v

act :: Perm -> a -> a

A (left) group action of Perm on a. As for any group action it should hold that

(u `act` v) `act` w == u `act` (v `act` w)   &&   idperm n `act` v == v

where v,w::a and u::Perm are of size n.

size :: a -> Int

The size of a permutation. The default implementation derived from

size == size . st

This is not a circular definition as size on Perm is implemented independently. If the implementation of st is slow, then it can be worth while to override the standard definiton; any implementation should, however, satisfy the identity above.

idperm :: Int -> a

The identity permutation of the given size.

inverse :: a -> a

The group theoretical inverse. It should hold that

inverse == unst . inverse . st

and this is the default implementation.

ordiso :: Perm -> a -> Bool

Predicate determining if two permutations are order-isomorphic. The default implementation uses

u `ordiso` v  ==  u == st v

Equivalently, one could use

u `ordiso` v  ==  inverse u `act` v == idperm (size u)

unst :: Perm -> a

The inverse of st. It should hold that

unst w == w `act` idperm (P.size w)

and this is the default implementation.

Instances

Permutation String

A String viewed as a permutation of its characters. The alphabet is ordered as

['1'..'9'] ++ ['A'..'Z'] ++ ['a'..]

Methods

st :: String -> Perm

act :: Perm -> String -> String

size :: String -> Int

idperm :: Int -> String

inverse :: String -> String

ordiso :: Perm -> String -> Bool

unst :: Perm -> String

Permutation Perm

Methods

st :: Perm -> Perm

act :: Perm -> Perm -> Perm

size :: Perm -> Int

idperm :: Int -> Perm

inverse :: Perm -> Perm

ordiso :: Perm -> Perm -> Bool

unst :: Perm -> Perm

Permutation SSYTPair

Methods

st :: SSYTPair -> Perm

act :: Perm -> SSYTPair -> SSYTPair

size :: SSYTPair -> Int

idperm :: Int -> SSYTPair

inverse :: SSYTPair -> SSYTPair

ordiso :: Perm -> SSYTPair -> Bool

unst :: Perm -> SSYTPair

perms :: Permutation a => Int -> [a]

The list of all permutations of the given size.

lift :: Permutation a => (Perm -> Perm) -> a -> a

Lifts a function on Perms to one on any permutations.

lift2 :: Permutation a => (Perm -> Perm -> Perm) -> a -> a -> a

Like lift but for functions of two variables.