License | BSD-like (see LICENSE) |
---|---|

Maintainer | Stephanie Weirich <sweirich@cis.upenn.edu> |

Portability | portable |

Safe Haskell | Safe |

Language | Haskell2010 |

A slow, but hopefully correct implementation of permutations.

## Synopsis

- newtype Perm a = Perm (Map a a)
- single :: Ord a => a -> a -> Perm a
- compose :: Ord a => Perm a -> Perm a -> Perm a
- apply :: Ord a => Perm a -> a -> a
- support :: Ord a => Perm a -> [a]
- isid :: Ord a => Perm a -> Bool
- join :: Ord a => Perm a -> Perm a -> Maybe (Perm a)
- empty :: Perm a
- restrict :: Ord a => Perm a -> [a] -> Perm a
- mkPerm :: Ord a => [a] -> [a] -> Maybe (Perm a)

# Documentation

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.

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

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

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

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