Safe Haskell | None |
---|---|

Language | Haskell2010 |

Compact representation of integer partitions.

Partitions are conceptually nonincreasing sequences of *positive* integers.

This implementation uses the `compact-word-vectors`

library internally to provide
a much more memory-efficient Partition type that the naive lists of integer.
This is very helpful when building large tables indexed by partitions, for example;
and hopefully quite a bit faster, too.

Note: This is an internal module, you are not supposed to import it directly. It is also not fully ready to be used yet...

## Synopsis

- newtype Partition = Partition WordVec
- showsPrecPartition :: Int -> Partition -> ShowS
- pattern Nil :: Partition
- pattern Cons :: Int -> Partition -> Partition
- pattern Partition_ :: [Int] -> Partition
- pattern Head :: Int -> Partition
- pattern Tail :: Partition -> Partition
- pattern Length :: Int -> Partition
- cmpLexico :: Partition -> Partition -> Ordering
- empty :: Partition
- isEmpty :: Partition -> Bool
- singleton :: Int -> Partition
- uncons :: Partition -> Maybe (Int, Partition)
- partitionTail :: Partition -> Partition
- cons :: Int -> Partition -> Partition
- snoc :: Partition -> Int -> Partition
- toExponentialForm :: Partition -> [(Int, Int)]
- fromExponentialForm :: [(Int, Int)] -> Partition
- width :: Partition -> Int
- height :: Partition -> Int
- widthHeight :: Partition -> (Int, Int)
- diffSequence :: Partition -> [Int]
- reverseDiffSequence :: Partition -> [Int]
- dualPartition :: Partition -> Partition
- toList :: Partition -> [Int]
- toDescList :: Partition -> [Int]
- toAscList :: Partition -> [Int]
- fromDescList :: [Int] -> Partition
- fromDescList' :: Int -> [Int] -> Partition
- isSubPartitionOf :: Partition -> Partition -> Bool
- dominates :: Partition -> Partition -> Bool
- pieriRule :: Partition -> Int -> [Partition]
- i2w :: Int -> Word
- w2i :: Word -> Int
- sum' :: [Word] -> Word
- safeTail :: [Int] -> [Int]
- descendToZero :: Int -> [Int]
- descendToOne :: Int -> [Int]

# The compact partition data type

# Pattern synonyms

pattern Nil :: Partition Source #

Pattern sysnonyms allows us to use existing code with minimal modifications

pattern Partition_ :: [Int] -> Partition Source #

Simulated newtype constructor

# Lexicographic comparison

# Basic (de)constructrion

partitionTail :: Partition -> Partition Source #

partitionTail p == snd (uncons p)

snoc :: Partition -> Int -> Partition Source #

We assume that the element is not bigger than the last element!

# exponential form

# Width and height of the bounding rectangle

# Differential sequence

diffSequence :: Partition -> [Int] Source #

From a non-increasing sequence `[a1,a2,..,an]`

this computes the sequence of differences
`[a1-a2,a2-a3,...,an-0]`

reverseDiffSequence :: Partition -> [Int] Source #

From a non-increasing sequence `[a1,a2,..,an]`

this computes the reversed sequence of differences
`[ a[n]-0 , a[n-1]-a[n] , ... , a[2]-a[3] , a[1]-a[2] ] `

# Dual partition

dualPartition :: Partition -> Partition Source #

# Conversion to list

toDescList :: Partition -> [Int] Source #

returns a descending (non-increasing) list

# Conversion from list

fromDescList :: [Int] -> Partition Source #

We assume that the input is a non-increasing list of *positive* integers!

# Partial orderings

# Pieri rule

pieriRule :: Partition -> Int -> [Partition] Source #

Expands to product `s[lambda]*h[k]`

as a sum of `s[mu]`

-s. See https://en.wikipedia.org/wiki/Pieri's_formula

# local (internally used) utility functions

descendToZero :: Int -> [Int] Source #

descendToOne :: Int -> [Int] Source #