-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Permutations, patterns, and statistics
--
-- Definitions for permutations with an emphasis on permutation patterns
-- and permutation statistics.
@package sym
@version 0.13.0
module Sym.Internal.Util
-- | The list of minimal sets with respect to inclusion.
minima :: Ord a => [Set a] -> [Set a]
-- | The list of maximal sets with respect to inclusion.
maxima :: Ord a => [Set a] -> [Set a]
-- | A list of all k element subsets of the given set.
kSubsets :: Ord a => Int -> Set a -> [Set a]
-- | A list of all subsets of the given set.
powerset :: Ord a => Set a -> [Set a]
-- | Sort and remove duplicates.
nubSort :: Ord a => [a] -> [a]
module Sym.Internal.Size
class Size a
size :: Size a => a -> Int
instance Sym.Internal.Size.Size [a]
instance Sym.Internal.Size.Size (Data.Set.Base.Set a)
instance Sym.Internal.Size.Size a => Sym.Internal.Size.Size (GHC.Base.Maybe a)
-- | Convenience functions for dealing with arrays of CLongs.
module Sym.Internal.CLongArray
-- | An array of CLongs
data CLongArray
-- | Construct an array from a list of elements.
fromList :: [Int] -> CLongArray
-- | The list of elements.
toList :: CLongArray -> [Int]
-- | Slice a CLongArray into contiguous segments of the given sizes.
-- Each segment size must be positive and they must sum to the size of
-- the array.
slices :: [Int] -> CLongArray -> [CLongArray]
size :: Size a => a -> Int
-- | w `at` i is the value of w at i, where
-- i is in [0..size w-1].
at :: CLongArray -> Int -> Int
infixl 9 `at`
-- | Like at but without range checking.
unsafeAt :: CLongArray -> Int -> Int
infixl 9 `unsafeAt`
-- | The indices of all elements equal to the query element, in ascending
-- order.
elemIndices :: CLong -> CLongArray -> Vector Int
-- | Apply a function to every element of an array and its index.
imap :: (Int -> CLong -> CLong) -> CLongArray -> CLongArray
-- | Apply a function to corresponding pairs of elements and their (shared)
-- index.
izipWith :: (Int -> CLong -> CLong -> CLong) -> CLongArray -> CLongArray -> CLongArray
-- | Create a new array of the given size that is initialized through an IO
-- action.
unsafeNew :: Int -> (Ptr CLong -> IO ()) -> IO CLongArray
-- | Pass a pointer to the array to an IO action; the array may not be
-- modified through the pointer.
unsafeWith :: CLongArray -> (Ptr CLong -> IO a) -> IO a
instance GHC.Classes.Eq Sym.Internal.CLongArray.CLongArray
instance GHC.Classes.Ord Sym.Internal.CLongArray.CLongArray
instance Sym.Internal.Size.Size Sym.Internal.CLongArray.CLongArray
instance GHC.Show.Show Sym.Internal.CLongArray.CLongArray
module Sym.Internal.SubSeq
-- | A SubSeq is represented by an increasing array of non-negative
-- integers.
type SubSeq = CLongArray
-- | n `choose` k is the list of subsequences of [0..n-1]
-- with k elements.
choose :: Int -> Int -> [SubSeq]
instance Sym.Internal.SubSeq.Bitmask Foreign.C.Types.CLong
instance Sym.Internal.SubSeq.Bitmask GHC.Integer.Type.Integer
-- | Generating permutations: rank and unrank
module Sym.Perm
-- | A permutation is just a CLongArray. By convention a permutation
-- of size n is understood to be a permutation of
-- [0..n-1].
type Perm = CLongArray
-- | The unique permutation length zero.
emptyperm :: Perm
-- | The unique permutation length one.
one :: Perm
-- | The identity permutation.
idperm :: Int -> Perm
-- | The reverse of the identity permutation.
ebb :: Int -> Perm
-- | Construct a permutation from a list of elements. As opposed to
-- fromList this is a safe function in the sense that the output
-- of mkPerm xs is guaranteed to be a permutation of
-- [0..length xs-1]. E.g., mkPerm "baxa" == fromList
-- [2,0,3,1].
mkPerm :: Ord a => [a] -> Perm
-- | The rank of the given permutation, where the rank is defined as in [W.
-- Myrvold and F. Ruskey, Ranking and Unranking Permutations in Linear
-- Time, Information Processing Letters, 79 (2001) 281-284].
rank :: Perm -> Integer
-- | The permutation of size n whose rank is r, where the
-- rank is defined as in [W. Myrvold and F. Ruskey, Ranking and Unranking
-- Permutations in Linear Time, Information Processing Letters, 79 (2001)
-- 281-284].
unrank :: Int -> Integer -> Perm
-- | All permutations of a given size.
perms :: Int -> [Perm]
module Sym.Perm.Bijection
-- | The Simion-Schmidt bijection from Av(123) onto Av(132).
simionSchmidt :: Perm -> Perm
-- | The inverse of the Simion-Schmidt bijection. It is a function from
-- Av(132) to Av(123).
simionSchmidt' :: Perm -> Perm
module Sym.Perm.D8
-- | Ration by 0 degrees, i.e. the identity map.
r0 :: Perm -> Perm
-- | Ration by 90 degrees clockwise.
r1 :: Perm -> Perm
-- | Ration by 2*90 = 180 degrees clockwise.
r2 :: Perm -> Perm
-- | Ration by 3*90 = 270 degrees clockwise.
r3 :: Perm -> Perm
-- | Reflection through a horizontal axis (also called complement).
s0 :: Perm -> Perm
-- | Reflection through a vertical axis (also called reverse).
s1 :: Perm -> Perm
-- | Reflection through the main diagonal (also called inverse).
s2 :: Perm -> Perm
-- | Reflection through the anti-diagonal.
s3 :: Perm -> Perm
-- | The dihedral group of order 8 (the symmetries of a square); that is,
--
--
-- d8 = [r0, r1, r2, r3, s0, s1, s2, s3]
--
d8 :: [Perm -> Perm]
-- | The Klein four-group (the symmetries of a non-equilateral rectangle);
-- that is,
--
--
-- klein4 = [r0, r2, s0, s1]
--
klein4 :: [Perm -> Perm]
-- | orbit fs x is the orbit of x under the group
-- of function fs. E.g.,
--
--
-- orbit klein4 "2314" == ["1423","2314","3241","4132"]
--
orbit :: [Perm -> Perm] -> Perm -> [Perm]
-- | symmetryClasses fs xs is the list of equivalence classes
-- under the action of the group of functions fs.
symmetryClasses :: [Perm -> Perm] -> [Perm] -> [[Perm]]
-- | Symmetry classes with respect to D8.
d8Classes :: [Perm] -> [[Perm]]
-- | Symmetry classes with respect to Klein4
klein4Classes :: [Perm] -> [[Perm]]
-- |
-- rotate = r1 = inverse . reverse
--
rotate :: Perm -> Perm
-- | The complement of the given permutation: if v = complement u
-- then v `at` i = n - 1 - u `at` i.
complement :: Perm -> Perm
-- | The reverse of the given permutation: if v = reverse u then
-- v `at` i = u `at` (n-1-i).
reverse :: Perm -> Perm
-- | The group theoretical inverse: if v = inverse u then v
-- `at` (u `at` i) = i.
inverse :: Perm -> Perm
-- | Components of permutations.
module Sym.Perm.Component
-- | The list of (plus) components.
components :: Perm -> [Perm]
-- | The list of skew components, also called minus components.
skewComponents :: Perm -> [Perm]
-- | For each position, left-to-right, records the largest value seen thus
-- far.
leftMaxima :: Perm -> [Int]
-- | For each position, left-to-right, records the smallest value seen thus
-- far.
leftMinima :: Perm -> [Int]
-- | For each position, right-to-left, records the largest value
-- seen thus far.
rightMaxima :: Perm -> [Int]
-- | For each position, right-to-left, records the smallest value
-- seen thus far.
rightMinima :: Perm -> [Int]
module Sym.Perm.Group
-- | The product/composition of u and v: if w = u
-- compose v then w `at ` i = v `at` (u `at` i).
compose :: Perm -> Perm -> Perm
-- | The (left) group action of Perm on itself: if w = u act
-- v then w `at ` (u `at` i) = v `at` i.
act :: Perm -> Perm -> Perm
module Sym.Perm.MeshPattern
data MeshPattern
MP :: Perm -> Mesh -> MeshPattern
[getPerm] :: MeshPattern -> Perm
[getMesh] :: MeshPattern -> Mesh
-- | A mesh is a, possibly empty, set of shaded boxes.
type Mesh = Set Box
-- | A box is represented by the coordinates of its southwest corner.
type Box = (Int, Int)
mkPattern :: Ord a => [a] -> MeshPattern
pattern :: Perm -> MeshPattern
mesh :: [Box] -> MeshPattern -> MeshPattern
cols :: [Int] -> MeshPattern -> MeshPattern
rows :: [Int] -> MeshPattern -> MeshPattern
col :: Int -> MeshPattern -> MeshPattern
row :: Int -> MeshPattern -> MeshPattern
box :: Box -> MeshPattern -> MeshPattern
-- | copiesOf p w is the list of sets that represent copies of
-- p in w.
copiesOf :: MeshPattern -> Perm -> [SubSeq]
-- | w contains p is a predicate determining if w
-- contains the pattern p.
contains :: Perm -> MeshPattern -> Bool
-- | w avoids p is a predicate determining if w
-- avoids the pattern p.
avoids :: Perm -> MeshPattern -> Bool
-- | w avoidsAll ps is a predicate determining if
-- w avoids the patterns ps.
avoidsAll :: Perm -> [MeshPattern] -> Bool
-- | avoiders ps ws is the list of permutations in ws
-- avoiding the patterns in ps.
avoiders :: [MeshPattern] -> [Perm] -> [Perm]
kVincular :: Int -> Perm -> [MeshPattern]
vincular :: Perm -> [MeshPattern]
bivincular :: Perm -> [MeshPattern]
meshPatterns :: Perm -> [MeshPattern]
instance GHC.Classes.Ord Sym.Perm.MeshPattern.MeshPattern
instance GHC.Classes.Eq Sym.Perm.MeshPattern.MeshPattern
instance GHC.Show.Show Sym.Perm.MeshPattern.MeshPattern
instance Sym.Internal.Size.Size Sym.Perm.MeshPattern.MeshPattern
module Sym.Perm.Pattern
-- | Pattern is just an alias for permutation.
type Pattern = Perm
-- | A SubSeq is represented by an increasing array of non-negative
-- integers.
type SubSeq = CLongArray
-- | ordiso u v m determines whether the subword in v
-- specified by m is order isomorphic to u.
ordiso :: Pattern -> Perm -> SubSeq -> Bool
-- | n `choose` k is the list of subsequences of [0..n-1]
-- with k elements.
choose :: Int -> Int -> [SubSeq]
-- | copiesOf p w is the list of sets that represent copies of
-- p in w.
copiesOf :: Pattern -> Perm -> [SubSeq]
-- | w contains p is a predicate determining if w
-- contains the pattern p.
contains :: Perm -> Pattern -> Bool
-- | w avoids p is a predicate determining if w
-- avoids the pattern p.
avoids :: Perm -> Pattern -> Bool
-- | w avoidsAll ps is a predicate determining if
-- w avoids the patterns ps.
avoidsAll :: Perm -> [Pattern] -> Bool
-- | avoiders ps ws is the list of permutations in ws
-- avoiding the patterns in ps.
avoiders :: [Pattern] -> [Perm] -> [Perm]
-- | The set of minimal elements with respect to containment. FIX: Poor
-- implementation
minima :: [Pattern] -> [Pattern]
-- | The set of maximal elements with respect to containment. FIX: Poor
-- implementation
maxima :: [Pattern] -> [Pattern]
-- | coeff f v is the coefficient of v when expanding the
-- permutation statistic f as a sum of permutations/patterns.
-- See Petter Brändén and Anders Claesson: Mesh patterns and the
-- expansion of permutation statistics as sums of permutation patterns,
-- The Electronic Journal of Combinatorics 18(2) (2011),
-- http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i2p5.
coeff :: (Pattern -> Int) -> Pattern -> Int
-- | Data types for Semistandard Young Tableaux (SSYT) and functions for
-- converting between (generalized) permutataions and SSYT. In other
-- words, this module implements the Robinson-Schensted-Knuth (RSK)
-- correspondence.
module Sym.Perm.SSYT
-- | A Generalized Permutation is a lexicographically sorted list of
-- pairs of non-negative integers.
type GeneralizedPerm = [(Int, Int)]
-- | An entry is a non-negative integer
type Entry = Int
-- | A Semistandard Young Tableau (SSYT): the entries weakly
-- increase along each row and strictly increase down each column.
type SSYT = [[Entry]]
-- | A pair of Semistandard Young Tableaux.
data SSYTPair
SSYTPair :: SSYT -> SSYT -> SSYTPair
[insertionTableau] :: SSYTPair -> SSYT
[recordingTableau] :: SSYTPair -> SSYT
class Shape a
shape :: Shape a => a -> [Int]
-- | A pair of empty Young tableaux.
empty :: SSYTPair
-- | Check if a given pair of Young tableaux are empty.
null :: SSYTPair -> Bool
-- | Produce a string for pretty printing SSYT pairs.
display :: SSYTPair -> String
-- | The Robinson-Schensted algorithm.
fromPerm :: Perm -> SSYTPair
-- | The Robinson-Schensted-Knuth (RSK) algorithm.
fromGeneralizedPerm :: GeneralizedPerm -> SSYTPair
-- | The inverse of the Robinson-Schensted algorithm.
toPerm :: SSYTPair -> Perm
-- | The inverse of the Robinson-Schensted-Knuth algorithm.
toGeneralizedPerm :: SSYTPair -> GeneralizedPerm
instance GHC.Classes.Eq Sym.Perm.SSYT.SSYTPair
instance Sym.Perm.SSYT.Shape Sym.Perm.SSYT.SSYT
instance Sym.Perm.SSYT.Shape Sym.Perm.SSYT.SSYTPair
instance GHC.Show.Show Sym.Perm.SSYT.SSYTPair
-- | Common permutation statistics. Most of these are "set" versions of
-- those in Sym.Perm.Stat
module Sym.Perm.STAT
asc :: Perm -> [(Int, Int, Int)]
ascIx :: Perm -> [Int]
ascTops :: Perm -> [Int]
ascBots :: Perm -> [Int]
des :: Perm -> [(Int, Int, Int)]
desIx :: Perm -> [Int]
desTops :: Perm -> [Int]
desBots :: Perm -> [Int]
exc :: Perm -> [Int]
fp :: Perm -> [Int]
des0 :: Perm -> [(Int, Int, Int)]
des0Ix :: Perm -> [Int]
des0Tops :: Perm -> [Int]
des0Bots :: Perm -> [Int]
module Sym.Perm.Simple
-- | Is the permutation simple?
simple :: Perm -> Bool
module Sym.Perm.Sort
-- | One pass of stack-sort.
stackSort :: Perm -> Perm
-- | One pass of bubble-sort.
bubbleSort :: Perm -> Perm
-- | Common permutation statistics. To avoid name clashes this module is
-- best imported qualified; e.g.
--
--
-- import qualified Sym.Perm.Stat as S
--
module Sym.Perm.Stat
-- | The number of ascents. An ascent in w is an index
-- i such that w[i] < w[i+1].
asc :: Perm -> Int
-- | The number of descents. A descent in w is an index
-- i such that w[i] > w[i+1].
des :: Perm -> Int
-- | The number of excedances: positions i such that
-- w[i] > i.
exc :: Perm -> Int
-- | The number of fixed points: positions i such that
-- w[i] == i.
fp :: Perm -> Int
-- | The number of strong fixed points (also called splitters):
-- positions i such that w[j] < i for j <
-- i and w[j] > i for j > i.
sfp :: Perm -> Int
-- | The number of cycles: orbits of the permutation when viewed as
-- a function.
cyc :: Perm -> Int
-- | The number of inversions: pairs <math> such that
-- i < j and w[i] > w[j].
inv :: Perm -> Int
-- | The major index is the sum of descents.
maj :: Perm -> Int
-- | The co-major index is the sum of descents.
comaj :: Perm -> Int
-- | The number of peaks: positions i such that w[i-1]
-- < w[i] and w[i] > w[i+1].
peak :: Perm -> Int
-- | The number of valleys: positions i such that
-- w[i-1] > w[i] and w[i] < w[i+1].
vall :: Perm -> Int
-- | The number of double ascents: positions i such that
-- w[i-1] < w[i] < w[i+1].
dasc :: Perm -> Int
-- | The number of double descents: positions i such that
-- w[i-1] > w[i] > w[i+1].
ddes :: Perm -> Int
-- | The number of left-to-right minima: positions i such
-- that w[i] < w[j] for all j < i.
lmin :: Perm -> Int
-- | The number of left-to-right maxima: positions i such
-- that w[i] > w[j] for all j < i.
lmax :: Perm -> Int
-- | The number of right-to-left minima: positions i such
-- that w[i] < w[j] for all j > i.
rmin :: Perm -> Int
-- | The number of right-to-left maxima: positions i such
-- that w[i] > w[j] for all j > i.
rmax :: Perm -> Int
-- | The first (left-most) element in the standardization. E.g., head
-- "231" = head (fromList [1,2,0]) = 1.
head :: Perm -> Int
-- | The last (right-most) element in the standardization. E.g., last
-- "231" = last (fromList [1,2,0]) = 0.
last :: Perm -> Int
-- | Length of the left-most increasing run: largest i such that
-- w[0] < w[1] < ... < w[i-1].
lir :: Perm -> Int
-- | Length of the left-most decreasing run: largest i such that
-- w[0] > w[1] > ... > w[i-1].
ldr :: Perm -> Int
-- | Length of the right-most increasing run: largest i such that
-- w[n-i] < ... < w[n-2] < w[n-1].
rir :: Perm -> Int
-- | Length of the right-most decreasing run: largest i such that
-- w[n-i] > ... > w[n-2] > w[n-1].
rdr :: Perm -> Int
-- | The number of components. E.g., [2,0,3,1,4,6,7,5] has three
-- components: [2,0,3,1], [4] and [6,7,5].
comp :: Perm -> Int
-- | The number of skew components. E.g., [5,7,4,6,3,1,0,2] has
-- three skew components: [5,7,4,6], [3] and
-- [1,0,2].
scomp :: Perm -> Int
-- | The rank as defined by Elizalde and Pak [Bijections for refined
-- restricted permutations, J. Comb. Theory, Ser. A, 2004]:
--
--
-- maximum [ k | k <- [0..n-1], w[i] >= k for all i < k ]
--
ep :: Perm -> Int
-- | The dimension of a permutation is defined as the largest
-- non-fixed-point, or zero if all points are fixed.
dim :: Perm -> Int
-- | The number of small ascents. A small ascent in w is an
-- index i such that w[i] + 1 == w[i+1].
asc0 :: Perm -> Int
-- | The number of small descents. A small descent in w is
-- an index i such that w[i] == w[i+1] + 1.
des0 :: Perm -> Int
-- | The longest increasing subsequence.
lis :: Perm -> Int
-- | The longest decreasing subsequence.
lds :: Perm -> Int
-- | Permutation diagrams, or permutations as monads.
module Sym.Permgram
-- | The purpose of this data type is to assign labels to the indices of a
-- given permutation.
type Label a = Vector a
-- | A permgram consists of a permutation together with a label for each
-- index of the permutation.
data Permgram a
-- | The underlying permutation.
perm :: Permgram a -> Perm
-- | The assignment of labels to indices.
label :: Permgram a -> Label a
-- | The size of a permgram is the size of the underlying permutation.
size :: Permgram a -> Int
-- | Construct a permgram from an underlying permutation and a list of
-- labels.
permgram :: Perm -> [a] -> Permgram a
-- | The inverse permgram. It's obtained by mirroring the permgram in the
-- x=y diagonal.
inverse :: Permgram a -> Permgram a
instance GHC.Show.Show a => GHC.Show.Show (Sym.Permgram.Permgram a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Sym.Permgram.Permgram a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Sym.Permgram.Permgram a)
instance GHC.Base.Functor Sym.Permgram.Permgram
instance GHC.Base.Monad Sym.Permgram.Permgram
instance GHC.Base.Applicative Sym.Permgram.Permgram
-- | Sum, skew sum, etc
module Sym.Perm.Constructions
-- | The direct sum of two permutations.
(/+/) :: Perm -> Perm -> Perm
infixl 6 /+/
-- | The skew sum of two permutations.
(\-\) :: Perm -> Perm -> Perm
infixl 6 \-\
-- | The direct sum of a list of permutations.
directSum :: [Perm] -> Perm
-- | The skew sum of a list of permutations.
skewSum :: [Perm] -> Perm
-- | inflate w vs is the inflation of w by
-- vs. It is the permutation of length sum (map size
-- vs) obtained by replacing each entry w!i by an interval
-- that is order isomorphic to vs!i in such a way that the
-- intervals are order isomorphic to w. In particular,
--
--
-- u /+/ v == inflate (mkPerm "12") [u,v]
-- u \-\ v == inflate (mkPerm "21") [u,v]
--
inflate :: Perm -> [Perm] -> Perm
module Sym.Perm.Class
-- | The class of increasing permutations.
inc :: Int -> [Perm]
-- | The class of decreasing permutations.
dec :: Int -> [Perm]
-- | Av(1)
av1 :: Int -> [Perm]
-- | Av(12)
av12 :: Int -> [Perm]
-- | Av(21)
av21 :: Int -> [Perm]
-- | Av(123)
av123 :: Int -> [Perm]
-- | Av(132)
av132 :: Int -> [Perm]
-- | Av(213)
av213 :: Int -> [Perm]
-- | Av(231); also know as the stack sortable permutations.
av231 :: Int -> [Perm]
-- | Av(312)
av312 :: Int -> [Perm]
-- | Av(321)
av321 :: Int -> [Perm]
-- | Av(1243)
av1243 :: Int -> [Perm]
-- | Av(1324)
av1324 :: Int -> [Perm]
-- | Av(2134)
av2134 :: Int -> [Perm]
-- | Av(s) where s is a string of one or more patterns, using space as a
-- seperator.
av :: String -> Int -> [Perm]
-- | The V-class is Av(132, 231). It is so named because the diagram of a
-- typical permutation in this class is shaped like a V.
vee :: Int -> [Perm]
-- | The ∧-class is Av(213, 312). It is so named because the diagram of a
-- typical permutation in this class is shaped like a ∧.
caret :: Int -> [Perm]
-- | The >-class is Av(132, 312). It is so named because the diagram of
-- a typical permutation in this class is shaped like a >.
gt :: Int -> [Perm]
-- | The <-class is Av(213, 231). It is so named because the diagram of
-- a typical permutation in this class is shaped like a <.
lt :: Int -> [Perm]
-- | The union of vee, caret, gt and lt.
wedges :: Int -> [Perm]
-- | The class of separable permutations; it is identical to Av(2413,3142).
separables :: Int -> [Perm]
-- | The class of layered permutations with k layers.
kLayered :: Int -> Int -> [Perm]
-- | The class of layered permutations.
layered :: Int -> [Perm]
-- | The class of Fibonacci permutations with k layers. A
-- Fibonacci permutation is a layered permutation whose layers are
-- all of size 1 or 2.
kFibonacci :: Int -> Int -> [Perm]
-- | The class of Fibonacci permutations. A Fibonacci permutation is
-- a layered permutation whose layers are all of size 1 or 2.
fibonacci :: Int -> [Perm]
-- | A meta module collecting all Perm-modules, except those that are best
-- imported "qualified".
module Sym.Perm.Meta
module Sym
-- | 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.
class Permutation a where size = size . st inverse = unst . inverse . st ordiso u v = u == st v unst w = w `act` idperm (size w)
-- | 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
--
st :: Permutation a => a -> Perm
-- | 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.
act :: Permutation a => Perm -> a -> a
-- | 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.
size :: Permutation a => a -> Int
-- | The identity permutation of the given size.
idperm :: Permutation a => Int -> a
-- | The group theoretical inverse. It should hold that
--
--
-- inverse == unst . inverse . st
--
--
-- and this is the default implementation.
inverse :: Permutation a => a -> a
-- | 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)
--
ordiso :: Permutation a => Perm -> a -> Bool
-- | The inverse of st. It should hold that
--
--
-- unst w == w `act` idperm (P.size w)
--
--
-- and this is the default implementation.
unst :: Permutation a => Perm -> a
-- | The list of all permutations of the given size.
perms :: Permutation a => Int -> [a]
-- | Lifts a function on Perms to one on any permutations.
lift :: (Permutation a) => (Perm -> Perm) -> a -> a
-- | Like lift but for functions of two variables.
lift2 :: (Permutation a) => (Perm -> Perm -> Perm) -> a -> a -> a
instance Sym.Permutation Sym.Perm.Perm
instance Sym.Permutation GHC.Base.String
instance Sym.Permutation Sym.Perm.SSYT.SSYTPair