-- | Gelfand-Tsetlin patterns and Kostka numbers.
--
-- Gelfand-Tsetlin patterns (or tableaux) are triangular arrays like
--
-- > [ 3 ]
-- > [ 3 , 2 ]
-- > [ 3 , 1 , 0 ]
-- > [ 2 , 0 , 0 , 0 ]
--
-- with both rows and columns non-increasing non-negative integers.
-- Note: these are in bijection with the semi-standard Young tableaux.
--
-- If we add the further restriction that
-- the top diagonal reads @lambda@, 
-- and the diagonal sums are partial sums of @mu@, where @lambda@ and @mu@ are two
-- partitions (in this case @lambda=[3,2]@ and @mu=[2,1,1,1]@), 
-- then the number of the resulting patterns 
-- or tableaux is the Kostka number @K(lambda,mu)@.
-- Actually @mu@ doesn't even need to the be non-increasing.
--

{-# LANGUAGE BangPatterns, ScopedTypeVariables #-}
module Math.Combinat.Tableaux.GelfandTsetlin where

--------------------------------------------------------------------------------

import Data.List
import Data.Maybe
import Data.Monoid
import Data.Ord

import Control.Monad
import Control.Monad.Trans.State

import Data.Map (Map)
import qualified Data.Map as Map

import Math.Combinat.Partitions.Integer
import Math.Combinat.Tableaux
import Math.Combinat.Helper
import Math.Combinat.ASCII

--------------------------------------------------------------------------------
-- * Kostka numbers

-- | Kostka numbers (via counting Gelfand-Tsetlin patterns). See for example <http://en.wikipedia.org/wiki/Kostka_number>
--
-- @K(lambda,mu)==0@ unless @lambda@ dominates @mu@:
--
-- > [ mu | mu <- partitions (weight lam) , kostkaNumber lam mu > 0 ] == dominatedPartitions lam
--
kostkaNumber :: Partition -> Partition -> Int
kostkaNumber :: Partition -> Partition -> Int
kostkaNumber = Partition -> Partition -> Int
countKostkaGelfandTsetlinPatterns

-- | Very naive (and slow) implementation of Kostka numbers, for reference.
kostkaNumberReferenceNaive :: Partition -> Partition -> Int
kostkaNumberReferenceNaive :: Partition -> Partition -> Int
kostkaNumberReferenceNaive Partition
plambda pmu :: Partition
pmu@(Partition [Int]
mu) = forall (t :: * -> *) a. Foldable t => t a -> Int
length [Int]
stuff where
  stuff :: [Int]
stuff  = [ (Int
1::Int) | Tableau Int
t <- Int -> Partition -> [Tableau Int]
semiStandardYoungTableaux Int
k Partition
plambda , forall {a} {t :: * -> *}.
(Ord a, Foldable t, Num a, Enum a) =>
t [a] -> Bool
cond Tableau Int
t ]
  k :: Int
k      = forall (t :: * -> *) a. Foldable t => t a -> Int
length [Int]
mu
  cond :: t [a] -> Bool
cond t [a]
t = [ (forall a. [a] -> a
head [a]
xs, forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
xs) | [a]
xs <- forall a. Eq a => [a] -> [[a]]
group (forall a. Ord a => [a] -> [a]
sort forall a b. (a -> b) -> a -> b
$ forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat t [a]
t) ] forall a. Eq a => a -> a -> Bool
== forall a b. [a] -> [b] -> [(a, b)]
zip [a
1..] [Int]
mu 

--------------------------------------------------------------------------------

-- | Lists all (positive) Kostka numbers @K(lambda,mu)@ with the given @lambda@:
--
-- > kostkaNumbersWithGivenLambda lambda == Map.fromList [ (mu , kostkaNumber lambda mu) | mu <- dominatedPartitions lambda ]
--
-- It's much faster than computing the individual Kostka numbers, but not as fast
-- as it could be.
--
{-# SPECIALIZE kostkaNumbersWithGivenLambda :: Partition -> Map Partition Int     #-}
{-# SPECIALIZE kostkaNumbersWithGivenLambda :: Partition -> Map Partition Integer #-}
kostkaNumbersWithGivenLambda :: forall coeff. Num coeff => Partition -> Map Partition coeff
kostkaNumbersWithGivenLambda :: forall coeff. Num coeff => Partition -> Map Partition coeff
kostkaNumbersWithGivenLambda plambda :: Partition
plambda@(Partition [Int]
lam) = forall s a. State s a -> s -> a
evalState ([Int]
-> State
     (Map Partition (Map Partition coeff)) (Map Partition coeff)
worker [Int]
lam) forall k a. Map k a
Map.empty where

  worker :: [Int] -> State (Map Partition (Map Partition coeff)) (Map Partition coeff)
  worker :: [Int]
-> State
     (Map Partition (Map Partition coeff)) (Map Partition coeff)
worker [Int]
unlam = case [Int]
unlam of
    [] -> forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$ forall k a. k -> a -> Map k a
Map.singleton ([Int] -> Partition
Partition []) coeff
1
    [Int]
_  -> do
      Map Partition (Map Partition coeff)
cache <- forall (m :: * -> *) s. Monad m => StateT s m s
get
      case forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup ([Int] -> Partition
Partition [Int]
unlam) Map Partition (Map Partition coeff)
cache of
        Just Map Partition coeff
sol -> forall (m :: * -> *) a. Monad m => a -> m a
return Map Partition coeff
sol
        Maybe (Map Partition coeff)
Nothing  -> do
          let s :: Int
s = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' forall a. Num a => a -> a -> a
(+) Int
0 [Int]
unlam
          [Map Partition coeff]
subsols <- forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
t a -> (a -> m b) -> m (t b)
forM ([Int] -> Tableau Int
prevLambdas0 [Int]
unlam) forall a b. (a -> b) -> a -> b
$ \[Int]
p -> do
            Map Partition coeff
sub <- [Int]
-> State
     (Map Partition (Map Partition coeff)) (Map Partition coeff)
worker [Int]
p 
            let t :: Int
t = Int
s forall a. Num a => a -> a -> a
- forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' forall a. Num a => a -> a -> a
(+) Int
0 [Int]
p              
                f :: (Partition, b) -> Maybe (Partition, b)
f (Partition [Int]
xs , b
c) = case [Int]
xs of
                  (Int
y:[Int]
_) -> if Int
t forall a. Ord a => a -> a -> Bool
>= Int
y then forall a. a -> Maybe a
Just ([Int] -> Partition
Partition (Int
tforall a. a -> [a] -> [a]
:[Int]
xs) , b
c) else forall a. Maybe a
Nothing
                  []    -> if Int
t forall a. Ord a => a -> a -> Bool
>  Int
0 then forall a. a -> Maybe a
Just ([Int] -> Partition
Partition [Int
t]    , b
c) else forall a. Maybe a
Nothing
            if Int
t forall a. Ord a => a -> a -> Bool
> Int
0
              then forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$ forall k a. Ord k => [(k, a)] -> Map k a
Map.fromList forall a b. (a -> b) -> a -> b
$ forall a b. (a -> Maybe b) -> [a] -> [b]
mapMaybe forall {b}. (Partition, b) -> Maybe (Partition, b)
f forall a b. (a -> b) -> a -> b
$ forall k a. Map k a -> [(k, a)]
Map.toList Map Partition coeff
sub
              else forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$ forall k a. Map k a
Map.empty

          let sol :: Map Partition coeff
sol = forall (f :: * -> *) k a.
(Foldable f, Ord k) =>
(a -> a -> a) -> f (Map k a) -> Map k a
Map.unionsWith forall a. Num a => a -> a -> a
(+) [Map Partition coeff]
subsols
          forall (m :: * -> *) s. Monad m => s -> StateT s m ()
put forall a b. (a -> b) -> a -> b
$! (forall k a. Ord k => k -> a -> Map k a -> Map k a
Map.insert ([Int] -> Partition
Partition [Int]
unlam) Map Partition coeff
sol Map Partition (Map Partition coeff)
cache)
          forall (m :: * -> *) a. Monad m => a -> m a
return Map Partition coeff
sol

  -- needs decreasing sequence
  prevLambdas0 :: [Int] -> [[Int]]
  prevLambdas0 :: [Int] -> Tableau Int
prevLambdas0 (Int
l:[Int]
ls) = forall {t}. (Enum t, Num t) => t -> [t] -> [[t]]
go Int
l [Int]
ls where
    go :: t -> [t] -> [[t]]
go t
b [t
a]    = [ [t
x]   | t
x <- [t
a..t
b] ] forall a. [a] -> [a] -> [a]
++ [ [t
x,t
y] | t
x <- [t
a..t
b] , t
y<-[t
1..t
a] ]
    go t
b (t
a:[t]
as) = [ t
xforall a. a -> [a] -> [a]
:[t]
xs  | t
x <- [t
a..t
b] , [t]
xs <- t -> [t] -> [[t]]
go t
a [t]
as ]
    go t
b []     = [] forall a. a -> [a] -> [a]
: [ [t
j] | t
j <- [t
1..t
b] ]
  prevLambdas0 []  = []

-- | Lists all (positive) Kostka numbers @K(lambda,mu)@ with the given @mu@:
--
-- > kostkaNumbersWithGivenMu mu == Map.fromList [ (lambda , kostkaNumber lambda mu) | lambda <- dominatingPartitions mu ]
--
-- This function uses the iterated Pieri rule, and is relatively fast.
--
kostkaNumbersWithGivenMu :: Partition -> Map Partition Int
kostkaNumbersWithGivenMu :: Partition -> Map Partition Int
kostkaNumbersWithGivenMu (Partition [Int]
mu) = forall coeff. Num coeff => [Int] -> Map Partition coeff
iteratedPieriRule (forall a. [a] -> [a]
reverse [Int]
mu)

--------------------------------------------------------------------------------
-- * Gelfand-Tsetlin patterns

-- | A Gelfand-Tstetlin tableau
type GT = [[Int]]

asciiGT :: GT -> ASCII
asciiGT :: Tableau Int -> ASCII
asciiGT Tableau Int
gt = (HAlign, VAlign) -> (HSep, VSep) -> [[ASCII]] -> ASCII
tabulate (HAlign
HRight,VAlign
VTop) (Int -> HSep
HSepSpaces Int
1, VSep
VSepEmpty) 
           forall a b. (a -> b) -> a -> b
$ (forall a b. (a -> b) -> [a] -> [b]
map forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a -> b) -> [a] -> [b]
map) forall a. Show a => a -> ASCII
asciiShow
           forall a b. (a -> b) -> a -> b
$ Tableau Int
gt

kostkaGelfandTsetlinPatterns :: Partition -> Partition -> [GT]
kostkaGelfandTsetlinPatterns :: Partition -> Partition -> [Tableau Int]
kostkaGelfandTsetlinPatterns Partition
lambda (Partition [Int]
mu) = Partition -> [Int] -> [Tableau Int]
kostkaGelfandTsetlinPatterns' Partition
lambda [Int]
mu

-- | Generates all Kostka-Gelfand-Tsetlin tableau, that is, triangular arrays like
--
-- > [ 3 ]
-- > [ 3 , 2 ]
-- > [ 3 , 1 , 0 ]
-- > [ 2 , 0 , 0 , 0 ]
--
-- with both rows and column non-increasing such that
-- the top diagonal read lambda (in this case @lambda=[3,2]@) and the diagonal sums
-- are partial sums of mu (in this case @mu=[2,1,1,1]@)
--
-- The number of such GT tableaux is the Kostka
-- number K(lambda,mu).
--
kostkaGelfandTsetlinPatterns' :: Partition -> [Int] -> [GT]
kostkaGelfandTsetlinPatterns' :: Partition -> [Int] -> [Tableau Int]
kostkaGelfandTsetlinPatterns' plam :: Partition
plam@(Partition [Int]
lambda0) [Int]
mu0
  | forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
minimum [Int]
mu0 forall a. Ord a => a -> a -> Bool
< Int
0                       = []
  | Int
wlam forall a. Eq a => a -> a -> Bool
== Int
0                             = if Int
wmu forall a. Eq a => a -> a -> Bool
== Int
0 then [ [] ] else []
  | Int
wmu  forall a. Eq a => a -> a -> Bool
== Int
wlam Bool -> Bool -> Bool
&& Partition
plam Partition -> Partition -> Bool
`dominates` Partition
pmu  = [Tableau Int]
list
  | Bool
otherwise                             = []
  where

    pmu :: Partition
pmu = [Int] -> Partition
mkPartition [Int]
mu0

    nlam :: Int
nlam = forall (t :: * -> *) a. Foldable t => t a -> Int
length [Int]
lambda0
    nmu :: Int
nmu  = forall (t :: * -> *) a. Foldable t => t a -> Int
length [Int]
mu0

    n :: Int
n = forall a. Ord a => a -> a -> a
max Int
nlam Int
nmu

    lambda :: [Int]
lambda = [Int]
lambda0 forall a. [a] -> [a] -> [a]
++ forall a. Int -> a -> [a]
replicate (Int
n forall a. Num a => a -> a -> a
- Int
nlam) Int
0
    mu :: [Int]
mu     = [Int]
mu0     forall a. [a] -> [a] -> [a]
++ forall a. Int -> a -> [a]
replicate (Int
n forall a. Num a => a -> a -> a
- Int
nmu ) Int
0

    revlam :: [Int]
revlam = forall a. [a] -> [a]
reverse [Int]
lambda

    wmu :: Int
wmu  = forall a. Num a => [a] -> a
sum' [Int]
mu
    wlam :: Int
wlam = forall a. Num a => [a] -> a
sum' [Int]
lambda

    list :: [Tableau Int]
list = [Int] -> [Int] -> [Int] -> [Int] -> Tableau Int -> [Tableau Int]
worker 
             [Int]
revlam 
             (forall a. (a -> a -> a) -> [a] -> [a]
scanl1 forall a. Num a => a -> a -> a
(+) [Int]
mu) 
             (forall a. Int -> a -> [a]
replicate (Int
nforall a. Num a => a -> a -> a
-Int
1) Int
0) 
             (forall a. Int -> a -> [a]
replicate (Int
n  ) Int
0) 
             []

    worker
      :: [Int]       -- lambda_i in reverse order
      -> [Int]       -- partial sums of mu
      -> [Int]       -- sums of the tails of previous rows
      -> [Int]       -- last row
      -> [[Int]]     -- the lower part of GT tableau we accumulated so far (this is not needed if we only want to count)
      -> [GT]   

    worker :: [Int] -> [Int] -> [Int] -> [Int] -> Tableau Int -> [Tableau Int]
worker (Int
rl:[Int]
rls) (Int
smu:[Int]
smus) (Int
a:[Int]
acc) (Int
lastx0:[Int]
lastrowt) Tableau Int
table = [Tableau Int]
stuff 
      where
        x0 :: Int
x0 = Int
smu forall a. Num a => a -> a -> a
- Int
a
        stuff :: [Tableau Int]
stuff = forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat 
          [ [Int] -> [Int] -> [Int] -> [Int] -> Tableau Int -> [Tableau Int]
worker [Int]
rls [Int]
smus (forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith forall a. Num a => a -> a -> a
(+) [Int]
acc (forall a. [a] -> [a]
tail [Int]
row)) (forall a. [a] -> [a]
init [Int]
row) ([Int]
rowforall a. a -> [a] -> [a]
:Tableau Int
table)
          | [Int]
row <- Int -> [Int] -> [Int] -> Tableau Int
boundedNonIncrSeqs' Int
x0 (forall a b. (a -> b) -> [a] -> [b]
map (forall a. Ord a => a -> a -> a
max Int
rl) (forall a. Ord a => a -> a -> a
max Int
lastx0 Int
x0 forall a. a -> [a] -> [a]
: [Int]
lastrowt)) [Int]
lambda
          ]
    worker [Int
rl] [Int]
_ [Int]
_ [Int]
_ Tableau Int
table = [ [Int
rl]forall a. a -> [a] -> [a]
:Tableau Int
table ] 
    worker []   [Int]
_ [Int]
_ [Int]
_ Tableau Int
_     = [ []         ]

    boundedNonIncrSeqs' :: Int -> [Int] -> [Int] -> [[Int]]
    boundedNonIncrSeqs' :: Int -> [Int] -> [Int] -> Tableau Int
boundedNonIncrSeqs' = forall {a}. (Ord a, Num a, Enum a) => a -> [a] -> [a] -> [[a]]
go where
      go :: a -> [a] -> [a] -> [[a]]
go a
h0 (a
a:[a]
as) (a
b:[a]
bs) = [ a
hforall a. a -> [a] -> [a]
:[a]
hs | a
h <- [(forall a. Ord a => a -> a -> a
max a
0 a
a)..(forall a. Ord a => a -> a -> a
min a
h0 a
b)] , [a]
hs <- a -> [a] -> [a] -> [[a]]
go a
h [a]
as [a]
bs ]
      go a
_  []     [a]
_      = [[]]
      go a
_  [a]
_      []     = [[]]

--------------------------------------------------------------------------------

-- | This returns the corresponding Kostka number:
--
-- > countKostkaGelfandTsetlinPatterns lambda mu == length (kostkaGelfandTsetlinPatterns lambda mu)
-- 
countKostkaGelfandTsetlinPatterns :: Partition -> Partition -> Int
countKostkaGelfandTsetlinPatterns :: Partition -> Partition -> Int
countKostkaGelfandTsetlinPatterns plam :: Partition
plam@(Partition [Int]
lambda0) pmu :: Partition
pmu@(Partition [Int]
mu0) 
  | Int
wlam forall a. Eq a => a -> a -> Bool
== Int
0                             = if Int
wmu forall a. Eq a => a -> a -> Bool
== Int
0 then Int
1 else Int
0
  | Int
wmu  forall a. Eq a => a -> a -> Bool
== Int
wlam Bool -> Bool -> Bool
&& Partition
plam Partition -> Partition -> Bool
`dominates` Partition
pmu  = Int
cnt
  | Bool
otherwise                             = Int
0
  where

    nlam :: Int
nlam = forall (t :: * -> *) a. Foldable t => t a -> Int
length [Int]
lambda0
    nmu :: Int
nmu  = forall (t :: * -> *) a. Foldable t => t a -> Int
length [Int]
mu0

    n :: Int
n = forall a. Ord a => a -> a -> a
max Int
nlam Int
nmu

    lambda :: [Int]
lambda = [Int]
lambda0 forall a. [a] -> [a] -> [a]
++ forall a. Int -> a -> [a]
replicate (Int
n forall a. Num a => a -> a -> a
- Int
nlam) Int
0
    mu :: [Int]
mu     = [Int]
mu0     forall a. [a] -> [a] -> [a]
++ forall a. Int -> a -> [a]
replicate (Int
n forall a. Num a => a -> a -> a
- Int
nmu ) Int
0

    revlam :: [Int]
revlam = forall a. [a] -> [a]
reverse [Int]
lambda

    wmu :: Int
wmu  = forall a. Num a => [a] -> a
sum' [Int]
mu
    wlam :: Int
wlam = forall a. Num a => [a] -> a
sum' [Int]
lambda

    cnt :: Int
cnt = [Int] -> [Int] -> [Int] -> [Int] -> Int
worker 
            [Int]
revlam 
            (forall a. (a -> a -> a) -> [a] -> [a]
scanl1 forall a. Num a => a -> a -> a
(+) [Int]
mu) 
            (forall a. Int -> a -> [a]
replicate (Int
nforall a. Num a => a -> a -> a
-Int
1) Int
0) 
            (forall a. Int -> a -> [a]
replicate (Int
n  ) Int
0) 

    worker
      :: [Int]       -- lambda_i in reverse order
      -> [Int]       -- partial sums of mu
      -> [Int]       -- sums of the tails of previous rows
      -> [Int]       -- last row
      -> Int

    worker :: [Int] -> [Int] -> [Int] -> [Int] -> Int
worker (Int
rl:[Int]
rls) (Int
smu:[Int]
smus) (Int
a:[Int]
acc) (Int
lastx0:[Int]
lastrowt) = Int
stuff 
      where
        x0 :: Int
x0 = Int
smu forall a. Num a => a -> a -> a
- Int
a
        stuff :: Int
stuff = forall a. Num a => [a] -> a
sum'
          [ [Int] -> [Int] -> [Int] -> [Int] -> Int
worker [Int]
rls [Int]
smus (forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith forall a. Num a => a -> a -> a
(+) [Int]
acc (forall a. [a] -> [a]
tail [Int]
row)) (forall a. [a] -> [a]
init [Int]
row) 
          | [Int]
row <- Int -> [Int] -> [Int] -> Tableau Int
boundedNonIncrSeqs' Int
x0 (forall a b. (a -> b) -> [a] -> [b]
map (forall a. Ord a => a -> a -> a
max Int
rl) (forall a. Ord a => a -> a -> a
max Int
lastx0 Int
x0 forall a. a -> [a] -> [a]
: [Int]
lastrowt)) [Int]
lambda
          ]
    worker [Int
rl] [Int]
_ [Int]
_ [Int]
_ = Int
1 
    worker []   [Int]
_ [Int]
_ [Int]
_ = Int
1

    boundedNonIncrSeqs' :: Int -> [Int] -> [Int] -> [[Int]]
    boundedNonIncrSeqs' :: Int -> [Int] -> [Int] -> Tableau Int
boundedNonIncrSeqs' = forall {a}. (Ord a, Num a, Enum a) => a -> [a] -> [a] -> [[a]]
go where
      go :: a -> [a] -> [a] -> [[a]]
go a
h0 (a
a:[a]
as) (a
b:[a]
bs) = [ a
hforall a. a -> [a] -> [a]
:[a]
hs | a
h <- [(forall a. Ord a => a -> a -> a
max a
0 a
a)..(forall a. Ord a => a -> a -> a
min a
h0 a
b)] , [a]
hs <- a -> [a] -> [a] -> [[a]]
go a
h [a]
as [a]
bs ]
      go a
_  []     [a]
_      = [[]]
      go a
_  [a]
_      []     = [[]]

--------------------------------------------------------------------------------

{-

-- | All non-increasing sentences between a lower and an upper bound
boundedNonIncrSeqs :: [Int] -> [Int] -> [[Int]]
boundedNonIncrSeqs as bs = case bs of  
  (h0:_) -> boundedNonIncrSeqs' h0 as bs
  []     -> [[]]

-- | All non-increasing sentences between a lower and an upper bound, and also less-or-equal than the given number
boundedNonIncrSeqs' :: Int -> [Int] -> [Int] -> [[Int]]
boundedNonIncrSeqs' = go where
  go h0 (a:as) (b:bs) = [ h:hs | h <- [(max 0 a)..(min h0 b)] , hs <- go h as bs ]
  go _  []     _      = [[]]
  go _  _      []     = [[]]

-- | All non-decreasing sentences between a lower and an upper bound
boundedNonDecrSeqs :: [Int] -> [Int] -> [[Int]]
boundedNonDecrSeqs = boundedNonDecrSeqs' 0

-- | All non-decreasing sentences between a lower and an upper bound, and also greator-or-equal then the given number
boundedNonDecrSeqs' :: Int -> [Int] -> [Int] -> [[Int]]
boundedNonDecrSeqs' h0 = go (max 0 h0) where
  go h0 (a:as) (b:bs) = [ h:hs | h <- [(max h0 a)..b] , hs <- go h as bs ]
  go _  []     _      = [[]]
  go _  _      []     = [[]]

-}

--------------------------------------------------------------------------------
-- * The iterated Pieri rule 

-- | Computes the Schur expansion of @h[n1]*h[n2]*h[n3]*...*h[nk]@ via iterating the Pieri rule.
-- Note: the coefficients are actually the Kostka numbers; the following is true:
--
-- > Map.toList (iteratedPieriRule (fromPartition mu))  ==  [ (lam, kostkaNumber lam mu) | lam <- dominatingPartitions mu ]
-- 
-- This should be faster than individually computing all these Kostka numbers.
--
iteratedPieriRule :: Num coeff => [Int] -> Map Partition coeff
iteratedPieriRule :: forall coeff. Num coeff => [Int] -> Map Partition coeff
iteratedPieriRule = forall coeff.
Num coeff =>
Partition -> [Int] -> Map Partition coeff
iteratedPieriRule' ([Int] -> Partition
Partition [])

-- | Iterating the Pieri rule, we can compute the Schur expansion of
-- @h[lambda]*h[n1]*h[n2]*h[n3]*...*h[nk]@
iteratedPieriRule' :: Num coeff => Partition -> [Int] -> Map Partition coeff
iteratedPieriRule' :: forall coeff.
Num coeff =>
Partition -> [Int] -> Map Partition coeff
iteratedPieriRule' Partition
plambda [Int]
ns = forall coeff.
Num coeff =>
(Partition, coeff) -> [Int] -> Map Partition coeff
iteratedPieriRule'' (Partition
plambda,coeff
1) [Int]
ns

{-# SPECIALIZE iteratedPieriRule'' :: (Partition,Int    ) -> [Int] -> Map Partition Int     #-}
{-# SPECIALIZE iteratedPieriRule'' :: (Partition,Integer) -> [Int] -> Map Partition Integer #-}
iteratedPieriRule'' :: Num coeff => (Partition,coeff) -> [Int] -> Map Partition coeff
iteratedPieriRule'' :: forall coeff.
Num coeff =>
(Partition, coeff) -> [Int] -> Map Partition coeff
iteratedPieriRule'' (Partition
plambda,coeff
coeff0) [Int]
ns = forall {a}. Num a => Map Partition a -> [Int] -> Map Partition a
worker (forall k a. k -> a -> Map k a
Map.singleton Partition
plambda coeff
coeff0) [Int]
ns where
  worker :: Map Partition a -> [Int] -> Map Partition a
worker Map Partition a
old []     = Map Partition a
old
  worker Map Partition a
old (Int
n:[Int]
ns) = Map Partition a -> [Int] -> Map Partition a
worker Map Partition a
new [Int]
ns where
    stuff :: [(a, [Partition])]
stuff = [ (a
coeff, Partition -> Int -> [Partition]
pieriRule Partition
lam Int
n) | (Partition
lam,a
coeff) <- forall k a. Map k a -> [(k, a)]
Map.toList Map Partition a
old ] 
    new :: Map Partition a
new   = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' forall {t :: * -> *} {k} {a}.
(Foldable t, Ord k, Num a) =>
Map k a -> (a, t k) -> Map k a
f forall k a. Map k a
Map.empty [(a, [Partition])]
stuff 
    f :: Map k a -> (a, t k) -> Map k a
f Map k a
t0 (a
c,t k
ps) = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\Map k a
t k
p -> forall k a. Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
Map.insertWith forall a. Num a => a -> a -> a
(+) k
p a
c Map k a
t) Map k a
t0 t k
ps  

--------------------------------------------------------------------------------

-- | Computes the Schur expansion of @e[n1]*e[n2]*e[n3]*...*e[nk]@ via iterating the Pieri rule.
-- Note: the coefficients are actually the Kostka numbers; the following is true:
--
-- > Map.toList (iteratedDualPieriRule (fromPartition mu))  ==  
-- >   [ (dualPartition lam, kostkaNumber lam mu) | lam <- dominatingPartitions mu ]
-- 
-- This should be faster than individually computing all these Kostka numbers.
-- It is a tiny bit slower than 'iteratedPieriRule'.
--
iteratedDualPieriRule :: Num coeff => [Int] -> Map Partition coeff
iteratedDualPieriRule :: forall coeff. Num coeff => [Int] -> Map Partition coeff
iteratedDualPieriRule = forall coeff.
Num coeff =>
Partition -> [Int] -> Map Partition coeff
iteratedDualPieriRule' ([Int] -> Partition
Partition [])

-- | Iterating the Pieri rule, we can compute the Schur expansion of
-- @e[lambda]*e[n1]*e[n2]*e[n3]*...*e[nk]@
iteratedDualPieriRule' :: Num coeff => Partition -> [Int] -> Map Partition coeff
iteratedDualPieriRule' :: forall coeff.
Num coeff =>
Partition -> [Int] -> Map Partition coeff
iteratedDualPieriRule' Partition
plambda [Int]
ns = forall coeff.
Num coeff =>
(Partition, coeff) -> [Int] -> Map Partition coeff
iteratedDualPieriRule'' (Partition
plambda,coeff
1) [Int]
ns

{-# SPECIALIZE iteratedDualPieriRule'' :: (Partition,Int    ) -> [Int] -> Map Partition Int     #-}
{-# SPECIALIZE iteratedDualPieriRule'' :: (Partition,Integer) -> [Int] -> Map Partition Integer #-}
iteratedDualPieriRule'' :: Num coeff => (Partition,coeff) -> [Int] -> Map Partition coeff
iteratedDualPieriRule'' :: forall coeff.
Num coeff =>
(Partition, coeff) -> [Int] -> Map Partition coeff
iteratedDualPieriRule'' (Partition
plambda,coeff
coeff0) [Int]
ns = forall {a}. Num a => Map Partition a -> [Int] -> Map Partition a
worker (forall k a. k -> a -> Map k a
Map.singleton Partition
plambda coeff
coeff0) [Int]
ns where
  worker :: Map Partition a -> [Int] -> Map Partition a
worker Map Partition a
old []     = Map Partition a
old
  worker Map Partition a
old (Int
n:[Int]
ns) = Map Partition a -> [Int] -> Map Partition a
worker Map Partition a
new [Int]
ns where
    stuff :: [(a, [Partition])]
stuff = [ (a
coeff, Partition -> Int -> [Partition]
dualPieriRule Partition
lam Int
n) | (Partition
lam,a
coeff) <- forall k a. Map k a -> [(k, a)]
Map.toList Map Partition a
old ] 
    new :: Map Partition a
new   = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' forall {t :: * -> *} {k} {a}.
(Foldable t, Ord k, Num a) =>
Map k a -> (a, t k) -> Map k a
f forall k a. Map k a
Map.empty [(a, [Partition])]
stuff 
    f :: Map k a -> (a, t k) -> Map k a
f Map k a
t0 (a
c,t k
ps) = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\Map k a
t k
p -> forall k a. Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
Map.insertWith forall a. Num a => a -> a -> a
(+) k
p a
c Map k a
t) Map k a
t0 t k
ps  

--------------------------------------------------------------------------------