{-# OPTIONS_HADDOCK show-extensions #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE TypeSynonymInstances #-}
module ToySolver.Data.Polynomial.Factorization.Rational () where
import Data.List (foldl')
import Data.Ratio
import ToySolver.Data.Polynomial.Base (UPolynomial)
import qualified ToySolver.Data.Polynomial.Base as P
import ToySolver.Data.Polynomial.Factorization.Integer ()
instance P.Factor (UPolynomial Rational) where
factor :: UPolynomial Rational -> [(UPolynomial Rational, Integer)]
factor UPolynomial Rational
0 = [(UPolynomial Rational
0,Integer
1)]
factor UPolynomial Rational
p = [(forall k v. (Eq k, Num k) => k -> Polynomial k v
P.constant Rational
c, Integer
1) | Rational
c forall a. Eq a => a -> a -> Bool
/= Rational
1] forall a. [a] -> [a] -> [a]
++ [(UPolynomial Rational, Integer)]
qs2
where
qs :: [(Polynomial Integer X, Integer)]
qs = forall a. Factor a => a -> [(a, Integer)]
P.factor forall a b. (a -> b) -> a -> b
$ forall k v.
(ContPP k, Ord v) =>
Polynomial k v -> Polynomial (PPCoeff k) v
P.pp UPolynomial Rational
p
qs2 :: [(UPolynomial Rational, Integer)]
qs2 = [(forall k1 k v.
(Eq k1, Num k1) =>
(k -> k1) -> Polynomial k v -> Polynomial k1 v
P.mapCoeff forall a. Num a => Integer -> a
fromInteger Polynomial Integer X
q, Integer
m) | (Polynomial Integer X
q,Integer
m) <- [(Polynomial Integer X, Integer)]
qs, forall t. Degree t => t -> Integer
P.deg Polynomial Integer X
q forall a. Ord a => a -> a -> Bool
> Integer
0]
c :: Rational
c = forall a. Real a => a -> Rational
toRational (forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
product [(forall k v. (Num k, Ord v) => Monomial v -> Polynomial k v -> k
P.coeff forall v. Monomial v
P.mone Polynomial Integer X
q)forall a b. (Num a, Integral b) => a -> b -> a
^Integer
m | (Polynomial Integer X
q,Integer
m) <- [(Polynomial Integer X, Integer)]
qs, forall t. Degree t => t -> Integer
P.deg Polynomial Integer X
q forall a. Eq a => a -> a -> Bool
== Integer
0]) forall a. Num a => a -> a -> a
* forall k v. (ContPP k, Ord v) => Polynomial k v -> k
P.cont UPolynomial Rational
p