-- | Univariate polynomials

{-# LANGUAGE BangPatterns, DataKinds, KindSignatures, GeneralizedNewtypeDeriving, TypeFamilies #-}
module Math.Algebra.Polynomial.Univariate
  ( -- * Univariate polynomials
    Univariate(..) ,  U(..) , unUni , uniVar , renameUniVar
  , ZUni , QUni , fromZUni , fromQUni
  , differentiateUni , integrateUni , integrateUni'
  )
  where

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

import Data.Array ( Array , (!) , listArray , assocs ) 
import Data.List

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

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

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

import Math.Algebra.Polynomial.Monomial.Univariate

--------------------------------------------------------------------------------
-- * Univariate polynomials

-- | A univariate polynomial with the given coefficient ring. Note: this 
-- is also indexed by the /name/ of the variable.
newtype Univariate (coeff :: *) (var :: Symbol) = Uni (FreeMod coeff (U var))
  deriving (Univariate coeff var -> Univariate coeff var -> Bool
(Univariate coeff var -> Univariate coeff var -> Bool)
-> (Univariate coeff var -> Univariate coeff var -> Bool)
-> Eq (Univariate coeff var)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall coeff (var :: Symbol).
Eq coeff =>
Univariate coeff var -> Univariate coeff var -> Bool
/= :: Univariate coeff var -> Univariate coeff var -> Bool
$c/= :: forall coeff (var :: Symbol).
Eq coeff =>
Univariate coeff var -> Univariate coeff var -> Bool
== :: Univariate coeff var -> Univariate coeff var -> Bool
$c== :: forall coeff (var :: Symbol).
Eq coeff =>
Univariate coeff var -> Univariate coeff var -> Bool
Eq,Eq (Univariate coeff var)
Eq (Univariate coeff var)
-> (Univariate coeff var -> Univariate coeff var -> Ordering)
-> (Univariate coeff var -> Univariate coeff var -> Bool)
-> (Univariate coeff var -> Univariate coeff var -> Bool)
-> (Univariate coeff var -> Univariate coeff var -> Bool)
-> (Univariate coeff var -> Univariate coeff var -> Bool)
-> (Univariate coeff var
    -> Univariate coeff var -> Univariate coeff var)
-> (Univariate coeff var
    -> Univariate coeff var -> Univariate coeff var)
-> Ord (Univariate coeff var)
Univariate coeff var -> Univariate coeff var -> Bool
Univariate coeff var -> Univariate coeff var -> Ordering
Univariate coeff var
-> Univariate coeff var -> Univariate 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 (Univariate coeff var)
forall coeff (var :: Symbol).
Ord coeff =>
Univariate coeff var -> Univariate coeff var -> Bool
forall coeff (var :: Symbol).
Ord coeff =>
Univariate coeff var -> Univariate coeff var -> Ordering
forall coeff (var :: Symbol).
Ord coeff =>
Univariate coeff var
-> Univariate coeff var -> Univariate coeff var
min :: Univariate coeff var
-> Univariate coeff var -> Univariate coeff var
$cmin :: forall coeff (var :: Symbol).
Ord coeff =>
Univariate coeff var
-> Univariate coeff var -> Univariate coeff var
max :: Univariate coeff var
-> Univariate coeff var -> Univariate coeff var
$cmax :: forall coeff (var :: Symbol).
Ord coeff =>
Univariate coeff var
-> Univariate coeff var -> Univariate coeff var
>= :: Univariate coeff var -> Univariate coeff var -> Bool
$c>= :: forall coeff (var :: Symbol).
Ord coeff =>
Univariate coeff var -> Univariate coeff var -> Bool
> :: Univariate coeff var -> Univariate coeff var -> Bool
$c> :: forall coeff (var :: Symbol).
Ord coeff =>
Univariate coeff var -> Univariate coeff var -> Bool
<= :: Univariate coeff var -> Univariate coeff var -> Bool
$c<= :: forall coeff (var :: Symbol).
Ord coeff =>
Univariate coeff var -> Univariate coeff var -> Bool
< :: Univariate coeff var -> Univariate coeff var -> Bool
$c< :: forall coeff (var :: Symbol).
Ord coeff =>
Univariate coeff var -> Univariate coeff var -> Bool
compare :: Univariate coeff var -> Univariate coeff var -> Ordering
$ccompare :: forall coeff (var :: Symbol).
Ord coeff =>
Univariate coeff var -> Univariate coeff var -> Ordering
$cp1Ord :: forall coeff (var :: Symbol).
Ord coeff =>
Eq (Univariate coeff var)
Ord,Int -> Univariate coeff var -> ShowS
[Univariate coeff var] -> ShowS
Univariate coeff var -> String
(Int -> Univariate coeff var -> ShowS)
-> (Univariate coeff var -> String)
-> ([Univariate coeff var] -> ShowS)
-> Show (Univariate coeff var)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall coeff (var :: Symbol).
Show coeff =>
Int -> Univariate coeff var -> ShowS
forall coeff (var :: Symbol).
Show coeff =>
[Univariate coeff var] -> ShowS
forall coeff (var :: Symbol).
Show coeff =>
Univariate coeff var -> String
showList :: [Univariate coeff var] -> ShowS
$cshowList :: forall coeff (var :: Symbol).
Show coeff =>
[Univariate coeff var] -> ShowS
show :: Univariate coeff var -> String
$cshow :: forall coeff (var :: Symbol).
Show coeff =>
Univariate coeff var -> String
showsPrec :: Int -> Univariate coeff var -> ShowS
$cshowsPrec :: forall coeff (var :: Symbol).
Show coeff =>
Int -> Univariate coeff var -> ShowS
Show)

unUni :: Univariate c v -> FreeMod c (U v)
unUni :: Univariate c v -> FreeMod c (U v)
unUni (Uni FreeMod c (U v)
a) = FreeMod c (U v)
a

instance FreeModule (Univariate c v) where
  type BaseF  (Univariate c v) = U v 
  type CoeffF (Univariate c v) = c
  toFreeModule :: Univariate c v
-> FreeMod (CoeffF (Univariate c v)) (BaseF (Univariate c v))
toFreeModule   = Univariate c v
-> FreeMod (CoeffF (Univariate c v)) (BaseF (Univariate c v))
forall c (v :: Symbol). Univariate c v -> FreeMod c (U v)
unUni
  fromFreeModule :: FreeMod (CoeffF (Univariate c v)) (BaseF (Univariate c v))
-> Univariate c v
fromFreeModule = FreeMod (CoeffF (Univariate c v)) (BaseF (Univariate c v))
-> Univariate c v
forall coeff (var :: Symbol).
FreeMod coeff (U var) -> Univariate coeff var
Uni

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

-- | Rename the variable (zero cost)
renameUniVar :: Univariate c var1 -> Univariate c var2
renameUniVar :: Univariate c var1 -> Univariate c var2
renameUniVar = Univariate c var1 -> Univariate c var2
forall a b. a -> b
Unsafe.unsafeCoerce

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

-- | An univariate polynomial integer coefficients
type ZUni var = Univariate Integer var

-- | An univariate polynomial with rational coefficients
type QUni var = Univariate Rational var

-- | Change the coefficient ring
fromZUni :: (Ring c, KnownSymbol v) => Univariate Integer v -> Univariate c v 
fromZUni :: Univariate Integer v -> Univariate c v
fromZUni = FreeMod c (U v) -> Univariate c v
forall coeff (var :: Symbol).
FreeMod coeff (U var) -> Univariate coeff var
Uni (FreeMod c (U v) -> Univariate c v)
-> (Univariate Integer v -> FreeMod c (U v))
-> Univariate Integer v
-> Univariate c v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ZMod (U v) -> FreeMod c (U v)
forall c b.
(Num c, Typeable c, Eq c, Num c, Ord b, Typeable b) =>
ZMod b -> FreeMod c b
ZMod.fromZMod (ZMod (U v) -> FreeMod c (U v))
-> (Univariate Integer v -> ZMod (U v))
-> Univariate Integer v
-> FreeMod c (U v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Univariate Integer v -> ZMod (U v)
forall c (v :: Symbol). Univariate c v -> FreeMod c (U v)
unUni

-- | Change the coefficient ring
fromQUni :: (Field c, KnownSymbol v) => Univariate Rational v -> Univariate c v 
fromQUni :: Univariate Rational v -> Univariate c v
fromQUni = FreeMod c (U v) -> Univariate c v
forall coeff (var :: Symbol).
FreeMod coeff (U var) -> Univariate coeff var
Uni (FreeMod c (U v) -> Univariate c v)
-> (Univariate Rational v -> FreeMod c (U v))
-> Univariate Rational v
-> Univariate c v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. QMod (U v) -> FreeMod c (U v)
forall c b.
(Fractional c, Typeable c, Eq c, Num c, Ord b, Typeable b) =>
QMod b -> FreeMod c b
ZMod.fromQMod (QMod (U v) -> FreeMod c (U v))
-> (Univariate Rational v -> QMod (U v))
-> Univariate Rational v
-> FreeMod c (U v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Univariate Rational v -> QMod (U v)
forall c (v :: Symbol). Univariate c v -> FreeMod c (U v)
unUni

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

-- | Differentiation
differentiateUni :: (Ring c, KnownSymbol var) => Univariate c var -> Univariate c var
differentiateUni :: Univariate c var -> Univariate c var
differentiateUni = FreeMod c (U var) -> Univariate c var
forall coeff (var :: Symbol).
FreeMod coeff (U var) -> Univariate coeff var
Uni (FreeMod c (U var) -> Univariate c var)
-> (Univariate c var -> FreeMod c (U var))
-> Univariate c var
-> Univariate c var
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (U var -> Maybe (U var, c))
-> FreeMod c (U var) -> FreeMod c (U var)
forall a b c.
(Ord a, Ord b, Eq c, Num c) =>
(a -> Maybe (b, c)) -> FreeMod c a -> FreeMod c b
ZMod.mapMaybeBaseCoeff U var -> Maybe (U var, c)
forall b (var :: Symbol) (var :: Symbol).
Num b =>
U var -> Maybe (U var, b)
f (FreeMod c (U var) -> FreeMod c (U var))
-> (Univariate c var -> FreeMod c (U var))
-> Univariate c var
-> FreeMod c (U var)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Univariate c var -> FreeMod c (U var)
forall c (v :: Symbol). Univariate c v -> FreeMod c (U v)
unUni where
  f :: U var -> Maybe (U var, b)
f (U Int
k) = case Int
k of
    Int
0 -> Maybe (U var, b)
forall a. Maybe a
Nothing
    Int
_ -> (U var, b) -> Maybe (U var, b)
forall a. a -> Maybe a
Just ( Int -> U var
forall (var :: Symbol). Int -> U var
U (Int
kInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) , Int -> b
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
k )

-- | Integration
integrateUni :: (Field c, KnownSymbol var) => Univariate c var -> Univariate c var
integrateUni :: Univariate c var -> Univariate c var
integrateUni = FreeMod c (U var) -> Univariate c var
forall coeff (var :: Symbol).
FreeMod coeff (U var) -> Univariate coeff var
Uni (FreeMod c (U var) -> Univariate c var)
-> (Univariate c var -> FreeMod c (U var))
-> Univariate c var
-> Univariate c var
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (U var -> Maybe (U var, c))
-> FreeMod c (U var) -> FreeMod c (U var)
forall a b c.
(Ord a, Ord b, Eq c, Num c) =>
(a -> Maybe (b, c)) -> FreeMod c a -> FreeMod c b
ZMod.mapMaybeBaseCoeff U var -> Maybe (U var, c)
forall b (var :: Symbol) (var :: Symbol).
Fractional b =>
U var -> Maybe (U var, b)
f (FreeMod c (U var) -> FreeMod c (U var))
-> (Univariate c var -> FreeMod c (U var))
-> Univariate c var
-> FreeMod c (U var)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Univariate c var -> FreeMod c (U var)
forall c (v :: Symbol). Univariate c v -> FreeMod c (U v)
unUni where
  f :: U var -> Maybe (U var, b)
f (U Int
k) = (U var, b) -> Maybe (U var, b)
forall a. a -> Maybe a
Just ( Int -> U var
forall (var :: Symbol). Int -> U var
U (Int
kInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) , b
1 b -> b -> b
forall a. Fractional a => a -> a -> a
/ Int -> b
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int
kInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) )

integrateUni' :: (Field c, KnownSymbol var) => c -> Univariate c var -> Univariate c var
integrateUni' :: c -> Univariate c var -> Univariate c var
integrateUni' c
c0 Univariate c var
p = Univariate c var -> Univariate c var
forall c (var :: Symbol).
(Field c, KnownSymbol var) =>
Univariate c var -> Univariate c var
integrateUni Univariate c var
p Univariate c var -> Univariate c var -> Univariate c var
forall a. Num a => a -> a -> a
+ CoeffP (Univariate c var) -> Univariate c var
forall p. AlmostPolynomial p => CoeffP p -> p
scalarP c
CoeffP (Univariate c var)
c0

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

instance (Ring coeff, KnownSymbol var) => AlmostPolynomial (Univariate coeff var) where
                                          
  type CoeffP (Univariate coeff var) = coeff
  type MonomP (Univariate coeff var) = U var
  type VarP   (Univariate coeff var) = ()

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

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

  variableP :: VarP (Univariate coeff var) -> Univariate coeff var
variableP     = FreeMod coeff (U var) -> Univariate coeff var
forall coeff (var :: Symbol).
FreeMod coeff (U var) -> Univariate coeff var
Uni (FreeMod coeff (U var) -> Univariate coeff var)
-> (() -> FreeMod coeff (U var)) -> () -> Univariate coeff var
forall b c a. (b -> c) -> (a -> b) -> a -> c
. U var -> FreeMod coeff (U var)
forall c b. Num c => b -> FreeMod c b
ZMod.generator (U var -> FreeMod coeff (U var))
-> (() -> U var) -> () -> FreeMod coeff (U var)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. () -> U var
forall m. Monomial m => VarM m -> m
variableM
  singletonP :: VarP (Univariate coeff var) -> Int -> Univariate coeff var
singletonP    = \VarP (Univariate coeff var)
v Int
e -> FreeMod coeff (U var) -> Univariate coeff var
forall coeff (var :: Symbol).
FreeMod coeff (U var) -> Univariate coeff var
Uni (U var -> FreeMod coeff (U var)
forall c b. Num c => b -> FreeMod c b
ZMod.generator (VarM (U var) -> Int -> U var
forall m. Monomial m => VarM m -> Int -> m
singletonM VarP (Univariate coeff var)
VarM (U var)
v Int
e))
  monomP :: MonomP (Univariate coeff var) -> Univariate coeff var
monomP        = \MonomP (Univariate coeff var)
m     -> FreeMod coeff (U var) -> Univariate coeff var
forall coeff (var :: Symbol).
FreeMod coeff (U var) -> Univariate coeff var
Uni (FreeMod coeff (U var) -> Univariate coeff var)
-> FreeMod coeff (U var) -> Univariate coeff var
forall a b. (a -> b) -> a -> b
$ U var -> FreeMod coeff (U var)
forall c b. Num c => b -> FreeMod c b
ZMod.generator MonomP (Univariate coeff var)
U var
m
  monomP' :: MonomP (Univariate coeff var)
-> CoeffP (Univariate coeff var) -> Univariate coeff var
monomP'       = \MonomP (Univariate coeff var)
m CoeffP (Univariate coeff var)
c   -> FreeMod coeff (U var) -> Univariate coeff var
forall coeff (var :: Symbol).
FreeMod coeff (U var) -> Univariate coeff var
Uni (FreeMod coeff (U var) -> Univariate coeff var)
-> FreeMod coeff (U var) -> Univariate coeff var
forall a b. (a -> b) -> a -> b
$ U var -> coeff -> FreeMod coeff (U var)
forall b c. (Ord b, Num c, Eq c) => b -> c -> FreeMod c b
ZMod.singleton MonomP (Univariate coeff var)
U var
m coeff
CoeffP (Univariate coeff var)
c
  scalarP :: CoeffP (Univariate coeff var) -> Univariate coeff var
scalarP       = \CoeffP (Univariate coeff var)
s     -> FreeMod coeff (U var) -> Univariate coeff var
forall coeff (var :: Symbol).
FreeMod coeff (U var) -> Univariate coeff var
Uni (FreeMod coeff (U var) -> Univariate coeff var)
-> FreeMod coeff (U var) -> Univariate coeff var
forall a b. (a -> b) -> a -> b
$ U var -> coeff -> FreeMod coeff (U var)
forall b c. (Ord b, Num c, Eq c) => b -> c -> FreeMod c b
ZMod.singleton U var
forall m. Monomial m => m
emptyM coeff
CoeffP (Univariate coeff var)
s

  addP :: Univariate coeff var
-> Univariate coeff var -> Univariate coeff var
addP          = \Univariate coeff var
p1 Univariate coeff var
p2 -> FreeMod coeff (U var) -> Univariate coeff var
forall coeff (var :: Symbol).
FreeMod coeff (U var) -> Univariate coeff var
Uni (FreeMod coeff (U var) -> Univariate coeff var)
-> FreeMod coeff (U var) -> Univariate coeff var
forall a b. (a -> b) -> a -> b
$ FreeMod coeff (U var)
-> FreeMod coeff (U var) -> FreeMod coeff (U var)
forall b c.
(Ord b, Eq c, Num c) =>
FreeMod c b -> FreeMod c b -> FreeMod c b
ZMod.add (Univariate coeff var -> FreeMod coeff (U var)
forall c (v :: Symbol). Univariate c v -> FreeMod c (U v)
unUni Univariate coeff var
p1) (Univariate coeff var -> FreeMod coeff (U var)
forall c (v :: Symbol). Univariate c v -> FreeMod c (U v)
unUni Univariate coeff var
p2)
  subP :: Univariate coeff var
-> Univariate coeff var -> Univariate coeff var
subP          = \Univariate coeff var
p1 Univariate coeff var
p2 -> FreeMod coeff (U var) -> Univariate coeff var
forall coeff (var :: Symbol).
FreeMod coeff (U var) -> Univariate coeff var
Uni (FreeMod coeff (U var) -> Univariate coeff var)
-> FreeMod coeff (U var) -> Univariate coeff var
forall a b. (a -> b) -> a -> b
$ FreeMod coeff (U var)
-> FreeMod coeff (U var) -> FreeMod coeff (U var)
forall b c.
(Ord b, Eq c, Num c) =>
FreeMod c b -> FreeMod c b -> FreeMod c b
ZMod.sub (Univariate coeff var -> FreeMod coeff (U var)
forall c (v :: Symbol). Univariate c v -> FreeMod c (U v)
unUni Univariate coeff var
p1) (Univariate coeff var -> FreeMod coeff (U var)
forall c (v :: Symbol). Univariate c v -> FreeMod c (U v)
unUni Univariate coeff var
p2)
  negP :: Univariate coeff var -> Univariate coeff var
negP          = FreeMod coeff (U var) -> Univariate coeff var
forall coeff (var :: Symbol).
FreeMod coeff (U var) -> Univariate coeff var
Uni (FreeMod coeff (U var) -> Univariate coeff var)
-> (Univariate coeff var -> FreeMod coeff (U var))
-> Univariate coeff var
-> Univariate coeff var
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FreeMod coeff (U var) -> FreeMod coeff (U var)
forall c b. Num c => FreeMod c b -> FreeMod c b
ZMod.neg (FreeMod coeff (U var) -> FreeMod coeff (U var))
-> (Univariate coeff var -> FreeMod coeff (U var))
-> Univariate coeff var
-> FreeMod coeff (U var)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Univariate coeff var -> FreeMod coeff (U var)
forall c (v :: Symbol). Univariate c v -> FreeMod c (U v)
unUni
  mulP :: Univariate coeff var
-> Univariate coeff var -> Univariate coeff var
mulP          = \Univariate coeff var
p1 Univariate coeff var
p2 -> FreeMod coeff (U var) -> Univariate coeff var
forall coeff (var :: Symbol).
FreeMod coeff (U var) -> Univariate coeff var
Uni (FreeMod coeff (U var) -> Univariate coeff var)
-> FreeMod coeff (U var) -> Univariate coeff var
forall a b. (a -> b) -> a -> b
$ (U var -> U var -> U var)
-> FreeMod coeff (U var)
-> FreeMod coeff (U var)
-> FreeMod coeff (U var)
forall b c.
(Ord b, Eq c, Num c) =>
(b -> b -> b) -> FreeMod c b -> FreeMod c b -> FreeMod c b
ZMod.mulWith U var -> U var -> U var
forall m. Monomial m => m -> m -> m
mulM (Univariate coeff var -> FreeMod coeff (U var)
forall c (v :: Symbol). Univariate c v -> FreeMod c (U v)
unUni Univariate coeff var
p1) (Univariate coeff var -> FreeMod coeff (U var)
forall c (v :: Symbol). Univariate c v -> FreeMod c (U v)
unUni Univariate coeff var
p2)
  productP :: [Univariate coeff var] -> Univariate coeff var
productP      = \[Univariate coeff var]
ps    -> FreeMod coeff (U var) -> Univariate coeff var
forall coeff (var :: Symbol).
FreeMod coeff (U var) -> Univariate coeff var
Uni (FreeMod coeff (U var) -> Univariate coeff var)
-> FreeMod coeff (U var) -> Univariate coeff var
forall a b. (a -> b) -> a -> b
$ U var
-> (U var -> U var -> U var)
-> [FreeMod coeff (U var)]
-> FreeMod coeff (U var)
forall b c.
(Ord b, Eq c, Num c) =>
b -> (b -> b -> b) -> [FreeMod c b] -> FreeMod c b
ZMod.productWith U var
forall m. Monomial m => m
emptyM U var -> U var -> U var
forall m. Monomial m => m -> m -> m
mulM ([FreeMod coeff (U var)] -> FreeMod coeff (U var))
-> [FreeMod coeff (U var)] -> FreeMod coeff (U var)
forall a b. (a -> b) -> a -> b
$ (Univariate coeff var -> FreeMod coeff (U var))
-> [Univariate coeff var] -> [FreeMod coeff (U var)]
forall a b. (a -> b) -> [a] -> [b]
map Univariate coeff var -> FreeMod coeff (U var)
forall c (v :: Symbol). Univariate c v -> FreeMod c (U v)
unUni [Univariate coeff var]
ps

  coeffOfP :: MonomP (Univariate coeff var)
-> Univariate coeff var -> CoeffP (Univariate coeff var)
coeffOfP      = \MonomP (Univariate coeff var)
m Univariate coeff var
p   -> U var -> FreeMod coeff (U var) -> coeff
forall b c. (Ord b, Num c) => b -> FreeMod c b -> c
ZMod.coeffOf MonomP (Univariate coeff var)
U var
m (Univariate coeff var -> FreeMod coeff (U var)
forall c (v :: Symbol). Univariate c v -> FreeMod c (U v)
unUni Univariate coeff var
p)
  mulByMonomP :: MonomP (Univariate coeff var)
-> Univariate coeff var -> Univariate coeff var
mulByMonomP   = \MonomP (Univariate coeff var)
m Univariate coeff var
p   -> FreeMod coeff (U var) -> Univariate coeff var
forall coeff (var :: Symbol).
FreeMod coeff (U var) -> Univariate coeff var
Uni (FreeMod coeff (U var) -> Univariate coeff var)
-> FreeMod coeff (U var) -> Univariate coeff var
forall a b. (a -> b) -> a -> b
$ U var -> FreeMod coeff (U var) -> FreeMod coeff (U var)
forall c b.
(Eq c, Num c, Ord b, Monoid b) =>
b -> FreeMod c b -> FreeMod c b
ZMod.mulByMonom  MonomP (Univariate coeff var)
U var
m (Univariate coeff var -> FreeMod coeff (U var)
forall c (v :: Symbol). Univariate c v -> FreeMod c (U v)
unUni Univariate coeff var
p)
  scaleP :: CoeffP (Univariate coeff var)
-> Univariate coeff var -> Univariate coeff var
scaleP        = \CoeffP (Univariate coeff var)
s Univariate coeff var
p   -> FreeMod coeff (U var) -> Univariate coeff var
forall coeff (var :: Symbol).
FreeMod coeff (U var) -> Univariate coeff var
Uni (FreeMod coeff (U var) -> Univariate coeff var)
-> FreeMod coeff (U var) -> Univariate coeff var
forall a b. (a -> b) -> a -> b
$ coeff -> FreeMod coeff (U var) -> FreeMod coeff (U var)
forall b c. (Ord b, Eq c, Num c) => c -> FreeMod c b -> FreeMod c b
ZMod.scale coeff
CoeffP (Univariate coeff var)
s (Univariate coeff var -> FreeMod coeff (U var)
forall c (v :: Symbol). Univariate c v -> FreeMod c (U v)
unUni Univariate coeff var
p) 

instance (Ring coeff, KnownSymbol var) => Polynomial (Univariate coeff var) where
  evalP :: (CoeffP (Univariate coeff var) -> d)
-> (VarP (Univariate coeff var) -> d) -> Univariate coeff var -> d
evalP         = \CoeffP (Univariate coeff var) -> d
g VarP (Univariate coeff var) -> d
f Univariate coeff var
p -> let { !z :: U var -> d
z = (VarM (U var) -> d) -> U var -> d
forall m c. (Monomial m, Num c) => (VarM m -> c) -> m -> c
evalM VarP (Univariate coeff var) -> d
VarM (U var) -> d
f ; h :: (U var, coeff) -> d
h (!U var
m,!coeff
c) = CoeffP (Univariate coeff var) -> d
g coeff
CoeffP (Univariate coeff var)
c d -> d -> d
forall a. Num a => a -> a -> a
* U var -> d
z U var
m } in [d] -> d
forall a. Num a => [a] -> a
sum' ([d] -> d) -> [d] -> d
forall a b. (a -> b) -> a -> b
$ ((U var, coeff) -> d) -> [(U var, coeff)] -> [d]
forall a b. (a -> b) -> [a] -> [b]
map (U var, coeff) -> d
h ([(U var, coeff)] -> [d]) -> [(U var, coeff)] -> [d]
forall a b. (a -> b) -> a -> b
$ FreeMod coeff (U var) -> [(U var, coeff)]
forall c b. FreeMod c b -> [(b, c)]
ZMod.toList (FreeMod coeff (U var) -> [(U var, coeff)])
-> FreeMod coeff (U var) -> [(U var, coeff)]
forall a b. (a -> b) -> a -> b
$ Univariate coeff var -> FreeMod coeff (U var)
forall c (v :: Symbol). Univariate c v -> FreeMod c (U v)
unUni Univariate coeff var
p
  varSubsP :: (VarP (Univariate coeff var) -> VarP (Univariate coeff var))
-> Univariate coeff var -> Univariate coeff var
varSubsP      = \VarP (Univariate coeff var) -> VarP (Univariate coeff var)
f Univariate coeff var
p   -> FreeMod coeff (U var) -> Univariate coeff var
forall coeff (var :: Symbol).
FreeMod coeff (U var) -> Univariate coeff var
Uni (FreeMod coeff (U var) -> Univariate coeff var)
-> FreeMod coeff (U var) -> Univariate coeff var
forall a b. (a -> b) -> a -> b
$ (U var -> U var) -> FreeMod coeff (U var) -> FreeMod coeff (U var)
forall a b c.
(Ord a, Ord b, Eq c, Num c) =>
(a -> b) -> FreeMod c a -> FreeMod c b
ZMod.mapBase ((VarM (U var) -> VarM (U var)) -> U var -> U var
forall m. Monomial m => (VarM m -> VarM m) -> m -> m
varSubsM VarP (Univariate coeff var) -> VarP (Univariate coeff var)
VarM (U var) -> VarM (U var)
f) (Univariate coeff var -> FreeMod coeff (U var)
forall c (v :: Symbol). Univariate c v -> FreeMod c (U v)
unUni Univariate coeff var
p)
  coeffSubsP :: (VarP (Univariate coeff var)
 -> Maybe (CoeffP (Univariate coeff var)))
-> Univariate coeff var -> Univariate coeff var
coeffSubsP    = \VarP (Univariate coeff var)
-> Maybe (CoeffP (Univariate coeff var))
f Univariate coeff var
p   -> FreeMod coeff (U var) -> Univariate coeff var
forall coeff (var :: Symbol).
FreeMod coeff (U var) -> Univariate coeff var
Uni (FreeMod coeff (U var) -> Univariate coeff var)
-> FreeMod coeff (U var) -> Univariate coeff var
forall a b. (a -> b) -> a -> b
$ [(U var, coeff)] -> FreeMod coeff (U var)
forall c b. (Eq c, Num c, Ord b) => [(b, c)] -> FreeMod c b
ZMod.fromList ([(U var, coeff)] -> FreeMod coeff (U var))
-> [(U var, coeff)] -> FreeMod coeff (U var)
forall a b. (a -> b) -> a -> b
$ ((U var, coeff) -> (U var, coeff))
-> [(U var, coeff)] -> [(U var, coeff)]
forall a b. (a -> b) -> [a] -> [b]
map ((VarM (U var) -> Maybe coeff) -> (U var, coeff) -> (U var, coeff)
forall m c.
(Monomial m, Num c) =>
(VarM m -> Maybe c) -> (m, c) -> (m, c)
termSubsM VarP (Univariate coeff var)
-> Maybe (CoeffP (Univariate coeff var))
VarM (U var) -> Maybe coeff
f) ([(U var, coeff)] -> [(U var, coeff)])
-> [(U var, coeff)] -> [(U var, coeff)]
forall a b. (a -> b) -> a -> b
$ FreeMod coeff (U var) -> [(U var, coeff)]
forall c b. FreeMod c b -> [(b, c)]
ZMod.toList (FreeMod coeff (U var) -> [(U var, coeff)])
-> FreeMod coeff (U var) -> [(U var, coeff)]
forall a b. (a -> b) -> a -> b
$ Univariate coeff var -> FreeMod coeff (U var)
forall c (v :: Symbol). Univariate c v -> FreeMod c (U v)
unUni Univariate coeff var
p 
  subsP :: (VarP (Univariate coeff var) -> Univariate coeff var)
-> Univariate coeff var -> Univariate coeff var
subsP         = \VarP (Univariate coeff var) -> Univariate coeff var
f Univariate coeff var
p   -> FreeMod coeff (U var) -> Univariate coeff var
forall coeff (var :: Symbol).
FreeMod coeff (U var) -> Univariate coeff var
Uni (FreeMod coeff (U var) -> Univariate coeff var)
-> FreeMod coeff (U var) -> Univariate coeff var
forall a b. (a -> b) -> a -> b
$ (U var -> FreeMod coeff (U var))
-> FreeMod coeff (U var) -> FreeMod coeff (U var)
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 (U var) -> FreeMod coeff (U var))
-> U var -> FreeMod coeff (U var)
forall m c. (Monomial m, Num c) => (VarM m -> c) -> m -> c
evalM (Univariate coeff var -> FreeMod coeff (U var)
forall c (v :: Symbol). Univariate c v -> FreeMod c (U v)
unUni (Univariate coeff var -> FreeMod coeff (U var))
-> (() -> Univariate coeff var) -> () -> FreeMod coeff (U var)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. () -> Univariate coeff var
VarP (Univariate coeff var) -> Univariate coeff var
f)) (Univariate coeff var -> FreeMod coeff (U var)
forall c (v :: Symbol). Univariate c v -> FreeMod c (U v)
unUni Univariate coeff var
p)

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

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

-- hackety hack hack...
instance IsSigned (Univariate c v) where
  signOf :: Univariate c v -> Maybe Sign
signOf = Maybe Sign -> Univariate 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 (Univariate c v) where
  isZeroR :: Univariate c v -> Bool
isZeroR   = FreeMod c (U v) -> Bool
forall b c. Ord b => FreeMod c b -> Bool
ZMod.isZero (FreeMod c (U v) -> Bool)
-> (Univariate c v -> FreeMod c (U v)) -> Univariate c v -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Univariate c v -> FreeMod c (U v)
forall c (v :: Symbol). Univariate c v -> FreeMod c (U v)
unUni
  isAtomicR :: Proxy (Univariate c v) -> Bool
isAtomicR = Bool -> Proxy (Univariate c v) -> Bool
forall a b. a -> b -> a
const Bool
False
  isSignedR :: Proxy (Univariate c v) -> Bool
isSignedR = Bool -> Proxy (Univariate c v) -> Bool
forall a b. a -> b -> a
const Bool
False
  absR :: Univariate c v -> Univariate c v
absR      = Univariate c v -> Univariate c v
forall a. a -> a
id
  signumR :: Univariate c v -> Maybe Sign
signumR   = Maybe Sign -> Univariate c v -> Maybe Sign
forall a b. a -> b -> a
const (Sign -> Maybe Sign
forall a. a -> Maybe a
Just Sign
Plus)

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