sym-0.9: Permutations, patterns, and statistics

MaintainerAnders Claesson <>
Safe HaskellNone






class Ord a => Permutation a whereSource

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.


st :: a -> PermSource

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

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

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

The identity permutation of the given size.

inverse :: a -> aSource

The group theoretical inverse. It should hold that

 inverse == unst . inverse . st

and this is the default implementation.

ordiso :: Perm -> a -> BoolSource

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 :: Permutation a => Perm -> aSource

The inverse of st. It should hold that

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

and this is the default implementation.


Permutation String

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

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

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

The list of all permutations of the given size.

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

Lifts a function on Perms to one on any permutations.

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

Like lift but for functions of two variables.