-- | Multivariate polynomial algebra where the set of variables is given by 
-- the inhabitants of a type

{-# LANGUAGE BangPatterns, TypeFamilies, KindSignatures, StandaloneDeriving, FlexibleContexts #-}
module Math.Algebra.Polynomial.Multivariate.Generic where

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

import Data.Maybe
import Data.List
import Data.Foldable as F

import Data.Proxy
import Data.Typeable

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

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

import Math.Algebra.Polynomial.Monomial.Generic 

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

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

newtype Poly (coeff :: *) (var :: *)
  = Poly (FreeMod coeff (Monom 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.
(Eq var, Eq coeff) =>
Poly coeff var -> Poly coeff var -> Bool
/= :: Poly coeff var -> Poly coeff var -> Bool
$c/= :: forall coeff var.
(Eq var, Eq coeff) =>
Poly coeff var -> Poly coeff var -> Bool
== :: Poly coeff var -> Poly coeff var -> Bool
$c== :: forall coeff var.
(Eq var, 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. (Ord var, Ord coeff) => Eq (Poly coeff var)
forall coeff var.
(Ord var, Ord coeff) =>
Poly coeff var -> Poly coeff var -> Bool
forall coeff var.
(Ord var, Ord coeff) =>
Poly coeff var -> Poly coeff var -> Ordering
forall coeff var.
(Ord var, 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.
(Ord var, 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.
(Ord var, Ord coeff) =>
Poly coeff var -> Poly coeff var -> Poly coeff var
>= :: Poly coeff var -> Poly coeff var -> Bool
$c>= :: forall coeff var.
(Ord var, Ord coeff) =>
Poly coeff var -> Poly coeff var -> Bool
> :: Poly coeff var -> Poly coeff var -> Bool
$c> :: forall coeff var.
(Ord var, Ord coeff) =>
Poly coeff var -> Poly coeff var -> Bool
<= :: Poly coeff var -> Poly coeff var -> Bool
$c<= :: forall coeff var.
(Ord var, Ord coeff) =>
Poly coeff var -> Poly coeff var -> Bool
< :: Poly coeff var -> Poly coeff var -> Bool
$c< :: forall coeff var.
(Ord var, Ord coeff) =>
Poly coeff var -> Poly coeff var -> Bool
compare :: Poly coeff var -> Poly coeff var -> Ordering
$ccompare :: forall coeff var.
(Ord var, Ord coeff) =>
Poly coeff var -> Poly coeff var -> Ordering
$cp1Ord :: forall coeff var. (Ord var, 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.
(Show var, Show coeff) =>
Int -> Poly coeff var -> ShowS
forall coeff var.
(Show var, Show coeff) =>
[Poly coeff var] -> ShowS
forall coeff var.
(Show var, Show coeff) =>
Poly coeff var -> String
showList :: [Poly coeff var] -> ShowS
$cshowList :: forall coeff var.
(Show var, Show coeff) =>
[Poly coeff var] -> ShowS
show :: Poly coeff var -> String
$cshow :: forall coeff var.
(Show var, Show coeff) =>
Poly coeff var -> String
showsPrec :: Int -> Poly coeff var -> ShowS
$cshowsPrec :: forall coeff var.
(Show var, Show coeff) =>
Int -> Poly coeff var -> ShowS
Show,Typeable)

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

instance Ord v => FreeModule (Poly c v) where
  type BaseF  (Poly c v) = Monom 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. Poly c v -> FreeMod c (Monom 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. FreeMod coeff (Monom var) -> Poly coeff var
Poly

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

type ZPoly = Poly Integer
type QPoly = Poly Rational

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

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

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

instance (Ring c, Ord v, Pretty v) => AlmostPolynomial (Poly c v) where
  type CoeffP (Poly c v) = c
  type MonomP (Poly c v) = Monom v
  type VarP   (Poly c v) = v

  fromListP :: [(MonomP (Poly c v), CoeffP (Poly c v))] -> Poly c v
fromListP     = FreeMod c (Monom v) -> Poly c v
forall coeff var. FreeMod coeff (Monom var) -> Poly coeff var
Poly (FreeMod c (Monom v) -> Poly c v)
-> ([(Monom v, c)] -> FreeMod c (Monom v))
-> [(Monom v, c)]
-> Poly c v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(Monom v, c)] -> FreeMod c (Monom 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 (Monom v) -> [(Monom v, c)]
forall c b. FreeMod c b -> [(b, c)]
ZMod.toList (FreeMod c (Monom v) -> [(Monom v, c)])
-> (Poly c v -> FreeMod c (Monom v)) -> Poly c v -> [(Monom v, c)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Poly c v -> FreeMod c (Monom v)
forall c v. Poly c v -> FreeMod c (Monom v)
unPoly

  zeroP :: Poly c v
zeroP         = FreeMod c (Monom v) -> Poly c v
forall coeff var. FreeMod coeff (Monom var) -> Poly coeff var
Poly FreeMod c (Monom v)
forall c b. FreeMod c b
ZMod.zero
  isZeroP :: Poly c v -> Bool
isZeroP       = FreeMod c (Monom v) -> Bool
forall b c. Ord b => FreeMod c b -> Bool
ZMod.isZero (FreeMod c (Monom v) -> Bool)
-> (Poly c v -> FreeMod c (Monom v)) -> Poly c v -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Poly c v -> FreeMod c (Monom v)
forall c v. Poly c v -> FreeMod c (Monom v)
unPoly
  oneP :: Poly c v
oneP          = FreeMod c (Monom v) -> Poly c v
forall coeff var. FreeMod coeff (Monom var) -> Poly coeff var
Poly (Monom v -> FreeMod c (Monom v)
forall c b. Num c => b -> FreeMod c b
ZMod.generator Monom v
forall v. Monom v
emptyMonom)

  variableP :: VarP (Poly c v) -> Poly c v
variableP     = FreeMod c (Monom v) -> Poly c v
forall coeff var. FreeMod coeff (Monom var) -> Poly coeff var
Poly (FreeMod c (Monom v) -> Poly c v)
-> (v -> FreeMod c (Monom v)) -> v -> Poly c v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Monom v -> FreeMod c (Monom v)
forall c b. Num c => b -> FreeMod c b
ZMod.generator (Monom v -> FreeMod c (Monom v))
-> (v -> Monom v) -> v -> FreeMod c (Monom v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. v -> Monom v
forall v. Ord v => v -> Monom v
varMonom
  singletonP :: VarP (Poly c v) -> Int -> Poly c v
singletonP    = \VarP (Poly c v)
v Int
e -> FreeMod c (Monom v) -> Poly c v
forall coeff var. FreeMod coeff (Monom var) -> Poly coeff var
Poly (Monom v -> FreeMod c (Monom v)
forall c b. Num c => b -> FreeMod c b
ZMod.generator (v -> Int -> Monom v
forall v. Ord v => v -> Int -> Monom v
singletonMonom v
VarP (Poly c v)
v Int
e))
  monomP :: MonomP (Poly c v) -> Poly c v
monomP        = \MonomP (Poly c v)
m     -> FreeMod c (Monom v) -> Poly c v
forall coeff var. FreeMod coeff (Monom var) -> Poly coeff var
Poly (FreeMod c (Monom v) -> Poly c v)
-> FreeMod c (Monom v) -> Poly c v
forall a b. (a -> b) -> a -> b
$ Monom v -> FreeMod c (Monom v)
forall c b. Num c => b -> FreeMod c b
ZMod.generator MonomP (Poly c v)
Monom 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 (Monom v) -> Poly c v
forall coeff var. FreeMod coeff (Monom var) -> Poly coeff var
Poly (FreeMod c (Monom v) -> Poly c v)
-> FreeMod c (Monom v) -> Poly c v
forall a b. (a -> b) -> a -> b
$ Monom v -> c -> FreeMod c (Monom v)
forall b c. (Ord b, Num c, Eq c) => b -> c -> FreeMod c b
ZMod.singleton MonomP (Poly c v)
Monom v
m c
CoeffP (Poly c v)
c
  scalarP :: CoeffP (Poly c v) -> Poly c v
scalarP       = \CoeffP (Poly c v)
s     -> FreeMod c (Monom v) -> Poly c v
forall coeff var. FreeMod coeff (Monom var) -> Poly coeff var
Poly (FreeMod c (Monom v) -> Poly c v)
-> FreeMod c (Monom v) -> Poly c v
forall a b. (a -> b) -> a -> b
$ Monom v -> c -> FreeMod c (Monom v)
forall b c. (Ord b, Num c, Eq c) => b -> c -> FreeMod c b
ZMod.singleton Monom v
forall v. Monom v
emptyMonom 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 (Monom v) -> Poly c v
forall coeff var. FreeMod coeff (Monom var) -> Poly coeff var
Poly (FreeMod c (Monom v) -> Poly c v)
-> FreeMod c (Monom v) -> Poly c v
forall a b. (a -> b) -> a -> b
$ FreeMod c (Monom v) -> FreeMod c (Monom v) -> FreeMod c (Monom 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 (Monom v)
forall c v. Poly c v -> FreeMod c (Monom v)
unPoly Poly c v
p1) (Poly c v -> FreeMod c (Monom v)
forall c v. Poly c v -> FreeMod c (Monom 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 (Monom v) -> Poly c v
forall coeff var. FreeMod coeff (Monom var) -> Poly coeff var
Poly (FreeMod c (Monom v) -> Poly c v)
-> FreeMod c (Monom v) -> Poly c v
forall a b. (a -> b) -> a -> b
$ FreeMod c (Monom v) -> FreeMod c (Monom v) -> FreeMod c (Monom 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 (Monom v)
forall c v. Poly c v -> FreeMod c (Monom v)
unPoly Poly c v
p1) (Poly c v -> FreeMod c (Monom v)
forall c v. Poly c v -> FreeMod c (Monom v)
unPoly Poly c v
p2)
  negP :: Poly c v -> Poly c v
negP          = FreeMod c (Monom v) -> Poly c v
forall coeff var. FreeMod coeff (Monom var) -> Poly coeff var
Poly (FreeMod c (Monom v) -> Poly c v)
-> (Poly c v -> FreeMod c (Monom v)) -> Poly c v -> Poly c v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FreeMod c (Monom v) -> FreeMod c (Monom v)
forall c b. Num c => FreeMod c b -> FreeMod c b
ZMod.neg (FreeMod c (Monom v) -> FreeMod c (Monom v))
-> (Poly c v -> FreeMod c (Monom v))
-> Poly c v
-> FreeMod c (Monom v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Poly c v -> FreeMod c (Monom v)
forall c v. Poly c v -> FreeMod c (Monom v)
unPoly
  mulP :: Poly c v -> Poly c v -> Poly c v
mulP          = \Poly c v
p1 Poly c v
p2 -> FreeMod c (Monom v) -> Poly c v
forall coeff var. FreeMod coeff (Monom var) -> Poly coeff var
Poly (FreeMod c (Monom v) -> Poly c v)
-> FreeMod c (Monom v) -> Poly c v
forall a b. (a -> b) -> a -> b
$ (Monom v -> Monom v -> Monom v)
-> FreeMod c (Monom v)
-> FreeMod c (Monom v)
-> FreeMod c (Monom v)
forall b c.
(Ord b, Eq c, Num c) =>
(b -> b -> b) -> FreeMod c b -> FreeMod c b -> FreeMod c b
ZMod.mulWith     Monom v -> Monom v -> Monom v
forall v. Ord v => Monom v -> Monom v -> Monom v
mulMonom (Poly c v -> FreeMod c (Monom v)
forall c v. Poly c v -> FreeMod c (Monom v)
unPoly Poly c v
p1) (Poly c v -> FreeMod c (Monom v)
forall c v. Poly c v -> FreeMod c (Monom v)
unPoly Poly c v
p2)
  productP :: [Poly c v] -> Poly c v
productP      = \[Poly c v]
ps    -> FreeMod c (Monom v) -> Poly c v
forall coeff var. FreeMod coeff (Monom var) -> Poly coeff var
Poly (FreeMod c (Monom v) -> Poly c v)
-> FreeMod c (Monom v) -> Poly c v
forall a b. (a -> b) -> a -> b
$ Monom v
-> (Monom v -> Monom v -> Monom v)
-> [FreeMod c (Monom v)]
-> FreeMod c (Monom v)
forall b c.
(Ord b, Eq c, Num c) =>
b -> (b -> b -> b) -> [FreeMod c b] -> FreeMod c b
ZMod.productWith Monom v
forall v. Monom v
emptyMonom Monom v -> Monom v -> Monom v
forall v. Ord v => Monom v -> Monom v -> Monom v
mulMonom ([FreeMod c (Monom v)] -> FreeMod c (Monom v))
-> [FreeMod c (Monom v)] -> FreeMod c (Monom v)
forall a b. (a -> b) -> a -> b
$ (Poly c v -> FreeMod c (Monom v))
-> [Poly c v] -> [FreeMod c (Monom v)]
forall a b. (a -> b) -> [a] -> [b]
map Poly c v -> FreeMod c (Monom v)
forall c v. Poly c v -> FreeMod c (Monom v)
unPoly [Poly c v]
ps

  coeffOfP :: MonomP (Poly c v) -> Poly c v -> CoeffP (Poly c v)
coeffOfP      = \MonomP (Poly c v)
m Poly c v
p   -> Monom v -> FreeMod c (Monom v) -> c
forall b c. (Ord b, Num c) => b -> FreeMod c b -> c
ZMod.coeffOf MonomP (Poly c v)
Monom v
m (Poly c v -> FreeMod c (Monom v)
forall c v. Poly c v -> FreeMod c (Monom v)
unPoly Poly c v
p)
  mulByMonomP :: MonomP (Poly c v) -> Poly c v -> Poly c v
mulByMonomP   = \MonomP (Poly c v)
m Poly c v
p   -> FreeMod c (Monom v) -> Poly c v
forall coeff var. FreeMod coeff (Monom var) -> Poly coeff var
Poly (FreeMod c (Monom v) -> Poly c v)
-> FreeMod c (Monom v) -> Poly c v
forall a b. (a -> b) -> a -> b
$ Monom v -> FreeMod c (Monom v) -> FreeMod c (Monom v)
forall b c. (Ord b, Monoid b) => b -> FreeMod c b -> FreeMod c b
ZMod.unsafeMulByMonom MonomP (Poly c v)
Monom v
m (Poly c v -> FreeMod c (Monom v)
forall c v. Poly c v -> FreeMod c (Monom 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 (Monom v) -> Poly c v
forall coeff var. FreeMod coeff (Monom var) -> Poly coeff var
Poly (FreeMod c (Monom v) -> Poly c v)
-> FreeMod c (Monom v) -> Poly c v
forall a b. (a -> b) -> a -> b
$ c -> FreeMod c (Monom v) -> FreeMod c (Monom 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 (Monom v)
forall c v. Poly c v -> FreeMod c (Monom v)
unPoly Poly c v
p) 

instance (Ring c, Ord v, Pretty 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 :: Monom v -> d
z = (VarM (Monom v) -> d) -> Monom v -> d
forall m c. (Monomial m, Num c) => (VarM m -> c) -> m -> c
evalM VarP (Poly c v) -> d
VarM (Monom v) -> d
f ; h :: (Monom v, c) -> d
h (!Monom 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
* Monom v -> d
z Monom v
m } in [d] -> d
forall a. Num a => [a] -> a
sum' ([d] -> d) -> [d] -> d
forall a b. (a -> b) -> a -> b
$ ((Monom v, c) -> d) -> [(Monom v, c)] -> [d]
forall a b. (a -> b) -> [a] -> [b]
map (Monom v, c) -> d
h ([(Monom v, c)] -> [d]) -> [(Monom v, c)] -> [d]
forall a b. (a -> b) -> a -> b
$ FreeMod c (Monom v) -> [(Monom v, c)]
forall c b. FreeMod c b -> [(b, c)]
ZMod.toList (FreeMod c (Monom v) -> [(Monom v, c)])
-> FreeMod c (Monom v) -> [(Monom v, c)]
forall a b. (a -> b) -> a -> b
$ Poly c v -> FreeMod c (Monom v)
forall c v. Poly c v -> FreeMod c (Monom 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 (Monom v) -> Poly c v
forall coeff var. FreeMod coeff (Monom var) -> Poly coeff var
Poly (FreeMod c (Monom v) -> Poly c v)
-> FreeMod c (Monom v) -> Poly c v
forall a b. (a -> b) -> a -> b
$ (Monom v -> Monom v) -> FreeMod c (Monom v) -> FreeMod c (Monom v)
forall a b c.
(Ord a, Ord b, Eq c, Num c) =>
(a -> b) -> FreeMod c a -> FreeMod c b
ZMod.mapBase ((v -> v) -> Monom v -> Monom v
forall v w. (Ord v, Ord w) => (v -> w) -> Monom v -> Monom w
mapMonom v -> v
VarP (Poly c v) -> VarP (Poly c v)
f) (Poly c v -> FreeMod c (Monom v)
forall c v. Poly c v -> FreeMod c (Monom 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 (Monom v) -> Poly c v
forall coeff var. FreeMod coeff (Monom var) -> Poly coeff var
Poly (FreeMod c (Monom v) -> Poly c v)
-> FreeMod c (Monom v) -> Poly c v
forall a b. (a -> b) -> a -> b
$ [(Monom v, c)] -> FreeMod c (Monom v)
forall c b. (Eq c, Num c, Ord b) => [(b, c)] -> FreeMod c b
ZMod.fromList ([(Monom v, c)] -> FreeMod c (Monom v))
-> [(Monom v, c)] -> FreeMod c (Monom v)
forall a b. (a -> b) -> a -> b
$ ((Monom v, c) -> (Monom v, c)) -> [(Monom v, c)] -> [(Monom v, c)]
forall a b. (a -> b) -> [a] -> [b]
map ((v -> Maybe c) -> (Monom v, c) -> (Monom v, c)
forall c v.
(Num c, Ord v) =>
(v -> Maybe c) -> (Monom v, c) -> (Monom v, c)
termSubsMonom v -> Maybe c
VarP (Poly c v) -> Maybe (CoeffP (Poly c v))
f) ([(Monom v, c)] -> [(Monom v, c)])
-> [(Monom v, c)] -> [(Monom v, c)]
forall a b. (a -> b) -> a -> b
$ FreeMod c (Monom v) -> [(Monom v, c)]
forall c b. FreeMod c b -> [(b, c)]
ZMod.toList (FreeMod c (Monom v) -> [(Monom v, c)])
-> FreeMod c (Monom v) -> [(Monom v, c)]
forall a b. (a -> b) -> a -> b
$ Poly c v -> FreeMod c (Monom v)
forall c v. Poly c v -> FreeMod c (Monom 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 (Monom v) -> Poly c v
forall coeff var. FreeMod coeff (Monom var) -> Poly coeff var
Poly (FreeMod c (Monom v) -> Poly c v)
-> FreeMod c (Monom v) -> Poly c v
forall a b. (a -> b) -> a -> b
$ (Monom v -> FreeMod c (Monom v))
-> FreeMod c (Monom v) -> FreeMod c (Monom 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 ((v -> FreeMod c (Monom v)) -> Monom v -> FreeMod c (Monom v)
forall c v. (Num c, Ord v) => (v -> c) -> Monom v -> c
evalMonom (Poly c v -> FreeMod c (Monom v)
forall c v. Poly c v -> FreeMod c (Monom v)
unPoly (Poly c v -> FreeMod c (Monom v))
-> (v -> Poly c v) -> v -> FreeMod c (Monom v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. v -> Poly c v
VarP (Poly c v) -> Poly c v
f)) (Poly c v -> FreeMod c (Monom v)
forall c v. Poly c v -> FreeMod c (Monom v)
unPoly Poly c v
p)

instance (Ring c, Ord v, Pretty 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, Ord v, Pretty v, Pretty (Monom v)) => Pretty (Poly c v) where
  pretty :: Poly c v -> String
pretty poly :: Poly c v
poly@(Poly FreeMod c (Monom 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 -> (Monom v -> String) -> FreeMod c (Monom v) -> String
forall c b.
(Num c, Eq c, IsSigned c, Pretty c) =>
Bool -> (b -> String) -> FreeMod c b -> String
prettyFreeMod'  Bool
True   Monom v -> String
forall a. Pretty a => a -> String
pretty FreeMod c (Monom v)
fm
    else (c -> String)
-> (Monom v -> String) -> FreeMod c (Monom v) -> String
forall c b. (c -> String) -> (b -> String) -> FreeMod c b -> String
prettyFreeMod'' c -> String
forall a. Pretty a => a -> String
pretty Monom v -> String
forall a. Pretty a => a -> String
pretty FreeMod c (Monom 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, Variable v) => Ring (Poly c v) where
  isZeroR :: Poly c v -> Bool
isZeroR   = FreeMod c (Monom v) -> Bool
forall b c. Ord b => FreeMod c b -> Bool
ZMod.isZero (FreeMod c (Monom v) -> Bool)
-> (Poly c v -> FreeMod c (Monom v)) -> Poly c v -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Poly c v -> FreeMod c (Monom v)
forall c v. Poly c v -> FreeMod c (Monom 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)

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