-- | Symmetric polynomials in two variables @alpha@ and @beta@.
--
-- We provide three representation:
--
-- * symmetric polynomials in @alpha@ and @beta@ (Chern roots)
--
-- * polynomials in the elementary symmetric polynomials @c1=alpha+beta@ and @c2=alpha*beta@ (Chern classes)
--
-- * Schur polynomials @s[i,j]@
--
-- The monomials of the first two of these form monoids (the product of 
-- monomials is again a monomial), and can be used uniformly with the
-- help of some type-level hackery.
--
-- How to use the unified interface?
-- Suppose you have a function like this:
--
-- > tau :: ChernBase base => Int -> ZMod base
--
-- When calling it, you want to specify the output type (either @ZMod AB@ or @ZMod Chern@).
-- You can do that three ways:
--
-- > x = tau @AB 10                  -- this needs -XTypeApplications
-- > x = (tau 10 :: ZMod AB)
-- > x = spec1' ChernRoot $ tau 10
--
-- The first one is the most convenient, but it only works with GHC 8 and later.
-- The other two work with older GHC versions, too.
--


{-# LANGUAGE BangPatterns, DataKinds, TypeFamilies, Rank2Types, GADTs, StandaloneDeriving #-}
module Math.RootLoci.Algebra.SymmPoly where

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

import Control.Monad
import Data.List

-- Semigroup became a superclass of Monoid
#if MIN_VERSION_base(4,11,0)     
import Data.Foldable
import Data.Semigroup
#endif

import System.Random       -- testing only

import Math.Combinat.Sign
import Math.Combinat.Numbers
import Math.Combinat.Sets ( choose ) 

import qualified Data.Map.Strict as Map

import Data.Array ( Array )
import Data.Array.IArray

import Math.Algebra.Polynomial.FreeModule (ZMod)
import qualified Math.Algebra.Polynomial.FreeModule as ZMod

import Math.RootLoci.Misc.Common
import Math.Algebra.Polynomial.Pretty

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

-- | An elementary symmetric polynomial of some generators
symPoly :: (Ord a, Monoid a) => Int -> [a] -> ZMod a
symPoly :: Int -> [a] -> ZMod a
symPoly Int
k [a]
xs = [(a, Integer)] -> ZMod a
forall c b. (Eq c, Num c, Ord b) => [(b, c)] -> FreeMod c b
ZMod.fromList ([(a, Integer)] -> ZMod a) -> [(a, Integer)] -> ZMod a
forall a b. (a -> b) -> a -> b
$ (a -> (a, Integer)) -> [a] -> [(a, Integer)]
forall a b. (a -> b) -> [a] -> [b]
map (\a
x -> (a
x,Integer
1)) ([a] -> [(a, Integer)]) -> [a] -> [(a, Integer)]
forall a b. (a -> b) -> a -> b
$ (([a] -> a) -> [[a]] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map [a] -> a
forall a. Monoid a => [a] -> a
mconcat ([[a]] -> [a]) -> [[a]] -> [a]
forall a b. (a -> b) -> a -> b
$ Int -> [a] -> [[a]]
forall a. Int -> [a] -> [[a]]
choose Int
k [a]
xs) 

--------------------------------------------------------------------------------
-- * Base monomials

-- | Chern roots: @alpha^i * beta^j@, monomial base of @Z[alpha,beta]@
data AB = AB !Int !Int deriving (AB -> AB -> Bool
(AB -> AB -> Bool) -> (AB -> AB -> Bool) -> Eq AB
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: AB -> AB -> Bool
$c/= :: AB -> AB -> Bool
== :: AB -> AB -> Bool
$c== :: AB -> AB -> Bool
Eq,Eq AB
Eq AB
-> (AB -> AB -> Ordering)
-> (AB -> AB -> Bool)
-> (AB -> AB -> Bool)
-> (AB -> AB -> Bool)
-> (AB -> AB -> Bool)
-> (AB -> AB -> AB)
-> (AB -> AB -> AB)
-> Ord AB
AB -> AB -> Bool
AB -> AB -> Ordering
AB -> AB -> AB
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: AB -> AB -> AB
$cmin :: AB -> AB -> AB
max :: AB -> AB -> AB
$cmax :: AB -> AB -> AB
>= :: AB -> AB -> Bool
$c>= :: AB -> AB -> Bool
> :: AB -> AB -> Bool
$c> :: AB -> AB -> Bool
<= :: AB -> AB -> Bool
$c<= :: AB -> AB -> Bool
< :: AB -> AB -> Bool
$c< :: AB -> AB -> Bool
compare :: AB -> AB -> Ordering
$ccompare :: AB -> AB -> Ordering
$cp1Ord :: Eq AB
Ord,Int -> AB -> ShowS
[AB] -> ShowS
AB -> String
(Int -> AB -> ShowS)
-> (AB -> String) -> ([AB] -> ShowS) -> Show AB
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [AB] -> ShowS
$cshowList :: [AB] -> ShowS
show :: AB -> String
$cshow :: AB -> String
showsPrec :: Int -> AB -> ShowS
$cshowsPrec :: Int -> AB -> ShowS
Show)

-- | Chern classes: @c1^i * c2^j@, monomial base of @Z[c1,c2]@
data Chern = Chern !Int !Int deriving (Chern -> Chern -> Bool
(Chern -> Chern -> Bool) -> (Chern -> Chern -> Bool) -> Eq Chern
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Chern -> Chern -> Bool
$c/= :: Chern -> Chern -> Bool
== :: Chern -> Chern -> Bool
$c== :: Chern -> Chern -> Bool
Eq,Eq Chern
Eq Chern
-> (Chern -> Chern -> Ordering)
-> (Chern -> Chern -> Bool)
-> (Chern -> Chern -> Bool)
-> (Chern -> Chern -> Bool)
-> (Chern -> Chern -> Bool)
-> (Chern -> Chern -> Chern)
-> (Chern -> Chern -> Chern)
-> Ord Chern
Chern -> Chern -> Bool
Chern -> Chern -> Ordering
Chern -> Chern -> Chern
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: Chern -> Chern -> Chern
$cmin :: Chern -> Chern -> Chern
max :: Chern -> Chern -> Chern
$cmax :: Chern -> Chern -> Chern
>= :: Chern -> Chern -> Bool
$c>= :: Chern -> Chern -> Bool
> :: Chern -> Chern -> Bool
$c> :: Chern -> Chern -> Bool
<= :: Chern -> Chern -> Bool
$c<= :: Chern -> Chern -> Bool
< :: Chern -> Chern -> Bool
$c< :: Chern -> Chern -> Bool
compare :: Chern -> Chern -> Ordering
$ccompare :: Chern -> Chern -> Ordering
$cp1Ord :: Eq Chern
Ord,Int -> Chern -> ShowS
[Chern] -> ShowS
Chern -> String
(Int -> Chern -> ShowS)
-> (Chern -> String) -> ([Chern] -> ShowS) -> Show Chern
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Chern] -> ShowS
$cshowList :: [Chern] -> ShowS
show :: Chern -> String
$cshow :: Chern -> String
showsPrec :: Int -> Chern -> ShowS
$cshowsPrec :: Int -> Chern -> ShowS
Show)

-- | Schur basis function: @S[i,j]@
data Schur = Schur !Int !Int deriving (Schur -> Schur -> Bool
(Schur -> Schur -> Bool) -> (Schur -> Schur -> Bool) -> Eq Schur
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Schur -> Schur -> Bool
$c/= :: Schur -> Schur -> Bool
== :: Schur -> Schur -> Bool
$c== :: Schur -> Schur -> Bool
Eq,Eq Schur
Eq Schur
-> (Schur -> Schur -> Ordering)
-> (Schur -> Schur -> Bool)
-> (Schur -> Schur -> Bool)
-> (Schur -> Schur -> Bool)
-> (Schur -> Schur -> Bool)
-> (Schur -> Schur -> Schur)
-> (Schur -> Schur -> Schur)
-> Ord Schur
Schur -> Schur -> Bool
Schur -> Schur -> Ordering
Schur -> Schur -> Schur
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: Schur -> Schur -> Schur
$cmin :: Schur -> Schur -> Schur
max :: Schur -> Schur -> Schur
$cmax :: Schur -> Schur -> Schur
>= :: Schur -> Schur -> Bool
$c>= :: Schur -> Schur -> Bool
> :: Schur -> Schur -> Bool
$c> :: Schur -> Schur -> Bool
<= :: Schur -> Schur -> Bool
$c<= :: Schur -> Schur -> Bool
< :: Schur -> Schur -> Bool
$c< :: Schur -> Schur -> Bool
compare :: Schur -> Schur -> Ordering
$ccompare :: Schur -> Schur -> Ordering
$cp1Ord :: Eq Schur
Ord,Int -> Schur -> ShowS
[Schur] -> ShowS
Schur -> String
(Int -> Schur -> ShowS)
-> (Schur -> String) -> ([Schur] -> ShowS) -> Show Schur
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Schur] -> ShowS
$cshowList :: [Schur] -> ShowS
show :: Schur -> String
$cshow :: Schur -> String
showsPrec :: Int -> Schur -> ShowS
$cshowsPrec :: Int -> Schur -> ShowS
Show) 

alpha, beta :: AB
alpha :: AB
alpha = Int -> Int -> AB
AB Int
1 Int
0 
beta :: AB
beta  = Int -> Int -> AB
AB Int
0 Int
1    

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

-- | @alpha * beta = c2@
alphaBeta :: AB
alphaBeta :: AB
alphaBeta = Int -> Int -> AB
AB Int
1 Int
1    

-- | @c1 = alpha + beta@
c1 :: Chern
c1 :: Chern
c1 = Int -> Int -> Chern
Chern Int
1 Int
0     

-- | @c2 = alpha * beta@
c2 :: Chern
c2 :: Chern
c2 = Int -> Int -> Chern
Chern Int
0 Int
1     

--------------------------------------------------------------------------------
-- * Unified interface

-- | A singleton for distinguishing the two cases 
data Sing base where
  ChernRoot  :: Sing AB
  ChernClass :: Sing Chern

deriving instance Eq  (Sing base)
deriving instance Ord (Sing base)

-- | Common interface to work with Chern classes and Chern roots uniformly
class (Eq base, Ord base, Monoid base, Graded base, Pretty base) => ChernBase base where
  chernTag  :: base       -> Sing base
  chernTag1 :: f base     -> Sing base
  chernTag2 :: f (g base)     -> Sing base
  chernTag3 :: f (g (h base)) -> Sing base
  fromAB    :: ZMod AB    -> ZMod base  
  fromChern :: ZMod Chern -> ZMod base  
  fromSchur :: ZMod Schur -> ZMod base
  toAB      :: ZMod base  -> ZMod AB  
  toChern   :: ZMod base  -> ZMod Chern
  toSchur   :: ZMod base  -> ZMod Schur

instance ChernBase AB where
  chernTag :: AB -> Sing AB
chernTag  AB
_ = Sing AB
ChernRoot
  chernTag1 :: f AB -> Sing AB
chernTag1 f AB
_ = Sing AB
ChernRoot
  chernTag2 :: f (g AB) -> Sing AB
chernTag2 f (g AB)
_ = Sing AB
ChernRoot
  chernTag3 :: f (g (h AB)) -> Sing AB
chernTag3 f (g (h AB))
_ = Sing AB
ChernRoot
  fromAB :: ZMod AB -> ZMod AB
fromAB     = ZMod AB -> ZMod AB
forall a. a -> a
id
  fromChern :: ZMod Chern -> ZMod AB
fromChern  = ZMod Chern -> ZMod AB
chernToAB
  fromSchur :: ZMod Schur -> ZMod AB
fromSchur  = ZMod Schur -> ZMod AB
schurToAB
  toAB :: ZMod AB -> ZMod AB
toAB       = ZMod AB -> ZMod AB
forall a. a -> a
id
  toChern :: ZMod AB -> ZMod Chern
toChern    = ZMod AB -> ZMod Chern
abToChern
  toSchur :: ZMod AB -> ZMod Schur
toSchur    = ZMod AB -> ZMod Schur
abToSchur

instance ChernBase Chern where
  chernTag :: Chern -> Sing Chern
chernTag  Chern
_ = Sing Chern
ChernClass
  chernTag1 :: f Chern -> Sing Chern
chernTag1 f Chern
_ = Sing Chern
ChernClass
  chernTag2 :: f (g Chern) -> Sing Chern
chernTag2 f (g Chern)
_ = Sing Chern
ChernClass
  chernTag3 :: f (g (h Chern)) -> Sing Chern
chernTag3 f (g (h Chern))
_ = Sing Chern
ChernClass
  fromAB :: ZMod AB -> ZMod Chern
fromAB     = ZMod AB -> ZMod Chern
abToChern
  fromChern :: ZMod Chern -> ZMod Chern
fromChern  = ZMod Chern -> ZMod Chern
forall a. a -> a
id
  fromSchur :: ZMod Schur -> ZMod Chern
fromSchur  = ZMod Schur -> ZMod Chern
schurToChern
  toAB :: ZMod Chern -> ZMod AB
toAB       = ZMod Chern -> ZMod AB
chernToAB
  toChern :: ZMod Chern -> ZMod Chern
toChern    = ZMod Chern -> ZMod Chern
forall a. a -> a
id
  toSchur :: ZMod Chern -> ZMod Schur
toSchur    = ZMod Chern -> ZMod Schur
chernToSchur

--------------------------------------------------------------------------------
-- * Helper functions for constructing and specializing uniform things

-- | Constructing uniform things
select0 :: (AB, Chern) -> (ChernBase base => base)
select0 :: (AB, Chern) -> ChernBase base => base
select0 (AB, Chern)
what = let final :: base
final = (AB, Chern) -> Sing base -> base
forall base. (AB, Chern) -> ChernBase base => Sing base -> base
select0' (AB, Chern)
what (base -> Sing base
forall base. ChernBase base => base -> Sing base
chernTag base
final) in base
final

select1 :: (f AB, f Chern) -> (ChernBase base => f base)
select1 :: (f AB, f Chern) -> ChernBase base => f base
select1 (f AB, f Chern)
what = let final :: f base
final = (f AB, f Chern) -> Sing base -> f base
forall (f :: * -> *) base.
(f AB, f Chern) -> ChernBase base => Sing base -> f base
select1' (f AB, f Chern)
what (f base -> Sing base
forall base (f :: * -> *). ChernBase base => f base -> Sing base
chernTag1 f base
final) in f base
final

select2 :: (f (g AB), f (g Chern)) -> (ChernBase base => f (g base))
select2 :: (f (g AB), f (g Chern)) -> ChernBase base => f (g base)
select2 (f (g AB), f (g Chern))
what = let final :: f (g base)
final = (f (g AB), f (g Chern)) -> Sing base -> f (g base)
forall (f :: * -> *) (g :: * -> *) base.
(f (g AB), f (g Chern))
-> ChernBase base => Sing base -> f (g base)
select2' (f (g AB), f (g Chern))
what (f (g base) -> Sing base
forall base (f :: * -> *) (g :: * -> *).
ChernBase base =>
f (g base) -> Sing base
chernTag2 f (g base)
final) in f (g base)
final

select3 :: (f (g (h AB)), f (g (h Chern))) -> (ChernBase base => f (g (h base)))
select3 :: (f (g (h AB)), f (g (h Chern))) -> ChernBase base => f (g (h base))
select3 (f (g (h AB)), f (g (h Chern)))
what = let final :: f (g (h base))
final = (f (g (h AB)), f (g (h Chern))) -> Sing base -> f (g (h base))
forall (f :: * -> *) (g :: * -> *) (h :: * -> *) base.
(f (g (h AB)), f (g (h Chern)))
-> ChernBase base => Sing base -> f (g (h base))
select3' (f (g (h AB)), f (g (h Chern)))
what (f (g (h base)) -> Sing base
forall base (f :: * -> *) (g :: * -> *) (h :: * -> *).
ChernBase base =>
f (g (h base)) -> Sing base
chernTag3 f (g (h base))
final) in f (g (h base))
final

-- | Constructing unifom things using a tag
select0' :: (AB, Chern) -> (ChernBase base => Sing base -> base)
select0' :: (AB, Chern) -> ChernBase base => Sing base -> base
select0' (AB
ab,Chern
ch) = \Sing base
sing -> case Sing base
sing of { Sing base
ChernRoot -> base
AB
ab ; Sing base
ChernClass -> base
Chern
ch }

select1' :: (f AB, f Chern) -> (ChernBase base => Sing base -> f base)
select1' :: (f AB, f Chern) -> ChernBase base => Sing base -> f base
select1' (f AB
ab,f Chern
ch) = \Sing base
sing -> case Sing base
sing of { Sing base
ChernRoot -> f base
f AB
ab ; Sing base
ChernClass -> f base
f Chern
ch }

select2' :: (f (g AB), f (g Chern)) -> (ChernBase base => Sing base -> f (g base))
select2' :: (f (g AB), f (g Chern))
-> ChernBase base => Sing base -> f (g base)
select2' (f (g AB)
ab,f (g Chern)
ch) = \Sing base
sing -> case Sing base
sing of { Sing base
ChernRoot -> f (g base)
f (g AB)
ab ; Sing base
ChernClass -> f (g base)
f (g Chern)
ch }

select3' :: (f (g (h AB)), f (g (h Chern))) -> (ChernBase base => Sing base -> f (g (h base)))
select3' :: (f (g (h AB)), f (g (h Chern)))
-> ChernBase base => Sing base -> f (g (h base))
select3' (f (g (h AB))
ab,f (g (h Chern))
ch) = \Sing base
sing -> case Sing base
sing of { Sing base
ChernRoot -> f (g (h base))
f (g (h AB))
ab ; Sing base
ChernClass -> f (g (h base))
f (g (h Chern))
ch }

-- | Specializing uniform things
spec0' :: ChernBase base => Sing base -> (forall b. ChernBase b => b) -> base
spec0' :: Sing base -> (forall b. ChernBase b => b) -> base
spec0' Sing base
_ forall b. ChernBase b => b
x = base
forall b. ChernBase b => b
x

spec1' :: ChernBase base => Sing base -> (forall b. ChernBase b => f b) -> f base
spec1' :: Sing base -> (forall b. ChernBase b => f b) -> f base
spec1' Sing base
_ forall b. ChernBase b => f b
x = f base
forall b. ChernBase b => f b
x

spec2' :: ChernBase base => Sing base -> (forall b. ChernBase b => f (g b)) -> f (g base)
spec2' :: Sing base -> (forall b. ChernBase b => f (g b)) -> f (g base)
spec2' Sing base
_ forall b. ChernBase b => f (g b)
x = f (g base)
forall b. ChernBase b => f (g b)
x

spec3' :: ChernBase base => Sing base -> (forall b. ChernBase b => f (g (h b))) -> f (g (h base))
spec3' :: Sing base
-> (forall b. ChernBase b => f (g (h b))) -> f (g (h base))
spec3' Sing base
_ forall b. ChernBase b => f (g (h b))
x = f (g (h base))
forall b. ChernBase b => f (g (h b))
x

{-
proxyOf :: a -> Proxy a
proxyOf _ = Proxy

proxyOf1 :: f a -> Proxy a
proxyOf1 _ = Proxy

proxyOf2 :: g (f a) -> Proxy a
proxyOf2 _ = Proxy
-}

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

-- Semigroup became a superclass of Monoid
#if MIN_VERSION_base(4,11,0)        

instance Semigroup AB where
  (AB Int
a1 Int
b1) <> :: AB -> AB -> AB
<> (AB Int
a2 Int
b2) = Int -> Int -> AB
AB (Int
a1Int -> Int -> Int
forall a. Num a => a -> a -> a
+Int
a2) (Int
b1Int -> Int -> Int
forall a. Num a => a -> a -> a
+Int
b2)

instance Semigroup Chern where
  (Chern Int
e1 Int
f1) <> :: Chern -> Chern -> Chern
<> (Chern Int
e2 Int
f2) = Int -> Int -> Chern
Chern (Int
e1Int -> Int -> Int
forall a. Num a => a -> a -> a
+Int
e2) (Int
f1Int -> Int -> Int
forall a. Num a => a -> a -> a
+Int
f2)

instance Semigroup Schur where
  <> :: Schur -> Schur -> Schur
(<>) = String -> Schur -> Schur -> Schur
forall a. HasCallStack => String -> a
error String
"Schur/mappend: not a monoid"

instance Monoid AB where
  mempty :: AB
mempty = Int -> Int -> AB
AB Int
0 Int
0 

instance Monoid Chern where
  mempty :: Chern
mempty = Int -> Int -> Chern
Chern Int
0 Int
0 

instance Monoid Schur where
  mempty :: Schur
mempty  = Int -> Int -> Schur
Schur Int
0 Int
0

#else

instance Monoid AB where
  mempty = AB 0 0 
  (AB a1 b1) `mappend` (AB a2 b2) = AB (a1+a2) (b1+b2)

instance Monoid Chern where
  mempty = Chern 0 0 
  (Chern e1 f1) `mappend` (Chern e2 f2) = Chern (e1+e2) (f1+f2)

instance Monoid Schur where
  mempty  = Schur 0 0
  mappend = error "Schur/mappend: not a monoid"

#endif

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

instance Pretty AB where
  pretty :: AB -> String
pretty AB
ab = case AB
ab of
    AB Int
0 Int
0 -> String
"" 
    AB Int
e Int
0 -> String -> Int -> String
showVarPower String
"a" Int
e
    AB Int
0 Int
f -> String -> Int -> String
showVarPower String
"b" Int
f
    AB Int
e Int
f -> String -> Int -> String
showVarPower String
"a" Int
e String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
"*" String -> ShowS
forall a. [a] -> [a] -> [a]
++ String -> Int -> String
showVarPower String
"b" Int
f
 
instance Pretty Chern where
  pretty :: Chern -> String
pretty (Chern Int
0 Int
0) = String
""
  pretty (Chern Int
e Int
0) = String -> Int -> String
showVarPower String
"c1" Int
e
  pretty (Chern Int
0 Int
f) = String -> Int -> String
showVarPower String
"c2" Int
f
  pretty (Chern Int
e Int
f) = String -> Int -> String
showVarPower String
"c1" Int
e String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
"*" String -> ShowS
forall a. [a] -> [a] -> [a]
++ String -> Int -> String
showVarPower String
"c2" Int
f

instance Pretty Schur where
  pretty :: Schur -> String
pretty (Schur Int
a Int
b) 
    | Int
b Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0     = String
"s[" String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
a String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
"]"
    | Bool
otherwise  = String
"s[" String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
a String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
"," String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
b String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
"]"

--------------------------------------------------------------------------------
-- * Grading

class Graded a where
  grade :: a -> Int

instance Graded AB    where grade :: AB -> Int
grade (AB    Int
a Int
b) = Int
a Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
b
instance Graded Chern where grade :: Chern -> Int
grade (Chern Int
e Int
f) = Int
e Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
2Int -> Int -> Int
forall a. Num a => a -> a -> a
*Int
f
instance Graded Schur where grade :: Schur -> Int
grade (Schur Int
i Int
j) = Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
j

-- | Filters out the given grade
filterGrade :: (Ord b, Graded b) => Int -> ZMod b -> ZMod b
filterGrade :: Int -> ZMod b -> ZMod b
filterGrade Int
g = (Map b Integer -> Map b Integer) -> ZMod b -> ZMod b
forall a b c.
(Ord a, Ord b) =>
(Map a c -> Map b c) -> FreeMod c a -> FreeMod c b
ZMod.onFreeMod Map b Integer -> Map b Integer
filt where
  filt :: Map b Integer -> Map b Integer
filt = (b -> Integer -> Bool) -> Map b Integer -> Map b Integer
forall k a. (k -> a -> Bool) -> Map k a -> Map k a
Map.filterWithKey ((b -> Integer -> Bool) -> Map b Integer -> Map b Integer)
-> (b -> Integer -> Bool) -> Map b Integer -> Map b Integer
forall a b. (a -> b) -> a -> b
$ \b
x Integer
_ -> (b -> Int
forall a. Graded a => a -> Int
grade b
x Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
g)

-- | Separates the different grades
separateGradedParts :: (Ord b, Graded b) => ZMod b -> Array Int (ZMod b)
separateGradedParts :: ZMod b -> Array Int (ZMod b)
separateGradedParts ZMod b
input = Array Int (ZMod b)
arr where
  table :: Map Int [(b, Integer)]
table = (Map Int [(b, Integer)] -> (b, Integer) -> Map Int [(b, Integer)])
-> Map Int [(b, Integer)]
-> [(b, Integer)]
-> Map Int [(b, Integer)]
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' Map Int [(b, Integer)] -> (b, Integer) -> Map Int [(b, Integer)]
forall a b.
Graded a =>
Map Int [(a, b)] -> (a, b) -> Map Int [(a, b)]
worker Map Int [(b, Integer)]
forall k a. Map k a
Map.empty (ZMod b -> [(b, Integer)]
forall c b. FreeMod c b -> [(b, c)]
ZMod.toList ZMod b
input) 
  worker :: Map Int [(a, b)] -> (a, b) -> Map Int [(a, b)]
worker !Map Int [(a, b)]
old (a
base,b
coeff) = ((a, b) -> [(a, b)])
-> ((a, b) -> [(a, b)] -> [(a, b)])
-> Int
-> (a, b)
-> Map Int [(a, b)]
-> Map Int [(a, b)]
forall k b a.
Ord k =>
(b -> a) -> (b -> a -> a) -> k -> b -> Map k a -> Map k a
insertMap ((a, b) -> [(a, b)] -> [(a, b)]
forall a. a -> [a] -> [a]
:[]) (:) (a -> Int
forall a. Graded a => a -> Int
grade a
base) (a
base,b
coeff) Map Int [(a, b)]
old
  size :: Int
size  = if Map Int [(b, Integer)] -> Bool
forall k a. Map k a -> Bool
Map.null Map Int [(b, Integer)]
table then Int
0 else (Int, [(b, Integer)]) -> Int
forall a b. (a, b) -> a
fst (Map Int [(b, Integer)] -> (Int, [(b, Integer)])
forall k a. Map k a -> (k, a)
Map.findMax Map Int [(b, Integer)]
table)
  arr :: Array Int (ZMod b)
arr   = (Int, Int) -> [ZMod b] -> Array Int (ZMod b)
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
(i, i) -> [e] -> a i e
listArray (Int
0,Int
size) 
            [ [(b, Integer)] -> ZMod b
forall c b. (Eq c, Num c, Ord b) => [(b, c)] -> FreeMod c b
ZMod.fromList ([(b, Integer)] -> Int -> Map Int [(b, Integer)] -> [(b, Integer)]
forall k a. Ord k => a -> k -> Map k a -> a
Map.findWithDefault [] Int
d Map Int [(b, Integer)]
table) 
            | Int
d <- [Int
0..Int
size] ]

--------------------------------------------------------------------------------
-- * Conversions

chernToAB :: ZMod Chern -> ZMod AB 
chernToAB :: ZMod Chern -> ZMod AB
chernToAB = (Chern -> ZMod AB) -> ZMod Chern -> ZMod AB
forall b1 b2 c.
(Ord b1, Ord b2, Eq c, Num c) =>
(b1 -> FreeMod c b2) -> FreeMod c b1 -> FreeMod c b2
ZMod.flatMap Chern -> ZMod AB
expandToAlphaBeta_1 where

  -- | c1^k * c2^n = (alpha+beta)^k * (alpha*beta)^n
  expandToAlphaBeta_1 :: Chern -> ZMod AB 
  expandToAlphaBeta_1 :: Chern -> ZMod AB
expandToAlphaBeta_1 (Chern Int
k Int
n) = [(AB, Integer)] -> ZMod AB
forall c b. (Eq c, Num c, Ord b) => [(b, c)] -> FreeMod c b
ZMod.fromList [ (Int -> Int -> AB
AB (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
i) (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
kInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
i) , Int -> Int -> Integer
forall a. Integral a => a -> a -> Integer
binomial Int
k Int
i) | Int
i<-[Int
0..Int
k] ]

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

-- | Converts a symmetric polynomial in the AB base (Chern roots) 
-- to the Chern base (elementary symmetric polynomials or Chern classes)
abToChern :: ZMod AB -> ZMod Chern
abToChern :: ZMod AB -> ZMod Chern
abToChern ZMod AB
ab = case ZMod AB -> Either (ZMod Chern, ZMod AB) (ZMod Chern)
symmetricReduction ZMod AB
ab of
  Right ZMod Chern
c -> ZMod Chern
c
  Left (ZMod Chern, ZMod AB)
_  -> String -> ZMod Chern
forall a. HasCallStack => String -> a
error String
"abToChern: input was not symmetric"

-- | @Left@ means there is a non-symmetric remainder; @Right@ means
-- that input was symmetric.
symmetricReduction :: ZMod AB -> Either (ZMod Chern, ZMod AB) (ZMod Chern)
symmetricReduction :: ZMod AB -> Either (ZMod Chern, ZMod AB) (ZMod Chern)
symmetricReduction = [(Chern, Integer)]
-> ZMod AB -> Either (ZMod Chern, ZMod AB) (ZMod Chern)
go [] where

  go :: [(Chern, Integer)]
-> ZMod AB -> Either (ZMod Chern, ZMod AB) (ZMod Chern)
go [(Chern, Integer)]
sofar ZMod AB
zmod = case ZMod AB -> Maybe (AB, Integer)
forall b c. Ord b => FreeMod c b -> Maybe (b, c)
ZMod.findMaxTerm ZMod AB
zmod of
    Maybe (AB, Integer)
Nothing          -> ZMod Chern -> Either (ZMod Chern, ZMod AB) (ZMod Chern)
forall a b. b -> Either a b
Right ZMod Chern
q
    Just (AB Int
n Int
m, Integer
k) -> if Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
m
      then (ZMod Chern, ZMod AB) -> Either (ZMod Chern, ZMod AB) (ZMod Chern)
forall a b. a -> Either a b
Left (ZMod Chern
q,ZMod AB
zmod)
      else [(Chern, Integer)]
-> ZMod AB -> Either (ZMod Chern, ZMod AB) (ZMod Chern)
go ((Chern
ch,Integer
k)(Chern, Integer) -> [(Chern, Integer)] -> [(Chern, Integer)]
forall a. a -> [a] -> [a]
:[(Chern, Integer)]
sofar) (ZMod AB
zmod ZMod AB -> ZMod AB -> ZMod AB
forall a. Num a => a -> a -> a
- ZMod AB
this) where
        ch :: Chern
ch   = Int -> Int -> Chern
Chern (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
m) Int
m
        this :: ZMod AB
this = Integer -> ZMod AB -> ZMod AB
forall b c. (Ord b, Eq c, Num c) => c -> FreeMod c b -> FreeMod c b
ZMod.scale Integer
k (ZMod AB -> ZMod AB) -> ZMod AB -> ZMod AB
forall a b. (a -> b) -> a -> b
$ Chern -> ZMod AB
expandToAlphaBeta_1 Chern
ch
    where
      q :: ZMod Chern
q = [(Chern, Integer)] -> ZMod Chern
forall c b. (Eq c, Num c, Ord b) => [(b, c)] -> FreeMod c b
ZMod.fromList [(Chern, Integer)]
sofar

  -- | c1^k * c2^n = (alpha+beta)^k * (alpha*beta)^n
  expandToAlphaBeta_1 :: Chern -> ZMod AB 
  expandToAlphaBeta_1 :: Chern -> ZMod AB
expandToAlphaBeta_1 (Chern Int
k Int
n) = [(AB, Integer)] -> ZMod AB
forall c b. (Eq c, Num c, Ord b) => [(b, c)] -> FreeMod c b
ZMod.fromList [ (Int -> Int -> AB
AB (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
i) (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
kInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
i) , Int -> Int -> Integer
forall a. Integral a => a -> a -> Integer
binomial Int
k Int
i) | Int
i<-[Int
0..Int
k] ]
            
--------------------------------------------------------------------------------

-- | Convert Schur to Chern roots
schurToAB :: ZMod Schur -> ZMod AB
schurToAB :: ZMod Schur -> ZMod AB
schurToAB = (Schur -> ZMod AB) -> ZMod Schur -> ZMod AB
forall b1 b2 c.
(Ord b1, Ord b2, Eq c, Num c) =>
(b1 -> FreeMod c b2) -> FreeMod c b1 -> FreeMod c b2
ZMod.flatMap Schur -> ZMod AB
schurExpandAB_1 where

  schurExpandAB_1 :: Schur -> ZMod AB
  schurExpandAB_1 :: Schur -> ZMod AB
schurExpandAB_1 (Schur Int
a Int
b)
    | Int
b Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
a     = String -> ZMod AB
forall a. HasCallStack => String -> a
error String
"schurExpandAB"
    | Int
b Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0     = String -> ZMod AB
forall a. HasCallStack => String -> a
error String
"schurExpandAB"
    | Bool
otherwise = [(AB, Integer)] -> ZMod AB
forall c b. (Eq c, Num c, Ord b) => [(b, c)] -> FreeMod c b
ZMod.fromList [ ( Int -> Int -> AB
AB (Int
aInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
j) (Int
bInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
j) , Integer
1 ) | Int
j <- [Int
0..Int
aInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
b] ]

  {-
    schurab[i_, j_] := 
     Expand[Factor[ Det[{{a^(i + 1), b^(i + 1)}, {a^j, b^j}}]] / 
       Det[{{a, b}, {1, 1}}] ]
  -}

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

-- | Convert Schur to Chern classes (elementary symmetric polynomials)
schurToChern :: ZMod Schur -> ZMod Chern
schurToChern :: ZMod Schur -> ZMod Chern
schurToChern = (Schur -> ZMod Chern) -> ZMod Schur -> ZMod Chern
forall b1 b2 c.
(Ord b1, Ord b2, Eq c, Num c) =>
(b1 -> FreeMod c b2) -> FreeMod c b1 -> FreeMod c b2
ZMod.flatMap Schur -> ZMod Chern
schurExpandChern_1 where

  schurExpandChern_1 :: Schur -> ZMod Chern
  schurExpandChern_1 :: Schur -> ZMod Chern
schurExpandChern_1 (Schur Int
a Int
b) 
    | Int
b Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
a     = String -> ZMod Chern
forall a. HasCallStack => String -> a
error String
"schurExpandChern_1"
    | Int
b Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0     = String -> ZMod Chern
forall a. HasCallStack => String -> a
error String
"schurExpandChern_1"
    | Bool
otherwise = [(Chern, Integer)] -> ZMod Chern
forall c b. (Eq c, Num c, Ord b) => [(b, c)] -> FreeMod c b
ZMod.fromList [ ( Int -> Int -> Chern
Chern (Int
aInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
bInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
2Int -> Int -> Int
forall a. Num a => a -> a -> a
*Int
j) (Int
bInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
j) , Int -> Integer
forall a. Integral a => a -> Integer
paritySignValue Int
j Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Int -> Int -> Integer
forall a. Integral a => a -> a -> Integer
binomial (Int
aInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
bInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
j) Int
j ) | Int
j <- [Int
0..(Int -> Int -> Int
forall a. Integral a => a -> a -> a
div (Int
aInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
b) Int
2)] ]

  --  schurcd[i_, j_] := SymmetricReduction[schurab[i, j], {a, b}, {c1, c2}][[1]]

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

chernToSchur :: ZMod Chern -> ZMod Schur
chernToSchur :: ZMod Chern -> ZMod Schur
chernToSchur = (Chern -> ZMod Schur) -> ZMod Chern -> ZMod Schur
forall b1 b2 c.
(Ord b1, Ord b2, Eq c, Num c) =>
(b1 -> FreeMod c b2) -> FreeMod c b1 -> FreeMod c b2
ZMod.flatMap Chern -> ZMod Schur
chernExpandSchur_1 where

  chernExpandSchur_1 :: Chern -> ZMod Schur
  chernExpandSchur_1 :: Chern -> ZMod Schur
chernExpandSchur_1 (Chern Int
e Int
f)
    | Int
e Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 Bool -> Bool -> Bool
|| Int
f Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 = String -> ZMod Schur
forall a. HasCallStack => String -> a
error String
"chernExpandSchur"
    | Bool
otherwise      = [(Schur, Integer)] -> ZMod Schur
forall c b. (Eq c, Num c, Ord b) => [(b, c)] -> FreeMod c b
ZMod.fromList [ ( Int -> Int -> Schur
Schur (Int
eInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
fInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
i) (Int
fInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
i) , Int -> Int -> Integer
forall a. Integral a => a -> a -> Integer
catalanTriangle (Int
eInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
i) Int
i) | Int
i<-[Int
0..(Int -> Int -> Int
forall a. Integral a => a -> a -> a
div Int
e Int
2)] ]

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

abToSchur :: ZMod AB -> ZMod Schur
abToSchur :: ZMod AB -> ZMod Schur
abToSchur = ZMod Chern -> ZMod Schur
chernToSchur (ZMod Chern -> ZMod Schur)
-> (ZMod AB -> ZMod Chern) -> ZMod AB -> ZMod Schur
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ZMod AB -> ZMod Chern
abToChern

chernToSchurNaive :: ZMod Chern -> ZMod Schur
chernToSchurNaive :: ZMod Chern -> ZMod Schur
chernToSchurNaive = [(Schur, Integer)] -> ZMod Schur
forall c b. (Eq c, Num c, Ord b) => [(b, c)] -> FreeMod c b
ZMod.fromList ([(Schur, Integer)] -> ZMod Schur)
-> (ZMod Chern -> [(Schur, Integer)]) -> ZMod Chern -> ZMod Schur
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ZMod Chern -> [(Schur, Integer)]
go where

  go :: ZMod Chern -> [(Schur, Integer)]
go ZMod Chern
zmod = case ZMod Chern -> Maybe (Chern, Integer)
forall b c. Ord b => FreeMod c b -> Maybe (b, c)
ZMod.findMaxTerm ZMod Chern
zmod of 
    Maybe (Chern, Integer)
Nothing             ->  []
    Just (Chern Int
a Int
b, Integer
k) -> ( Schur
s , Integer
k ) (Schur, Integer) -> [(Schur, Integer)] -> [(Schur, Integer)]
forall a. a -> [a] -> [a]
: ZMod Chern -> [(Schur, Integer)]
go (ZMod Chern
zmod ZMod Chern -> ZMod Chern -> ZMod Chern
forall a. Num a => a -> a -> a
- ZMod Chern
this) where
      this :: ZMod Chern
this = Integer -> ZMod Chern -> ZMod Chern
forall b c. (Ord b, Eq c, Num c) => c -> FreeMod c b -> FreeMod c b
ZMod.scale Integer
k (ZMod Chern -> ZMod Chern) -> ZMod Chern -> ZMod Chern
forall a b. (a -> b) -> a -> b
$ Schur -> ZMod Chern
schurExpandChern_1 Schur
s
      s :: Schur
s    = Int -> Int -> Schur
Schur (Int
aInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
b) Int
b

  schurExpandChern_1 :: Schur -> ZMod Chern
  schurExpandChern_1 :: Schur -> ZMod Chern
schurExpandChern_1 (Schur Int
a Int
b) 
    | Int
b Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
a     = String -> ZMod Chern
forall a. HasCallStack => String -> a
error String
"schurExpandChern_1"
    | Int
b Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0     = String -> ZMod Chern
forall a. HasCallStack => String -> a
error String
"schurExpandChern_1"
    | Bool
otherwise = [(Chern, Integer)] -> ZMod Chern
forall c b. (Eq c, Num c, Ord b) => [(b, c)] -> FreeMod c b
ZMod.fromList [ ( Int -> Int -> Chern
Chern (Int
aInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
bInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
2Int -> Int -> Int
forall a. Num a => a -> a -> a
*Int
j) (Int
bInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
j) , Int -> Integer
forall a. Integral a => a -> Integer
paritySignValue Int
j Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Int -> Int -> Integer
forall a. Integral a => a -> a -> Integer
binomial (Int
aInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
bInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
j) Int
j ) | Int
j <- [Int
0..(Int -> Int -> Int
forall a. Integral a => a -> a -> a
div (Int
aInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
b) Int
2)] ]

--------------------------------------------------------------------------------
-- * random polynomials for testing

randomChernMonom :: IO Chern
randomChernMonom :: IO Chern
randomChernMonom = do
  Int
a <- (Int, Int) -> IO Int
forall a (m :: * -> *). (Random a, MonadIO m) => (a, a) -> m a
randomRIO (Int
0,Int
30)
  Int
b <- (Int, Int) -> IO Int
forall a (m :: * -> *). (Random a, MonadIO m) => (a, a) -> m a
randomRIO (Int
0,Int
15)
  Chern -> IO Chern
forall (m :: * -> *) a. Monad m => a -> m a
return (Int -> Int -> Chern
Chern Int
a Int
b)

randomSchurMonom :: IO Schur
randomSchurMonom :: IO Schur
randomSchurMonom = do
  Int
a <- (Int, Int) -> IO Int
forall a (m :: * -> *). (Random a, MonadIO m) => (a, a) -> m a
randomRIO (Int
0,Int
30)
  Int
b <- (Int, Int) -> IO Int
forall a (m :: * -> *). (Random a, MonadIO m) => (a, a) -> m a
randomRIO (Int
0,Int
30)
  Schur -> IO Schur
forall (m :: * -> *) a. Monad m => a -> m a
return (Int -> Int -> Schur
Schur (Int
aInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
b) Int
b)

withRandomCoeff :: IO a -> IO (a,Integer)
withRandomCoeff :: IO a -> IO (a, Integer)
withRandomCoeff IO a
rnd = do
  Integer
k <- (Integer, Integer) -> IO Integer
forall a (m :: * -> *). (Random a, MonadIO m) => (a, a) -> m a
randomRIO (-Integer
100,Integer
100)
  a
x <- IO a
rnd
  (a, Integer) -> IO (a, Integer)
forall (m :: * -> *) a. Monad m => a -> m a
return (a
x,Integer
k)

randomChernPoly :: IO (ZMod Chern)   
randomChernPoly :: IO (ZMod Chern)
randomChernPoly = do
  Int
n <- (Int, Int) -> IO Int
forall a (m :: * -> *). (Random a, MonadIO m) => (a, a) -> m a
randomRIO (Int
0,Int
100)
  [(Chern, Integer)] -> ZMod Chern
forall c b. (Eq c, Num c, Ord b) => [(b, c)] -> FreeMod c b
ZMod.fromList ([(Chern, Integer)] -> ZMod Chern)
-> IO [(Chern, Integer)] -> IO (ZMod Chern)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Int -> IO (Chern, Integer) -> IO [(Chern, Integer)]
forall (m :: * -> *) a. Applicative m => Int -> m a -> m [a]
replicateM Int
n (IO Chern -> IO (Chern, Integer)
forall a. IO a -> IO (a, Integer)
withRandomCoeff IO Chern
randomChernMonom)

randomSchurPoly :: IO (ZMod Schur)   
randomSchurPoly :: IO (ZMod Schur)
randomSchurPoly = do
  Int
n <- (Int, Int) -> IO Int
forall a (m :: * -> *). (Random a, MonadIO m) => (a, a) -> m a
randomRIO (Int
0,Int
100)
  [(Schur, Integer)] -> ZMod Schur
forall c b. (Eq c, Num c, Ord b) => [(b, c)] -> FreeMod c b
ZMod.fromList ([(Schur, Integer)] -> ZMod Schur)
-> IO [(Schur, Integer)] -> IO (ZMod Schur)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Int -> IO (Schur, Integer) -> IO [(Schur, Integer)]
forall (m :: * -> *) a. Applicative m => Int -> m a -> m [a]
replicateM Int
n (IO Schur -> IO (Schur, Integer)
forall a. IO a -> IO (a, Integer)
withRandomCoeff IO Schur
randomSchurMonom)

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