sym-0.9: Permutations, patterns, and statistics

Maintainer Anders Claesson None

Math.Sym

Description

Synopsis

# Documentation

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.

Methods

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.

Instances

 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 `Perm`s to one on any permutations.

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

Like `lift` but for functions of two variables.