-- | Multivariate polynomials where the variable set is the countably infinite
-- set @{x_1, x_2, x_3, ...}@ 

{-# LANGUAGE 
      BangPatterns, TypeFamilies, DataKinds, KindSignatures, ScopedTypeVariables,
      FlexibleContexts
  #-}
module Math.Algebra.Polynomial.Multivariate.Infinite
  (
    Poly(..) , unPoly , polyVar , renamePolyVar
  , ZPoly , QPoly , fromZPoly, fromQPoly
  , truncate
  , XInf(..)
  )
  where

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

import Prelude hiding ( truncate )

import Data.Maybe
import Data.List
import Data.Array.Unboxed 

import Data.Typeable
import GHC.TypeLits
import Data.Proxy
import Unsafe.Coerce as Unsafe

import Data.Foldable as F 

import qualified Math.Algebra.Polynomial.FreeModule as ZMod
import Math.Algebra.Polynomial.FreeModule ( FreeMod , FreeModule(..) ) -- , ZMod , QMod )

import Math.Algebra.Polynomial.Monomial.Infinite

import Math.Algebra.Polynomial.Class
import Math.Algebra.Polynomial.Pretty
import Math.Algebra.Polynomial.Misc

import qualified Math.Algebra.Polynomial.Monomial.Indexed     as Fin
import qualified Math.Algebra.Polynomial.Multivariate.Indexed as Fin

--------------------------------------------------------------------------------
-- * Polynomials

-- | A multivariate polynomial in with a given coefficient ring. 
--
-- It is also indexed by the (shared) /name/ of the variables and the /number of/
-- variable. For example @Polyn Rational "x" 3@ the type of polynomials in the
-- variables @x1, x2, x3@ with rational coefficients.
newtype Poly (coeff :: *) (var :: Symbol) 
  = Poly (FreeMod coeff (XInf var))
  deriving (Poly coeff var -> Poly coeff var -> Bool
(Poly coeff var -> Poly coeff var -> Bool)
-> (Poly coeff var -> Poly coeff var -> Bool)
-> Eq (Poly coeff var)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall coeff (var :: Symbol).
Eq coeff =>
Poly coeff var -> Poly coeff var -> Bool
/= :: Poly coeff var -> Poly coeff var -> Bool
$c/= :: forall coeff (var :: Symbol).
Eq coeff =>
Poly coeff var -> Poly coeff var -> Bool
== :: Poly coeff var -> Poly coeff var -> Bool
$c== :: forall coeff (var :: Symbol).
Eq coeff =>
Poly coeff var -> Poly coeff var -> Bool
Eq,Eq (Poly coeff var)
Eq (Poly coeff var)
-> (Poly coeff var -> Poly coeff var -> Ordering)
-> (Poly coeff var -> Poly coeff var -> Bool)
-> (Poly coeff var -> Poly coeff var -> Bool)
-> (Poly coeff var -> Poly coeff var -> Bool)
-> (Poly coeff var -> Poly coeff var -> Bool)
-> (Poly coeff var -> Poly coeff var -> Poly coeff var)
-> (Poly coeff var -> Poly coeff var -> Poly coeff var)
-> Ord (Poly coeff var)
Poly coeff var -> Poly coeff var -> Bool
Poly coeff var -> Poly coeff var -> Ordering
Poly coeff var -> Poly coeff var -> Poly coeff var
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
forall coeff (var :: Symbol). Ord coeff => Eq (Poly coeff var)
forall coeff (var :: Symbol).
Ord coeff =>
Poly coeff var -> Poly coeff var -> Bool
forall coeff (var :: Symbol).
Ord coeff =>
Poly coeff var -> Poly coeff var -> Ordering
forall coeff (var :: Symbol).
Ord coeff =>
Poly coeff var -> Poly coeff var -> Poly coeff var
min :: Poly coeff var -> Poly coeff var -> Poly coeff var
$cmin :: forall coeff (var :: Symbol).
Ord coeff =>
Poly coeff var -> Poly coeff var -> Poly coeff var
max :: Poly coeff var -> Poly coeff var -> Poly coeff var
$cmax :: forall coeff (var :: Symbol).
Ord coeff =>
Poly coeff var -> Poly coeff var -> Poly coeff var
>= :: Poly coeff var -> Poly coeff var -> Bool
$c>= :: forall coeff (var :: Symbol).
Ord coeff =>
Poly coeff var -> Poly coeff var -> Bool
> :: Poly coeff var -> Poly coeff var -> Bool
$c> :: forall coeff (var :: Symbol).
Ord coeff =>
Poly coeff var -> Poly coeff var -> Bool
<= :: Poly coeff var -> Poly coeff var -> Bool
$c<= :: forall coeff (var :: Symbol).
Ord coeff =>
Poly coeff var -> Poly coeff var -> Bool
< :: Poly coeff var -> Poly coeff var -> Bool
$c< :: forall coeff (var :: Symbol).
Ord coeff =>
Poly coeff var -> Poly coeff var -> Bool
compare :: Poly coeff var -> Poly coeff var -> Ordering
$ccompare :: forall coeff (var :: Symbol).
Ord coeff =>
Poly coeff var -> Poly coeff var -> Ordering
$cp1Ord :: forall coeff (var :: Symbol). Ord coeff => Eq (Poly coeff var)
Ord,Int -> Poly coeff var -> ShowS
[Poly coeff var] -> ShowS
Poly coeff var -> String
(Int -> Poly coeff var -> ShowS)
-> (Poly coeff var -> String)
-> ([Poly coeff var] -> ShowS)
-> Show (Poly coeff var)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall coeff (var :: Symbol).
Show coeff =>
Int -> Poly coeff var -> ShowS
forall coeff (var :: Symbol).
Show coeff =>
[Poly coeff var] -> ShowS
forall coeff (var :: Symbol).
Show coeff =>
Poly coeff var -> String
showList :: [Poly coeff var] -> ShowS
$cshowList :: forall coeff (var :: Symbol).
Show coeff =>
[Poly coeff var] -> ShowS
show :: Poly coeff var -> String
$cshow :: forall coeff (var :: Symbol).
Show coeff =>
Poly coeff var -> String
showsPrec :: Int -> Poly coeff var -> ShowS
$cshowsPrec :: forall coeff (var :: Symbol).
Show coeff =>
Int -> Poly coeff var -> ShowS
Show,Typeable)

unPoly :: Poly c v -> FreeMod c (XInf v) 
unPoly :: Poly c v -> FreeMod c (XInf v)
unPoly (Poly FreeMod c (XInf v)
p) = FreeMod c (XInf v)
p

-- | Name of the variables
polyVar :: KnownSymbol var => Poly c var -> String
polyVar :: Poly c var -> String
polyVar = Proxy var -> String
forall (n :: Symbol) (proxy :: Symbol -> *).
KnownSymbol n =>
proxy n -> String
symbolVal (Proxy var -> String)
-> (Poly c var -> Proxy var) -> Poly c var -> String
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Poly c var -> Proxy var
forall c (var :: Symbol). Poly c var -> Proxy var
varProxy where
  varProxy :: Poly c var -> Proxy var
  varProxy :: Poly c var -> Proxy var
varProxy Poly c var
_ = Proxy var
forall k (t :: k). Proxy t
Proxy

instance FreeModule (Poly c v) where
  type BaseF  (Poly c v) = XInf v 
  type CoeffF (Poly c v) = c
  toFreeModule :: Poly c v -> FreeMod (CoeffF (Poly c v)) (BaseF (Poly c v))
toFreeModule   = Poly c v -> FreeMod (CoeffF (Poly c v)) (BaseF (Poly c v))
forall c (v :: Symbol). Poly c v -> FreeMod c (XInf v)
unPoly
  fromFreeModule :: FreeMod (CoeffF (Poly c v)) (BaseF (Poly c v)) -> Poly c v
fromFreeModule = FreeMod (CoeffF (Poly c v)) (BaseF (Poly c v)) -> Poly c v
forall coeff (var :: Symbol).
FreeMod coeff (XInf var) -> Poly coeff var
Poly

renamePolyVar :: Poly c var1 -> Poly c var2 
renamePolyVar :: Poly c var1 -> Poly c var2
renamePolyVar = Poly c var1 -> Poly c var2
forall a b. a -> b
Unsafe.unsafeCoerce

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

type ZPoly = Poly Integer
type QPoly = Poly Rational

-- | Change the coefficient ring (from integers)
fromZPoly :: (Ring c, KnownSymbol v) => Poly Integer v -> Poly c v 
fromZPoly :: Poly Integer v -> Poly c v
fromZPoly= FreeMod c (XInf v) -> Poly c v
forall coeff (var :: Symbol).
FreeMod coeff (XInf var) -> Poly coeff var
Poly (FreeMod c (XInf v) -> Poly c v)
-> (Poly Integer v -> FreeMod c (XInf v))
-> Poly Integer v
-> Poly c v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ZMod (XInf v) -> FreeMod c (XInf v)
forall c b.
(Num c, Typeable c, Eq c, Num c, Ord b, Typeable b) =>
ZMod b -> FreeMod c b
ZMod.fromZMod (ZMod (XInf v) -> FreeMod c (XInf v))
-> (Poly Integer v -> ZMod (XInf v))
-> Poly Integer v
-> FreeMod c (XInf v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Poly Integer v -> ZMod (XInf v)
forall c (v :: Symbol). Poly c v -> FreeMod c (XInf v)
unPoly

-- | Change the coefficient field (from rationals)
fromQPoly :: (Field c, KnownSymbol v) => Poly Rational v -> Poly c v 
fromQPoly :: Poly Rational v -> Poly c v
fromQPoly = FreeMod c (XInf v) -> Poly c v
forall coeff (var :: Symbol).
FreeMod coeff (XInf var) -> Poly coeff var
Poly (FreeMod c (XInf v) -> Poly c v)
-> (Poly Rational v -> FreeMod c (XInf v))
-> Poly Rational v
-> Poly c v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. QMod (XInf v) -> FreeMod c (XInf v)
forall c b.
(Fractional c, Typeable c, Eq c, Num c, Ord b, Typeable b) =>
QMod b -> FreeMod c b
ZMod.fromQMod (QMod (XInf v) -> FreeMod c (XInf v))
-> (Poly Rational v -> QMod (XInf v))
-> Poly Rational v
-> FreeMod c (XInf v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Poly Rational v -> QMod (XInf v)
forall c (v :: Symbol). Poly c v -> FreeMod c (XInf v)
unPoly

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

instance (Ring c, KnownSymbol v) => AlmostPolynomial (Poly c v) where
  type CoeffP (Poly c v) = c
  type MonomP (Poly c v) = XInf v
  type VarP   (Poly c v) = Index

  zeroP :: Poly c v
zeroP         = FreeMod c (XInf v) -> Poly c v
forall coeff (var :: Symbol).
FreeMod coeff (XInf var) -> Poly coeff var
Poly FreeMod c (XInf v)
forall c b. FreeMod c b
ZMod.zero
  isZeroP :: Poly c v -> Bool
isZeroP       = FreeMod c (XInf v) -> Bool
forall b c. Ord b => FreeMod c b -> Bool
ZMod.isZero (FreeMod c (XInf v) -> Bool)
-> (Poly c v -> FreeMod c (XInf v)) -> Poly c v -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Poly c v -> FreeMod c (XInf v)
forall c (v :: Symbol). Poly c v -> FreeMod c (XInf v)
unPoly
  oneP :: Poly c v
oneP          = FreeMod c (XInf v) -> Poly c v
forall coeff (var :: Symbol).
FreeMod coeff (XInf var) -> Poly coeff var
Poly (XInf v -> FreeMod c (XInf v)
forall c b. Num c => b -> FreeMod c b
ZMod.generator XInf v
forall m. Monomial m => m
emptyM)

  fromListP :: [(MonomP (Poly c v), CoeffP (Poly c v))] -> Poly c v
fromListP     = FreeMod c (XInf v) -> Poly c v
forall coeff (var :: Symbol).
FreeMod coeff (XInf var) -> Poly coeff var
Poly (FreeMod c (XInf v) -> Poly c v)
-> ([(XInf v, c)] -> FreeMod c (XInf v))
-> [(XInf v, c)]
-> Poly c v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(XInf v, c)] -> FreeMod c (XInf v)
forall c b. (Eq c, Num c, Ord b) => [(b, c)] -> FreeMod c b
ZMod.fromList
  toListP :: Poly c v -> [(MonomP (Poly c v), CoeffP (Poly c v))]
toListP       = FreeMod c (XInf v) -> [(XInf v, c)]
forall c b. FreeMod c b -> [(b, c)]
ZMod.toList (FreeMod c (XInf v) -> [(XInf v, c)])
-> (Poly c v -> FreeMod c (XInf v)) -> Poly c v -> [(XInf v, c)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Poly c v -> FreeMod c (XInf v)
forall c (v :: Symbol). Poly c v -> FreeMod c (XInf v)
unPoly

  variableP :: VarP (Poly c v) -> Poly c v
variableP     = FreeMod c (XInf v) -> Poly c v
forall coeff (var :: Symbol).
FreeMod coeff (XInf var) -> Poly coeff var
Poly (FreeMod c (XInf v) -> Poly c v)
-> (Index -> FreeMod c (XInf v)) -> Index -> Poly c v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. XInf v -> FreeMod c (XInf v)
forall c b. Num c => b -> FreeMod c b
ZMod.generator (XInf v -> FreeMod c (XInf v))
-> (Index -> XInf v) -> Index -> FreeMod c (XInf v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Index -> XInf v
forall (v :: Symbol). Index -> XInf v
variableXInf
  singletonP :: VarP (Poly c v) -> Int -> Poly c v
singletonP    = \VarP (Poly c v)
v Int
e -> FreeMod c (XInf v) -> Poly c v
forall coeff (var :: Symbol).
FreeMod coeff (XInf var) -> Poly coeff var
Poly (XInf v -> FreeMod c (XInf v)
forall c b. Num c => b -> FreeMod c b
ZMod.generator (Index -> Int -> XInf v
forall (v :: Symbol). Index -> Int -> XInf v
singletonXInf VarP (Poly c v)
Index
v Int
e))
  monomP :: MonomP (Poly c v) -> Poly c v
monomP        = \MonomP (Poly c v)
m     -> FreeMod c (XInf v) -> Poly c v
forall coeff (var :: Symbol).
FreeMod coeff (XInf var) -> Poly coeff var
Poly (FreeMod c (XInf v) -> Poly c v) -> FreeMod c (XInf v) -> Poly c v
forall a b. (a -> b) -> a -> b
$ XInf v -> FreeMod c (XInf v)
forall c b. Num c => b -> FreeMod c b
ZMod.generator MonomP (Poly c v)
XInf v
m
  monomP' :: MonomP (Poly c v) -> CoeffP (Poly c v) -> Poly c v
monomP'       = \MonomP (Poly c v)
m CoeffP (Poly c v)
c   -> FreeMod c (XInf v) -> Poly c v
forall coeff (var :: Symbol).
FreeMod coeff (XInf var) -> Poly coeff var
Poly (FreeMod c (XInf v) -> Poly c v) -> FreeMod c (XInf v) -> Poly c v
forall a b. (a -> b) -> a -> b
$ XInf v -> c -> FreeMod c (XInf v)
forall b c. (Ord b, Num c, Eq c) => b -> c -> FreeMod c b
ZMod.singleton MonomP (Poly c v)
XInf v
m c
CoeffP (Poly c v)
c
  scalarP :: CoeffP (Poly c v) -> Poly c v
scalarP       = \CoeffP (Poly c v)
s     -> FreeMod c (XInf v) -> Poly c v
forall coeff (var :: Symbol).
FreeMod coeff (XInf var) -> Poly coeff var
Poly (FreeMod c (XInf v) -> Poly c v) -> FreeMod c (XInf v) -> Poly c v
forall a b. (a -> b) -> a -> b
$ XInf v -> c -> FreeMod c (XInf v)
forall b c. (Ord b, Num c, Eq c) => b -> c -> FreeMod c b
ZMod.singleton XInf v
forall (v :: Symbol). XInf v
emptyXInf c
CoeffP (Poly c v)
s

  addP :: Poly c v -> Poly c v -> Poly c v
addP          = \Poly c v
p1 Poly c v
p2 -> FreeMod c (XInf v) -> Poly c v
forall coeff (var :: Symbol).
FreeMod coeff (XInf var) -> Poly coeff var
Poly (FreeMod c (XInf v) -> Poly c v) -> FreeMod c (XInf v) -> Poly c v
forall a b. (a -> b) -> a -> b
$ FreeMod c (XInf v) -> FreeMod c (XInf v) -> FreeMod c (XInf v)
forall b c.
(Ord b, Eq c, Num c) =>
FreeMod c b -> FreeMod c b -> FreeMod c b
ZMod.add (Poly c v -> FreeMod c (XInf v)
forall c (v :: Symbol). Poly c v -> FreeMod c (XInf v)
unPoly Poly c v
p1) (Poly c v -> FreeMod c (XInf v)
forall c (v :: Symbol). Poly c v -> FreeMod c (XInf v)
unPoly Poly c v
p2)
  subP :: Poly c v -> Poly c v -> Poly c v
subP          = \Poly c v
p1 Poly c v
p2 -> FreeMod c (XInf v) -> Poly c v
forall coeff (var :: Symbol).
FreeMod coeff (XInf var) -> Poly coeff var
Poly (FreeMod c (XInf v) -> Poly c v) -> FreeMod c (XInf v) -> Poly c v
forall a b. (a -> b) -> a -> b
$ FreeMod c (XInf v) -> FreeMod c (XInf v) -> FreeMod c (XInf v)
forall b c.
(Ord b, Eq c, Num c) =>
FreeMod c b -> FreeMod c b -> FreeMod c b
ZMod.sub (Poly c v -> FreeMod c (XInf v)
forall c (v :: Symbol). Poly c v -> FreeMod c (XInf v)
unPoly Poly c v
p1) (Poly c v -> FreeMod c (XInf v)
forall c (v :: Symbol). Poly c v -> FreeMod c (XInf v)
unPoly Poly c v
p2)
  negP :: Poly c v -> Poly c v
negP          = FreeMod c (XInf v) -> Poly c v
forall coeff (var :: Symbol).
FreeMod coeff (XInf var) -> Poly coeff var
Poly (FreeMod c (XInf v) -> Poly c v)
-> (Poly c v -> FreeMod c (XInf v)) -> Poly c v -> Poly c v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FreeMod c (XInf v) -> FreeMod c (XInf v)
forall c b. Num c => FreeMod c b -> FreeMod c b
ZMod.neg (FreeMod c (XInf v) -> FreeMod c (XInf v))
-> (Poly c v -> FreeMod c (XInf v))
-> Poly c v
-> FreeMod c (XInf v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Poly c v -> FreeMod c (XInf v)
forall c (v :: Symbol). Poly c v -> FreeMod c (XInf v)
unPoly
  mulP :: Poly c v -> Poly c v -> Poly c v
mulP          = \Poly c v
p1 Poly c v
p2 -> FreeMod c (XInf v) -> Poly c v
forall coeff (var :: Symbol).
FreeMod coeff (XInf var) -> Poly coeff var
Poly (FreeMod c (XInf v) -> Poly c v) -> FreeMod c (XInf v) -> Poly c v
forall a b. (a -> b) -> a -> b
$ (XInf v -> XInf v -> XInf v)
-> FreeMod c (XInf v) -> FreeMod c (XInf v) -> FreeMod c (XInf v)
forall b c.
(Ord b, Eq c, Num c) =>
(b -> b -> b) -> FreeMod c b -> FreeMod c b -> FreeMod c b
ZMod.mulWith     XInf v -> XInf v -> XInf v
forall (v :: Symbol). XInf v -> XInf v -> XInf v
mulXInf (Poly c v -> FreeMod c (XInf v)
forall c (v :: Symbol). Poly c v -> FreeMod c (XInf v)
unPoly Poly c v
p1) (Poly c v -> FreeMod c (XInf v)
forall c (v :: Symbol). Poly c v -> FreeMod c (XInf v)
unPoly Poly c v
p2)

  coeffOfP :: MonomP (Poly c v) -> Poly c v -> CoeffP (Poly c v)
coeffOfP      = \MonomP (Poly c v)
m Poly c v
p   -> XInf v -> FreeMod c (XInf v) -> c
forall b c. (Ord b, Num c) => b -> FreeMod c b -> c
ZMod.coeffOf MonomP (Poly c v)
XInf v
m (Poly c v -> FreeMod c (XInf v)
forall c (v :: Symbol). Poly c v -> FreeMod c (XInf v)
unPoly Poly c v
p)
  productP :: [Poly c v] -> Poly c v
productP      = \[Poly c v]
ps    -> FreeMod c (XInf v) -> Poly c v
forall coeff (var :: Symbol).
FreeMod coeff (XInf var) -> Poly coeff var
Poly (FreeMod c (XInf v) -> Poly c v) -> FreeMod c (XInf v) -> Poly c v
forall a b. (a -> b) -> a -> b
$ XInf v
-> (XInf v -> XInf v -> XInf v)
-> [FreeMod c (XInf v)]
-> FreeMod c (XInf v)
forall b c.
(Ord b, Eq c, Num c) =>
b -> (b -> b -> b) -> [FreeMod c b] -> FreeMod c b
ZMod.productWith XInf v
forall (v :: Symbol). XInf v
emptyXInf XInf v -> XInf v -> XInf v
forall (v :: Symbol). XInf v -> XInf v -> XInf v
mulXInf ([FreeMod c (XInf v)] -> FreeMod c (XInf v))
-> [FreeMod c (XInf v)] -> FreeMod c (XInf v)
forall a b. (a -> b) -> a -> b
$ (Poly c v -> FreeMod c (XInf v))
-> [Poly c v] -> [FreeMod c (XInf v)]
forall a b. (a -> b) -> [a] -> [b]
map Poly c v -> FreeMod c (XInf v)
forall c (v :: Symbol). Poly c v -> FreeMod c (XInf v)
unPoly [Poly c v]
ps
  mulByMonomP :: MonomP (Poly c v) -> Poly c v -> Poly c v
mulByMonomP   = \MonomP (Poly c v)
m Poly c v
p   -> FreeMod c (XInf v) -> Poly c v
forall coeff (var :: Symbol).
FreeMod coeff (XInf var) -> Poly coeff var
Poly (FreeMod c (XInf v) -> Poly c v) -> FreeMod c (XInf v) -> Poly c v
forall a b. (a -> b) -> a -> b
$ XInf v -> FreeMod c (XInf v) -> FreeMod c (XInf v)
forall c b.
(Eq c, Num c, Ord b, Monoid b) =>
b -> FreeMod c b -> FreeMod c b
ZMod.mulByMonom  MonomP (Poly c v)
XInf v
m (Poly c v -> FreeMod c (XInf v)
forall c (v :: Symbol). Poly c v -> FreeMod c (XInf v)
unPoly Poly c v
p)
  scaleP :: CoeffP (Poly c v) -> Poly c v -> Poly c v
scaleP        = \CoeffP (Poly c v)
s Poly c v
p   -> FreeMod c (XInf v) -> Poly c v
forall coeff (var :: Symbol).
FreeMod coeff (XInf var) -> Poly coeff var
Poly (FreeMod c (XInf v) -> Poly c v) -> FreeMod c (XInf v) -> Poly c v
forall a b. (a -> b) -> a -> b
$ c -> FreeMod c (XInf v) -> FreeMod c (XInf v)
forall b c. (Ord b, Eq c, Num c) => c -> FreeMod c b -> FreeMod c b
ZMod.scale c
CoeffP (Poly c v)
s (Poly c v -> FreeMod c (XInf v)
forall c (v :: Symbol). Poly c v -> FreeMod c (XInf v)
unPoly Poly c v
p) 

instance (Ring c, KnownSymbol v) => Polynomial (Poly c v) where
  evalP :: (CoeffP (Poly c v) -> d) -> (VarP (Poly c v) -> d) -> Poly c v -> d
evalP         = \CoeffP (Poly c v) -> d
g VarP (Poly c v) -> d
f Poly c v
p -> let { !z :: XInf v -> d
z = (VarM (XInf v) -> d) -> XInf v -> d
forall m c. (Monomial m, Num c) => (VarM m -> c) -> m -> c
evalM VarP (Poly c v) -> d
VarM (XInf v) -> d
f ; h :: (XInf v, c) -> d
h (!XInf v
m,!c
c) = CoeffP (Poly c v) -> d
g c
CoeffP (Poly c v)
c d -> d -> d
forall a. Num a => a -> a -> a
* XInf v -> d
z XInf v
m } in [d] -> d
forall a. Num a => [a] -> a
sum' ([d] -> d) -> [d] -> d
forall a b. (a -> b) -> a -> b
$ ((XInf v, c) -> d) -> [(XInf v, c)] -> [d]
forall a b. (a -> b) -> [a] -> [b]
map (XInf v, c) -> d
h ([(XInf v, c)] -> [d]) -> [(XInf v, c)] -> [d]
forall a b. (a -> b) -> a -> b
$ FreeMod c (XInf v) -> [(XInf v, c)]
forall c b. FreeMod c b -> [(b, c)]
ZMod.toList (FreeMod c (XInf v) -> [(XInf v, c)])
-> FreeMod c (XInf v) -> [(XInf v, c)]
forall a b. (a -> b) -> a -> b
$ Poly c v -> FreeMod c (XInf v)
forall c (v :: Symbol). Poly c v -> FreeMod c (XInf v)
unPoly Poly c v
p
  varSubsP :: (VarP (Poly c v) -> VarP (Poly c v)) -> Poly c v -> Poly c v
varSubsP      = \VarP (Poly c v) -> VarP (Poly c v)
f Poly c v
p   -> FreeMod c (XInf v) -> Poly c v
forall coeff (var :: Symbol).
FreeMod coeff (XInf var) -> Poly coeff var
Poly (FreeMod c (XInf v) -> Poly c v) -> FreeMod c (XInf v) -> Poly c v
forall a b. (a -> b) -> a -> b
$ (XInf v -> XInf v) -> FreeMod c (XInf v) -> FreeMod c (XInf v)
forall a b c.
(Ord a, Ord b, Eq c, Num c) =>
(a -> b) -> FreeMod c a -> FreeMod c b
ZMod.mapBase ((VarM (XInf v) -> VarM (XInf v)) -> XInf v -> XInf v
forall m. Monomial m => (VarM m -> VarM m) -> m -> m
varSubsM VarP (Poly c v) -> VarP (Poly c v)
VarM (XInf v) -> VarM (XInf v)
f) (Poly c v -> FreeMod c (XInf v)
forall c (v :: Symbol). Poly c v -> FreeMod c (XInf v)
unPoly Poly c v
p)
  coeffSubsP :: (VarP (Poly c v) -> Maybe (CoeffP (Poly c v)))
-> Poly c v -> Poly c v
coeffSubsP    = \VarP (Poly c v) -> Maybe (CoeffP (Poly c v))
f Poly c v
p   -> FreeMod c (XInf v) -> Poly c v
forall coeff (var :: Symbol).
FreeMod coeff (XInf var) -> Poly coeff var
Poly (FreeMod c (XInf v) -> Poly c v) -> FreeMod c (XInf v) -> Poly c v
forall a b. (a -> b) -> a -> b
$ [(XInf v, c)] -> FreeMod c (XInf v)
forall c b. (Eq c, Num c, Ord b) => [(b, c)] -> FreeMod c b
ZMod.fromList ([(XInf v, c)] -> FreeMod c (XInf v))
-> [(XInf v, c)] -> FreeMod c (XInf v)
forall a b. (a -> b) -> a -> b
$ ((XInf v, c) -> (XInf v, c)) -> [(XInf v, c)] -> [(XInf v, c)]
forall a b. (a -> b) -> [a] -> [b]
map ((VarM (XInf v) -> Maybe c) -> (XInf v, c) -> (XInf v, c)
forall m c.
(Monomial m, Num c) =>
(VarM m -> Maybe c) -> (m, c) -> (m, c)
termSubsM VarP (Poly c v) -> Maybe (CoeffP (Poly c v))
VarM (XInf v) -> Maybe c
f) ([(XInf v, c)] -> [(XInf v, c)]) -> [(XInf v, c)] -> [(XInf v, c)]
forall a b. (a -> b) -> a -> b
$ FreeMod c (XInf v) -> [(XInf v, c)]
forall c b. FreeMod c b -> [(b, c)]
ZMod.toList (FreeMod c (XInf v) -> [(XInf v, c)])
-> FreeMod c (XInf v) -> [(XInf v, c)]
forall a b. (a -> b) -> a -> b
$ Poly c v -> FreeMod c (XInf v)
forall c (v :: Symbol). Poly c v -> FreeMod c (XInf v)
unPoly Poly c v
p 
  subsP :: (VarP (Poly c v) -> Poly c v) -> Poly c v -> Poly c v
subsP         = \VarP (Poly c v) -> Poly c v
f Poly c v
p   -> FreeMod c (XInf v) -> Poly c v
forall coeff (var :: Symbol).
FreeMod coeff (XInf var) -> Poly coeff var
Poly (FreeMod c (XInf v) -> Poly c v) -> FreeMod c (XInf v) -> Poly c v
forall a b. (a -> b) -> a -> b
$ (XInf v -> FreeMod c (XInf v))
-> FreeMod c (XInf v) -> FreeMod c (XInf v)
forall b1 b2 c.
(Ord b1, Ord b2, Eq c, Num c) =>
(b1 -> FreeMod c b2) -> FreeMod c b1 -> FreeMod c b2
ZMod.flatMap ((VarM (XInf v) -> FreeMod c (XInf v))
-> XInf v -> FreeMod c (XInf v)
forall m c. (Monomial m, Num c) => (VarM m -> c) -> m -> c
evalM (Poly c v -> FreeMod c (XInf v)
forall c (v :: Symbol). Poly c v -> FreeMod c (XInf v)
unPoly (Poly c v -> FreeMod c (XInf v))
-> (Index -> Poly c v) -> Index -> FreeMod c (XInf v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. VarP (Poly c v) -> Poly c v
Index -> Poly c v
f)) (Poly c v -> FreeMod c (XInf v)
forall c (v :: Symbol). Poly c v -> FreeMod c (XInf v)
unPoly Poly c v
p)

instance (Ring c, KnownSymbol v) => Num (Poly c v) where
  fromInteger :: Integer -> Poly c v
fromInteger = c -> Poly c v
forall p. AlmostPolynomial p => CoeffP p -> p
scalarP (c -> Poly c v) -> (Integer -> c) -> Integer -> Poly c v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Integer -> c
forall a. Num a => Integer -> a
fromInteger
  + :: Poly c v -> Poly c v -> Poly c v
(+)    = Poly c v -> Poly c v -> Poly c v
forall p. AlmostPolynomial p => p -> p -> p
addP
  (-)    = Poly c v -> Poly c v -> Poly c v
forall p. AlmostPolynomial p => p -> p -> p
subP
  negate :: Poly c v -> Poly c v
negate = Poly c v -> Poly c v
forall p. AlmostPolynomial p => p -> p
negP
  * :: Poly c v -> Poly c v -> Poly c v
(*)    = Poly c v -> Poly c v -> Poly c v
forall p. AlmostPolynomial p => p -> p -> p
mulP
  abs :: Poly c v -> Poly c v
abs    = Poly c v -> Poly c v
forall a. a -> a
id
  signum :: Poly c v -> Poly c v
signum = \Poly c v
_ -> CoeffP (Poly c v) -> Poly c v
forall p. AlmostPolynomial p => CoeffP p -> p
scalarP CoeffP (Poly c v)
1

instance (Ring c, KnownSymbol v, Pretty (XInf v)) => Pretty (Poly c v) where
  pretty :: Poly c v -> String
pretty poly :: Poly c v
poly@(Poly FreeMod c (XInf v)
fm) = if Proxy c -> Bool
forall c. Ring c => Proxy c -> Bool
isSignedR (Poly c v -> Proxy (CoeffP (Poly c v))
forall p. AlmostPolynomial p => p -> Proxy (CoeffP p)
proxyCoeffP Poly c v
poly)
    then Bool -> (XInf v -> String) -> FreeMod c (XInf v) -> String
forall c b.
(Num c, Eq c, IsSigned c, Pretty c) =>
Bool -> (b -> String) -> FreeMod c b -> String
prettyFreeMod'  Bool
True   XInf v -> String
forall a. Pretty a => a -> String
pretty FreeMod c (XInf v)
fm
    else (c -> String) -> (XInf v -> String) -> FreeMod c (XInf v) -> String
forall c b. (c -> String) -> (b -> String) -> FreeMod c b -> String
prettyFreeMod'' c -> String
forall a. Pretty a => a -> String
pretty XInf v -> String
forall a. Pretty a => a -> String
pretty FreeMod c (XInf v)
fm

-- hackety hack hack...
instance IsSigned (Poly c v) where
  signOf :: Poly c v -> Maybe Sign
signOf = Maybe Sign -> Poly c v -> Maybe Sign
forall a b. a -> b -> a
const (Sign -> Maybe Sign
forall a. a -> Maybe a
Just Sign
Plus)

-- So that we can use it again as a coefficient ring
instance (Ring c, KnownSymbol v) => Ring (Poly c v) where
  isZeroR :: Poly c v -> Bool
isZeroR   = FreeMod c (XInf v) -> Bool
forall b c. Ord b => FreeMod c b -> Bool
ZMod.isZero (FreeMod c (XInf v) -> Bool)
-> (Poly c v -> FreeMod c (XInf v)) -> Poly c v -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Poly c v -> FreeMod c (XInf v)
forall c (v :: Symbol). Poly c v -> FreeMod c (XInf v)
unPoly
  isAtomicR :: Proxy (Poly c v) -> Bool
isAtomicR = Bool -> Proxy (Poly c v) -> Bool
forall a b. a -> b -> a
const Bool
False
  isSignedR :: Proxy (Poly c v) -> Bool
isSignedR = Bool -> Proxy (Poly c v) -> Bool
forall a b. a -> b -> a
const Bool
False
  absR :: Poly c v -> Poly c v
absR      = Poly c v -> Poly c v
forall a. a -> a
id
  signumR :: Poly c v -> Maybe Sign
signumR   = Maybe Sign -> Poly c v -> Maybe Sign
forall a b. a -> b -> a
const (Sign -> Maybe Sign
forall a. a -> Maybe a
Just Sign
Plus)

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

-- | We can always truncate to a given number of variables, simply 
-- by substituting zero to the rest
truncate :: (Eq c, Num c, KnownNat n) => Poly c v -> Fin.Poly c v n
truncate :: Poly c v -> Poly c v n
truncate input :: Poly c v
input@(Poly FreeMod c (XInf v)
inpoly) = Poly c v n
output where
  n :: Int
n = Poly c v n -> Int
forall (n :: Nat) c (var :: Symbol).
KnownNat n =>
Poly c var n -> Int
Fin.nOfPoly Poly c v n
output
  output :: Poly c v n
output = FreeMod c (XS v n) -> Poly c v n
forall coeff (var :: Symbol) (n :: Nat).
FreeMod coeff (XS var n) -> Poly coeff var n
Fin.Poly (FreeMod c (XS v n) -> Poly c v n)
-> FreeMod c (XS v n) -> Poly c v n
forall a b. (a -> b) -> a -> b
$ (XInf v -> Maybe (XS v n))
-> FreeMod c (XInf v) -> FreeMod c (XS v n)
forall a b c.
(Ord a, Ord b, Eq c, Num c) =>
(a -> Maybe b) -> FreeMod c a -> FreeMod c b
ZMod.mapMaybeBase XInf v -> Maybe (XS v n)
f FreeMod c (XInf v)
inpoly
  f :: XInf v -> Maybe (XS v n)
f (XInf [Int]
es) =
      let ([Int]
fs,[Int]
rest) = Int -> [Int] -> ([Int], [Int])
forall a. Int -> [a] -> ([a], [a])
splitAt Int
n [Int]
es
      in  if (Int -> Bool) -> [Int] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all (Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
==Int
0) [Int]
rest 
            then XS v n -> Maybe (XS v n)
forall a. a -> Maybe a
Just ([Int] -> XS v n
forall (n :: Nat) (v :: Symbol). KnownNat n => [Int] -> XS v n
Fin.xsFromExponents [Int]
fs) 
            else Maybe (XS v n)
forall a. Maybe a
Nothing 

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