{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE CPP #-}
{-# LANGUAGE ConstraintKinds #-}
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE RoleAnnotations #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE UndecidableSuperClasses #-}
{-# LANGUAGE NoImplicitPrelude #-}
{-# OPTIONS_GHC -Wno-redundant-constraints #-}

-- | Polynomial type optimized to univariate polynomial.
module Algebra.Ring.Polynomial.Univariate
  ( Unipol (),
    naiveMult,
    karatsuba,
    coeffList,
    cutoff,
    termsUnipol,
    divModUnipolByMult,
    divModUnipol,
    mapCoeffUnipol,
    liftMapUnipol,
    module Algebra.Ring.Polynomial.Class,
    module Algebra.Ring.Polynomial.Monomial,
  )
where

import Algebra.Prelude.Core
import Algebra.Ring.Polynomial.Class
import Algebra.Ring.Polynomial.Monomial
import Control.DeepSeq (NFData)
import qualified Data.Coerce as C
import qualified Data.Foldable as F
import qualified Data.HashSet as HS
import qualified Data.IntMap as IM
import qualified Data.Map.Strict as M
import qualified Data.Sized as SV
import qualified Numeric.Algebra as NA
import qualified Prelude as P

{- | Univariate polynomial.
   It uses @'IM.IntMap'@ as its internal representation;
   so if you want to treat the power greater than @maxBound :: Int@,
   please consider using other represntation.
-}
newtype Unipol r = Unipol {Unipol r -> IntMap r
runUnipol :: IM.IntMap r}
  deriving (Unipol r -> ()
(Unipol r -> ()) -> NFData (Unipol r)
forall r. NFData r => Unipol r -> ()
forall a. (a -> ()) -> NFData a
rnf :: Unipol r -> ()
$crnf :: forall r. NFData r => Unipol r -> ()
NFData, a -> Unipol a -> Bool
Unipol m -> m
Unipol a -> [a]
Unipol a -> Bool
Unipol a -> Int
Unipol a -> a
Unipol a -> a
Unipol a -> a
Unipol a -> a
(a -> m) -> Unipol a -> m
(a -> m) -> Unipol a -> m
(a -> b -> b) -> b -> Unipol a -> b
(a -> b -> b) -> b -> Unipol a -> b
(b -> a -> b) -> b -> Unipol a -> b
(b -> a -> b) -> b -> Unipol a -> b
(a -> a -> a) -> Unipol a -> a
(a -> a -> a) -> Unipol a -> a
(forall m. Monoid m => Unipol m -> m)
-> (forall m a. Monoid m => (a -> m) -> Unipol a -> m)
-> (forall m a. Monoid m => (a -> m) -> Unipol a -> m)
-> (forall a b. (a -> b -> b) -> b -> Unipol a -> b)
-> (forall a b. (a -> b -> b) -> b -> Unipol a -> b)
-> (forall b a. (b -> a -> b) -> b -> Unipol a -> b)
-> (forall b a. (b -> a -> b) -> b -> Unipol a -> b)
-> (forall a. (a -> a -> a) -> Unipol a -> a)
-> (forall a. (a -> a -> a) -> Unipol a -> a)
-> (forall a. Unipol a -> [a])
-> (forall a. Unipol a -> Bool)
-> (forall a. Unipol a -> Int)
-> (forall a. Eq a => a -> Unipol a -> Bool)
-> (forall a. Ord a => Unipol a -> a)
-> (forall a. Ord a => Unipol a -> a)
-> (forall a. Num a => Unipol a -> a)
-> (forall a. Num a => Unipol a -> a)
-> Foldable Unipol
forall a. Eq a => a -> Unipol a -> Bool
forall a. Num a => Unipol a -> a
forall a. Ord a => Unipol a -> a
forall m. Monoid m => Unipol m -> m
forall a. Unipol a -> Bool
forall a. Unipol a -> Int
forall a. Unipol a -> [a]
forall a. (a -> a -> a) -> Unipol a -> a
forall m a. Monoid m => (a -> m) -> Unipol a -> m
forall b a. (b -> a -> b) -> b -> Unipol a -> b
forall a b. (a -> b -> b) -> b -> Unipol a -> b
forall (t :: * -> *).
(forall m. Monoid m => t m -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. t a -> [a])
-> (forall a. t a -> Bool)
-> (forall a. t a -> Int)
-> (forall a. Eq a => a -> t a -> Bool)
-> (forall a. Ord a => t a -> a)
-> (forall a. Ord a => t a -> a)
-> (forall a. Num a => t a -> a)
-> (forall a. Num a => t a -> a)
-> Foldable t
product :: Unipol a -> a
$cproduct :: forall a. Num a => Unipol a -> a
sum :: Unipol a -> a
$csum :: forall a. Num a => Unipol a -> a
minimum :: Unipol a -> a
$cminimum :: forall a. Ord a => Unipol a -> a
maximum :: Unipol a -> a
$cmaximum :: forall a. Ord a => Unipol a -> a
elem :: a -> Unipol a -> Bool
$celem :: forall a. Eq a => a -> Unipol a -> Bool
length :: Unipol a -> Int
$clength :: forall a. Unipol a -> Int
null :: Unipol a -> Bool
$cnull :: forall a. Unipol a -> Bool
toList :: Unipol a -> [a]
$ctoList :: forall a. Unipol a -> [a]
foldl1 :: (a -> a -> a) -> Unipol a -> a
$cfoldl1 :: forall a. (a -> a -> a) -> Unipol a -> a
foldr1 :: (a -> a -> a) -> Unipol a -> a
$cfoldr1 :: forall a. (a -> a -> a) -> Unipol a -> a
foldl' :: (b -> a -> b) -> b -> Unipol a -> b
$cfoldl' :: forall b a. (b -> a -> b) -> b -> Unipol a -> b
foldl :: (b -> a -> b) -> b -> Unipol a -> b
$cfoldl :: forall b a. (b -> a -> b) -> b -> Unipol a -> b
foldr' :: (a -> b -> b) -> b -> Unipol a -> b
$cfoldr' :: forall a b. (a -> b -> b) -> b -> Unipol a -> b
foldr :: (a -> b -> b) -> b -> Unipol a -> b
$cfoldr :: forall a b. (a -> b -> b) -> b -> Unipol a -> b
foldMap' :: (a -> m) -> Unipol a -> m
$cfoldMap' :: forall m a. Monoid m => (a -> m) -> Unipol a -> m
foldMap :: (a -> m) -> Unipol a -> m
$cfoldMap :: forall m a. Monoid m => (a -> m) -> Unipol a -> m
fold :: Unipol m -> m
$cfold :: forall m. Monoid m => Unipol m -> m
Foldable)

type role Unipol representational

instance (DecidableZero r, Hashable r) => Hashable (Unipol r) where
  hashWithSalt :: Int -> Unipol r -> Int
hashWithSalt Int
p = Int -> [(Int, r)] -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
p ([(Int, r)] -> Int) -> (Unipol r -> [(Int, r)]) -> Unipol r -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntMap r -> [(Int, r)]
forall a. IntMap a -> [(Int, a)]
IM.toList (IntMap r -> [(Int, r)])
-> (Unipol r -> IntMap r) -> Unipol r -> [(Int, r)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Unipol r -> IntMap r
forall r. Unipol r -> IntMap r
runUnipol

{- | By this instance, you can use @#x@ for
   the unique variable of @'Unipol' r@.
-}
instance Unital r => IsLabel "x" (Unipol r) where
  fromLabel :: Unipol r
fromLabel = IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol (IntMap r -> Unipol r) -> IntMap r -> Unipol r
forall a b. (a -> b) -> a -> b
$ Int -> r -> IntMap r
forall a. Int -> a -> IntMap a
IM.singleton Int
1 r
forall r. Unital r => r
one

divModUnipol :: (CoeffRing r, Field r) => Unipol r -> Unipol r -> (Unipol r, Unipol r)
divModUnipol :: Unipol r -> Unipol r -> (Unipol r, Unipol r)
divModUnipol Unipol r
f Unipol r
g =
  if Unipol r -> Bool
forall r. DecidableZero r => r -> Bool
isZero Unipol r
g then [Char] -> (Unipol r, Unipol r)
forall a. HasCallStack => [Char] -> a
error [Char]
"Divided by zero!" else Unipol r -> Unipol r -> (Unipol r, Unipol r)
loop Unipol r
f Unipol r
forall m. Monoidal m => m
zero
  where
    (Int
dq, r
cq) = Unipol r -> (Int, r)
forall r. Monoidal r => Unipol r -> (Int, r)
leadingTermIM Unipol r
g
    loop :: Unipol r -> Unipol r -> (Unipol r, Unipol r)
loop Unipol r
p !Unipol r
acc =
      let (Int
dp, r
cp) = Unipol r -> (Int, r)
forall r. Monoidal r => Unipol r -> (Int, r)
leadingTermIM Unipol r
p
          coe :: r
coe = r
cp r -> r -> r
forall r. Division r => r -> r -> r
/ r
cq
          deg :: Int
deg = Int
dp Int -> Int -> Int
forall r. Group r => r -> r -> r
- Int
dq
          canceler :: Unipol r
canceler = IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol (IntMap r -> Unipol r) -> IntMap r -> Unipol r
forall a b. (a -> b) -> a -> b
$ (r -> r) -> IntMap r -> IntMap r
forall a b. (a -> b) -> IntMap a -> IntMap b
IM.map (r -> r -> r
forall r. Multiplicative r => r -> r -> r
* r
coe) (IntMap r -> IntMap r) -> IntMap r -> IntMap r
forall a b. (a -> b) -> a -> b
$ (Int -> Int) -> IntMap r -> IntMap r
forall a. (Int -> Int) -> IntMap a -> IntMap a
IM.mapKeysMonotonic (Int -> Int -> Int
forall r. Additive r => r -> r -> r
+ Int
deg) (Unipol r -> IntMap r
forall r. Unipol r -> IntMap r
runUnipol Unipol r
g)
       in if Int
dp Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
dq Bool -> Bool -> Bool
|| Unipol r -> Bool
forall r. DecidableZero r => r -> Bool
isZero Unipol r
p
            then (Unipol r
acc, Unipol r
p)
            else
              Unipol r -> Unipol r -> (Unipol r, Unipol r)
loop (Unipol r
p Unipol r -> Unipol r -> Unipol r
forall r. Group r => r -> r -> r
- Unipol r
canceler) (Unipol r -> (Unipol r, Unipol r))
-> Unipol r -> (Unipol r, Unipol r)
forall a b. (a -> b) -> a -> b
$
                IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol (IntMap r -> Unipol r) -> IntMap r -> Unipol r
forall a b. (a -> b) -> a -> b
$ Int -> r -> IntMap r -> IntMap r
forall a. Int -> a -> IntMap a -> IntMap a
IM.insert Int
deg r
coe (IntMap r -> IntMap r) -> IntMap r -> IntMap r
forall a b. (a -> b) -> a -> b
$ Unipol r -> IntMap r
forall r. Unipol r -> IntMap r
runUnipol Unipol r
acc
{-# INLINE divModUnipol #-}

divModUnipolByMult :: (Eq r, Field r) => Unipol r -> Unipol r -> (Unipol r, Unipol r)
divModUnipolByMult :: Unipol r -> Unipol r -> (Unipol r, Unipol r)
divModUnipolByMult Unipol r
f Unipol r
g =
  if Unipol r -> Bool
forall r. DecidableZero r => r -> Bool
isZero Unipol r
g
    then [Char] -> (Unipol r, Unipol r)
forall a. HasCallStack => [Char] -> a
error [Char]
"Divided by zero!"
    else
      let ((Int
n, r
_), (Int
m, r
_)) = (Unipol r -> (Int, r)
forall r. Monoidal r => Unipol r -> (Int, r)
leadingTermIM Unipol r
f, Unipol r -> (Int, r)
forall r. Monoidal r => Unipol r -> (Int, r)
leadingTermIM Unipol r
g)
          i :: Int
i = Int -> Int
logBase2 (Int
n Int -> Int -> Int
forall r. Group r => r -> r -> r
- Int
m Int -> Int -> Int
forall r. Additive r => r -> r -> r
+ Int
1) Int -> Int -> Int
forall r. Additive r => r -> r -> r
+ Int
1
          g' :: Unipol r
g' = Unipol r -> Unipol r
forall r. Monoidal r => Unipol r -> Unipol r
reversalIM Unipol r
g
          t :: Unipol r
t = Int -> Unipol r -> Unipol r
forall r. (Eq r, Field r) => Int -> Unipol r -> Unipol r
recipBinPow Int
i Unipol r
g'
          q :: Unipol r
q =
            Int -> Unipol r -> Unipol r
forall r. Monoidal r => Int -> Unipol r -> Unipol r
reversalIMWith (Int
n Int -> Int -> Int
forall r. Group r => r -> r -> r
- Int
m) (Unipol r -> Unipol r) -> Unipol r -> Unipol r
forall a b. (a -> b) -> a -> b
$
              Int -> Unipol r -> Unipol r
forall r. Int -> Unipol r -> Unipol r
modVarPower (Int
n Int -> Int -> Int
forall r. Group r => r -> r -> r
- Int
m Int -> Int -> Int
forall r. Additive r => r -> r -> r
+ Int
1) (Unipol r -> Unipol r) -> Unipol r -> Unipol r
forall a b. (a -> b) -> a -> b
$
                Unipol r
t Unipol r -> Unipol r -> Unipol r
forall r. Multiplicative r => r -> r -> r
* Unipol r -> Unipol r
forall r. Monoidal r => Unipol r -> Unipol r
reversalIM Unipol r
f
       in if Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
m
            then (Unipol r
q, Unipol r
f Unipol r -> Unipol r -> Unipol r
forall r. Group r => r -> r -> r
- Unipol r
g Unipol r -> Unipol r -> Unipol r
forall r. Multiplicative r => r -> r -> r
* Unipol r
q)
            else (Unipol r
forall m. Monoidal m => m
zero, Unipol r
f)
{-# INLINE divModUnipolByMult #-}

recipBinPow ::
  (Eq r, Field r) =>
  Int ->
  Unipol r ->
  Unipol r
recipBinPow :: Int -> Unipol r -> Unipol r
recipBinPow Int
i Unipol r
f =
  let g :: Int -> Unipol r
g Int
0 = IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol (IntMap r -> Unipol r) -> IntMap r -> Unipol r
forall a b. (a -> b) -> a -> b
$ Int -> r -> IntMap r
forall a. Int -> a -> IntMap a
IM.singleton Int
0 (r -> IntMap r) -> r -> IntMap r
forall a b. (a -> b) -> a -> b
$ r -> r
forall r. Division r => r -> r
recip (Unipol r -> Coefficient (Unipol r)
forall poly. IsPolynomial poly => poly -> Coefficient poly
constantTerm Unipol r
f)
      g Int
k =
        let p :: Unipol r
p = Int -> Unipol r
g (Int
k Int -> Int -> Int
forall r. Group r => r -> r -> r
- Int
1)
         in Int -> Unipol r -> Unipol r
forall r. Int -> Unipol r -> Unipol r
modVarPower (Int
2 Int -> Natural -> Int
forall r. Unital r => r -> Natural -> r
^ Int -> Natural
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
k) (Integer -> Unipol r
forall a. Num a => Integer -> a
P.fromInteger Integer
2 Unipol r -> Unipol r -> Unipol r
forall r. Multiplicative r => r -> r -> r
* Unipol r
p Unipol r -> Unipol r -> Unipol r
forall r. Group r => r -> r -> r
- Unipol r
p Unipol r -> Unipol r -> Unipol r
forall r. Multiplicative r => r -> r -> r
* Unipol r
p Unipol r -> Unipol r -> Unipol r
forall r. Multiplicative r => r -> r -> r
* Unipol r
f)
   in Int -> Unipol r
g Int
i
{-# INLINE recipBinPow #-}

modVarPower :: Int -> Unipol r -> Unipol r
modVarPower :: Int -> Unipol r -> Unipol r
modVarPower Int
n = IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol (IntMap r -> Unipol r)
-> (Unipol r -> IntMap r) -> Unipol r -> Unipol r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (IntMap r, IntMap r) -> IntMap r
forall a b. (a, b) -> a
fst ((IntMap r, IntMap r) -> IntMap r)
-> (Unipol r -> (IntMap r, IntMap r)) -> Unipol r -> IntMap r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> IntMap r -> (IntMap r, IntMap r)
forall a. Int -> IntMap a -> (IntMap a, IntMap a)
IM.split Int
n (IntMap r -> (IntMap r, IntMap r))
-> (Unipol r -> IntMap r) -> Unipol r -> (IntMap r, IntMap r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Unipol r -> IntMap r
forall r. Unipol r -> IntMap r
runUnipol
{-# INLINE modVarPower #-}

reversalIM :: Monoidal r => Unipol r -> Unipol r
reversalIM :: Unipol r -> Unipol r
reversalIM Unipol r
m = Int -> Unipol r -> Unipol r
forall r. Monoidal r => Int -> Unipol r -> Unipol r
reversalIMWith ((Int, r) -> Int
forall a b. (a, b) -> a
fst ((Int, r) -> Int) -> (Int, r) -> Int
forall a b. (a -> b) -> a -> b
$ Unipol r -> (Int, r)
forall r. Monoidal r => Unipol r -> (Int, r)
leadingTermIM Unipol r
m) Unipol r
m
{-# INLINE reversalIM #-}

reversalIMWith :: Monoidal r => Int -> Unipol r -> Unipol r
reversalIMWith :: Int -> Unipol r -> Unipol r
reversalIMWith Int
d = IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol (IntMap r -> Unipol r)
-> (Unipol r -> IntMap r) -> Unipol r -> Unipol r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int -> Int) -> IntMap r -> IntMap r
forall a. (Int -> Int) -> IntMap a -> IntMap a
IM.mapKeys (Int
d Int -> Int -> Int
forall r. Group r => r -> r -> r
-) (IntMap r -> IntMap r)
-> (Unipol r -> IntMap r) -> Unipol r -> IntMap r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Unipol r -> IntMap r
forall r. Unipol r -> IntMap r
runUnipol
{-# INLINE reversalIMWith #-}

instance (Eq r, Field r) => DecidableUnits (Unipol r) where
  isUnit :: Unipol r -> Bool
isUnit Unipol r
f =
    let (r
lc, OrderedMonomial Grevlex 1
lm) = Unipol r
-> (Coefficient (Unipol r),
    OrderedMonomial (MOrder (Unipol r)) (Arity (Unipol r)))
forall poly.
IsOrderedPolynomial poly =>
poly
-> (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
leadingTerm Unipol r
f
     in OrderedMonomial Grevlex 1
lm OrderedMonomial Grevlex 1 -> OrderedMonomial Grevlex 1 -> Bool
forall a. Eq a => a -> a -> Bool
== OrderedMonomial Grevlex 1
forall r. Unital r => r
one Bool -> Bool -> Bool
&& r -> Bool
forall r. DecidableUnits r => r -> Bool
isUnit r
lc
  recipUnit :: Unipol r -> Maybe (Unipol r)
recipUnit Unipol r
f
    | Unipol r -> Bool
forall r. DecidableUnits r => r -> Bool
isUnit Unipol r
f = r -> Unipol r
forall poly. IsPolynomial poly => Coefficient poly -> poly
injectCoeff (r -> Unipol r) -> Maybe r -> Maybe (Unipol r)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> r -> Maybe r
forall r. DecidableUnits r => r -> Maybe r
recipUnit (Unipol r -> Coefficient (Unipol r)
forall poly. IsOrderedPolynomial poly => poly -> Coefficient poly
leadingCoeff Unipol r
f)
    | Bool
otherwise = Maybe (Unipol r)
forall a. Maybe a
Nothing

instance (Eq r, Field r) => DecidableAssociates (Unipol r) where
  isAssociate :: Unipol r -> Unipol r -> Bool
isAssociate = Unipol r -> Unipol r -> Bool
forall a. Eq a => a -> a -> Bool
(==) (Unipol r -> Unipol r -> Bool)
-> (Unipol r -> Unipol r) -> Unipol r -> Unipol r -> Bool
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` Unipol r -> Unipol r
forall r. UnitNormalForm r => r -> r
normaliseUnit

instance (Eq r, Field r) => UnitNormalForm (Unipol r) where
  splitUnit :: Unipol r -> (Unipol r, Unipol r)
splitUnit Unipol r
f
    | Unipol r -> Bool
forall r. DecidableZero r => r -> Bool
isZero Unipol r
f = (Unipol r
forall m. Monoidal m => m
zero, Unipol r
f)
    | Bool
otherwise =
      let lc :: Coefficient (Unipol r)
lc = Unipol r -> Coefficient (Unipol r)
forall poly. IsOrderedPolynomial poly => poly -> Coefficient poly
leadingCoeff Unipol r
f
       in (Coefficient (Unipol r) -> Unipol r
forall poly. IsPolynomial poly => Coefficient poly -> poly
injectCoeff Coefficient (Unipol r)
lc, Coefficient (Unipol r) -> Unipol r
forall poly. IsPolynomial poly => Coefficient poly -> poly
injectCoeff (r -> r
forall r. Division r => r -> r
recip r
Coefficient (Unipol r)
lc) Unipol r -> Unipol r -> Unipol r
forall r. Multiplicative r => r -> r -> r
* Unipol r
f)

instance (Eq r, Field r) => GCDDomain (Unipol r)

instance (Eq r, Field r) => ZeroProductSemiring (Unipol r)

instance (Eq r, Field r) => IntegralDomain (Unipol r)

instance (Eq r, Field r) => UFD (Unipol r)

instance (Eq r, Field r) => PID (Unipol r)

instance (Eq r, Field r) => Euclidean (Unipol r) where
  divide :: Unipol r -> Unipol r -> (Unipol r, Unipol r)
divide Unipol r
f Unipol r
g =
    if Unipol r -> Int
forall poly. IsPolynomial poly => poly -> Int
totalDegree' Unipol r
f Int -> Int -> Int
forall a. Ord a => a -> a -> a
`min` Unipol r -> Int
forall poly. IsPolynomial poly => poly -> Int
totalDegree' Unipol r
g Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
50
      then Unipol r -> Unipol r -> (Unipol r, Unipol r)
forall r.
(CoeffRing r, Field r) =>
Unipol r -> Unipol r -> (Unipol r, Unipol r)
divModUnipol Unipol r
f Unipol r
g
      else Unipol r -> Unipol r -> (Unipol r, Unipol r)
forall r.
(Eq r, Field r) =>
Unipol r -> Unipol r -> (Unipol r, Unipol r)
divModUnipolByMult Unipol r
f Unipol r
g
  degree :: Unipol r -> Maybe Natural
degree Unipol r
f = if Unipol r -> Bool
forall r. DecidableZero r => r -> Bool
isZero Unipol r
f then Maybe Natural
forall a. Maybe a
Nothing else Natural -> Maybe Natural
forall a. a -> Maybe a
Just (Int -> Natural
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int -> Natural) -> Int -> Natural
forall a b. (a -> b) -> a -> b
$ Unipol r -> Int
forall poly. IsPolynomial poly => poly -> Int
totalDegree' Unipol r
f)

leadingTermIM :: Monoidal r => Unipol r -> (Int, r)
leadingTermIM :: Unipol r -> (Int, r)
leadingTermIM = (Int, r)
-> (((Int, r), IntMap r) -> (Int, r))
-> Maybe ((Int, r), IntMap r)
-> (Int, r)
forall b a. b -> (a -> b) -> Maybe a -> b
maybe (Int
0, r
forall m. Monoidal m => m
zero) ((Int, r), IntMap r) -> (Int, r)
forall a b. (a, b) -> a
fst (Maybe ((Int, r), IntMap r) -> (Int, r))
-> (Unipol r -> Maybe ((Int, r), IntMap r)) -> Unipol r -> (Int, r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntMap r -> Maybe ((Int, r), IntMap r)
forall a. IntMap a -> Maybe ((Int, a), IntMap a)
IM.maxViewWithKey (IntMap r -> Maybe ((Int, r), IntMap r))
-> (Unipol r -> IntMap r) -> Unipol r -> Maybe ((Int, r), IntMap r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Unipol r -> IntMap r
forall r. Unipol r -> IntMap r
runUnipol
{-# INLINE leadingTermIM #-}

instance CoeffRing r => P.Num (Unipol r) where
  fromInteger :: Integer -> Unipol r
fromInteger = Integer -> Unipol r
forall r. Ring r => Integer -> r
NA.fromInteger
  + :: Unipol r -> Unipol r -> Unipol r
(+) = Unipol r -> Unipol r -> Unipol r
forall r. Additive r => r -> r -> r
(NA.+)
  * :: Unipol r -> Unipol r -> Unipol r
(*) = Unipol r -> Unipol r -> Unipol r
forall r. Multiplicative r => r -> r -> r
(NA.*)
  negate :: Unipol r -> Unipol r
negate = Unipol r -> Unipol r
forall r. Group r => r -> r
NA.negate
  (-) = Unipol r -> Unipol r -> Unipol r
forall r. Group r => r -> r -> r
(NA.-)
  abs :: Unipol r -> Unipol r
abs = Unipol r -> Unipol r
forall a. a -> a
id
  signum :: Unipol r -> Unipol r
signum Unipol r
f =
    if Unipol r -> Bool
forall r. DecidableZero r => r -> Bool
isZero Unipol r
f
      then Unipol r
forall m. Monoidal m => m
zero
      else Unipol r
forall r. Unital r => r
one

varUnipol :: Unital r => Ordinal 1 -> Unipol r
varUnipol :: Ordinal 1 -> Unipol r
varUnipol Ordinal 1
_ = IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol (IntMap r -> Unipol r) -> IntMap r -> Unipol r
forall a b. (a -> b) -> a -> b
$ Int -> r -> IntMap r
forall a. Int -> a -> IntMap a
IM.singleton Int
1 r
forall r. Unital r => r
one
{-# NOINLINE [1] varUnipol #-}

instance (Eq r, DecidableZero r) => Eq (Unipol r) where
  == :: Unipol r -> Unipol r -> Bool
(==) = IntMap r -> IntMap r -> Bool
forall a. Eq a => a -> a -> Bool
(==) (IntMap r -> IntMap r -> Bool)
-> (Unipol r -> IntMap r) -> Unipol r -> Unipol r -> Bool
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` (r -> Bool) -> IntMap r -> IntMap r
forall a. (a -> Bool) -> IntMap a -> IntMap a
IM.filter (Bool -> Bool
not (Bool -> Bool) -> (r -> Bool) -> r -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. r -> Bool
forall r. DecidableZero r => r -> Bool
isZero) (IntMap r -> IntMap r)
-> (Unipol r -> IntMap r) -> Unipol r -> IntMap r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Unipol r -> IntMap r
forall r. Unipol r -> IntMap r
runUnipol
  /= :: Unipol r -> Unipol r -> Bool
(/=) = IntMap r -> IntMap r -> Bool
forall a. Eq a => a -> a -> Bool
(/=) (IntMap r -> IntMap r -> Bool)
-> (Unipol r -> IntMap r) -> Unipol r -> Unipol r -> Bool
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` (r -> Bool) -> IntMap r -> IntMap r
forall a. (a -> Bool) -> IntMap a -> IntMap a
IM.filter (Bool -> Bool
not (Bool -> Bool) -> (r -> Bool) -> r -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. r -> Bool
forall r. DecidableZero r => r -> Bool
isZero) (IntMap r -> IntMap r)
-> (Unipol r -> IntMap r) -> Unipol r -> IntMap r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Unipol r -> IntMap r
forall r. Unipol r -> IntMap r
runUnipol

instance (Ord r, DecidableZero r) => Ord (Unipol r) where
  compare :: Unipol r -> Unipol r -> Ordering
compare = (Unipol r -> IntMap r) -> Unipol r -> Unipol r -> Ordering
forall a b. Ord a => (b -> a) -> b -> b -> Ordering
comparing Unipol r -> IntMap r
forall r. Unipol r -> IntMap r
runUnipol
  < :: Unipol r -> Unipol r -> Bool
(<) = IntMap r -> IntMap r -> Bool
forall a. Ord a => a -> a -> Bool
(<) (IntMap r -> IntMap r -> Bool)
-> (Unipol r -> IntMap r) -> Unipol r -> Unipol r -> Bool
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` Unipol r -> IntMap r
forall r. Unipol r -> IntMap r
runUnipol
  > :: Unipol r -> Unipol r -> Bool
(>) = IntMap r -> IntMap r -> Bool
forall a. Ord a => a -> a -> Bool
(>) (IntMap r -> IntMap r -> Bool)
-> (Unipol r -> IntMap r) -> Unipol r -> Unipol r -> Bool
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` Unipol r -> IntMap r
forall r. Unipol r -> IntMap r
runUnipol
  <= :: Unipol r -> Unipol r -> Bool
(<=) = IntMap r -> IntMap r -> Bool
forall a. Ord a => a -> a -> Bool
(<=) (IntMap r -> IntMap r -> Bool)
-> (Unipol r -> IntMap r) -> Unipol r -> Unipol r -> Bool
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` Unipol r -> IntMap r
forall r. Unipol r -> IntMap r
runUnipol
  >= :: Unipol r -> Unipol r -> Bool
(>=) = IntMap r -> IntMap r -> Bool
forall a. Ord a => a -> a -> Bool
(>=) (IntMap r -> IntMap r -> Bool)
-> (Unipol r -> IntMap r) -> Unipol r -> Unipol r -> Bool
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` Unipol r -> IntMap r
forall r. Unipol r -> IntMap r
runUnipol

-- | Polynomial multiplication, naive version.
naiveMult :: (DecidableZero r, Multiplicative r) => Unipol r -> Unipol r -> Unipol r
naiveMult :: Unipol r -> Unipol r -> Unipol r
naiveMult (Unipol IntMap r
f) (Unipol IntMap r
g) =
  IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol (IntMap r -> Unipol r) -> IntMap r -> Unipol r
forall a b. (a -> b) -> a -> b
$
    (r -> Bool) -> IntMap r -> IntMap r
forall a. (a -> Bool) -> IntMap a -> IntMap a
IM.filter (Bool -> Bool
not (Bool -> Bool) -> (r -> Bool) -> r -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. r -> Bool
forall r. DecidableZero r => r -> Bool
isZero) (IntMap r -> IntMap r) -> IntMap r -> IntMap r
forall a b. (a -> b) -> a -> b
$
      (r -> r -> r) -> [(Int, r)] -> IntMap r
forall a. (a -> a -> a) -> [(Int, a)] -> IntMap a
IM.fromListWith
        r -> r -> r
forall r. Additive r => r -> r -> r
(+)
        [ (Int
n Int -> Int -> Int
forall r. Additive r => r -> r -> r
+ Int
m, r
p r -> r -> r
forall r. Multiplicative r => r -> r -> r
* r
q)
        | (Int
n, r
p) <- IntMap r -> [(Int, r)]
forall a. IntMap a -> [(Int, a)]
IM.toList IntMap r
f
        , (Int
m, r
q) <- IntMap r -> [(Int, r)]
forall a. IntMap a -> [(Int, a)]
IM.toList IntMap r
g
        ]

-- | Polynomial multiplication using Karatsuba's method.
karatsuba :: forall r. CoeffRing r => Unipol r -> Unipol r -> Unipol r
karatsuba :: Unipol r -> Unipol r -> Unipol r
karatsuba Unipol r
f0 Unipol r
g0 =
  let n0 :: Int
n0 = (Unipol r -> Int
forall poly. IsPolynomial poly => poly -> Int
totalDegree' Unipol r
f0 Int -> Int -> Int
forall a. Ord a => a -> a -> a
`max` Unipol r -> Int
forall poly. IsPolynomial poly => poly -> Int
totalDegree' Unipol r
g0) Int -> Int -> Int
forall r. Additive r => r -> r -> r
+ Int
1
      -- The least @m@ such that deg(f), deg(g) <= 2^m - 1.
      m0 :: Natural
m0 = Int -> Natural
forall a. Enum a => Int -> a
toEnum (Int -> Natural) -> Int -> Natural
forall a b. (a -> b) -> a -> b
$ Int -> Int
ceilingLogBase2 Int
n0
   in IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol (IntMap r -> Unipol r) -> IntMap r -> Unipol r
forall a b. (a -> b) -> a -> b
$ Natural -> IntMap r -> IntMap r -> IntMap r
loop Natural
m0 (Unipol r -> IntMap r
forall r. Unipol r -> IntMap r
runUnipol Unipol r
f0) (Unipol r -> IntMap r
forall r. Unipol r -> IntMap r
runUnipol Unipol r
g0)
  where
    linearProduct :: (r -> r -> c) -> (r, r) -> (r, r) -> (c, c, c)
linearProduct r -> r -> c
op (r
a, r
b) (r
c, r
d) =
      let (c
ac, c
bd, c
abdc) = (r
a r -> r -> c
`op` r
c, r
b r -> r -> c
`op` r
d, (r
a r -> r -> r
forall r. Group r => r -> r -> r
- r
b) r -> r -> c
`op` (r
d r -> r -> r
forall r. Group r => r -> r -> r
- r
c))
       in (c
ac, c
abdc c -> c -> c
forall r. Additive r => r -> r -> r
+ c
ac c -> c -> c
forall r. Additive r => r -> r -> r
+ c
bd, c
bd)
    {-# SPECIALIZE INLINE linearProduct ::
      (r -> r -> r) -> (r, r) -> (r, r) -> (r, r, r)
      #-}
    {-# SPECIALIZE INLINE linearProduct ::
      (Unipol r -> Unipol r -> Unipol r) ->
      (Unipol r, Unipol r) ->
      (Unipol r, Unipol r) ->
      (Unipol r, Unipol r, Unipol r)
      #-}

    divideAt :: Int -> IntMap a -> (IntMap a, IntMap a)
divideAt Int
m IntMap a
h =
      let (IntMap a
l, Maybe a
mk, IntMap a
u) = Int -> IntMap a -> (IntMap a, Maybe a, IntMap a)
forall a. Int -> IntMap a -> (IntMap a, Maybe a, IntMap a)
IM.splitLookup Int
m IntMap a
h
       in ((IntMap a -> IntMap a)
-> (a -> IntMap a -> IntMap a) -> Maybe a -> IntMap a -> IntMap a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe IntMap a -> IntMap a
forall a. a -> a
id (Int -> a -> IntMap a -> IntMap a
forall a. Int -> a -> IntMap a -> IntMap a
IM.insert Int
0) Maybe a
mk (IntMap a -> IntMap a) -> IntMap a -> IntMap a
forall a b. (a -> b) -> a -> b
$ (Int -> Int) -> IntMap a -> IntMap a
forall a. (Int -> Int) -> IntMap a -> IntMap a
IM.mapKeysMonotonic (Int -> Int -> Int
forall r. Group r => r -> r -> r
subtract Int
m) IntMap a
u, IntMap a
l)
    {-# INLINE divideAt #-}

    xCoeff :: IntMap r -> r
xCoeff = r -> Int -> IntMap r -> r
forall a. a -> Int -> IntMap a -> a
IM.findWithDefault r
forall m. Monoidal m => m
zero Int
1
    {-# INLINE xCoeff #-}
    cCoeff :: IntMap r -> r
cCoeff = r -> Int -> IntMap r -> r
forall a. a -> Int -> IntMap a -> a
IM.findWithDefault r
forall m. Monoidal m => m
zero Int
0
    {-# INLINE cCoeff #-}

    loop :: Natural -> IntMap r -> IntMap r -> IntMap r
loop !Natural
m !IntMap r
f !IntMap r
g
      | Natural
m Natural -> Natural -> Bool
forall a. Ord a => a -> a -> Bool
<= Natural
1 =
        let (r
a, r
b, r
c) =
              (r -> r -> r) -> (r, r) -> (r, r) -> (r, r, r)
forall r r c.
(Group r, Group r, Additive c) =>
(r -> r -> c) -> (r, r) -> (r, r) -> (c, c, c)
linearProduct
                r -> r -> r
forall r. Multiplicative r => r -> r -> r
(*)
                (IntMap r -> r
xCoeff IntMap r
f, IntMap r -> r
cCoeff IntMap r
f)
                (IntMap r -> r
xCoeff IntMap r
g, IntMap r -> r
cCoeff IntMap r
g)
         in [(Int, r)] -> IntMap r
forall a. [(Int, a)] -> IntMap a
IM.fromAscList ([(Int, r)] -> IntMap r) -> [(Int, r)] -> IntMap r
forall a b. (a -> b) -> a -> b
$
              ((Int, r) -> Bool) -> [(Int, r)] -> [(Int, r)]
forall a. (a -> Bool) -> [a] -> [a]
filter
                (Bool -> Bool
not (Bool -> Bool) -> ((Int, r) -> Bool) -> (Int, r) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. r -> Bool
forall r. DecidableZero r => r -> Bool
isZero (r -> Bool) -> ((Int, r) -> r) -> (Int, r) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int, r) -> r
forall a b. (a, b) -> b
snd)
                [(Int
0, r
c), (Int
1, r
b), (Int
2, r
a)]
      | Bool
otherwise =
        let (IntMap r
f1, IntMap r
f2) = Int -> IntMap r -> (IntMap r, IntMap r)
forall a. Int -> IntMap a -> (IntMap a, IntMap a)
divideAt (Int
2 Int -> Natural -> Int
forall r. Unital r => r -> Natural -> r
^ (Natural
m Natural -> Natural -> Natural
forall a. Num a => a -> a -> a
P.- Natural
1)) IntMap r
f -- f = f1 x^m + f2
            (IntMap r
g1, IntMap r
g2) = Int -> IntMap r -> (IntMap r, IntMap r)
forall a. Int -> IntMap a -> (IntMap a, IntMap a)
divideAt (Int
2 Int -> Natural -> Int
forall r. Unital r => r -> Natural -> r
^ (Natural
m Natural -> Natural -> Natural
forall a. Num a => a -> a -> a
P.- Natural
1)) IntMap r
g -- g = g1 x^m + g2
            (Unipol IntMap r
m2, Unipol IntMap r
m1, Unipol IntMap r
c) =
              (Unipol r -> Unipol r -> Unipol r)
-> (Unipol r, Unipol r)
-> (Unipol r, Unipol r)
-> (Unipol r, Unipol r, Unipol r)
forall r r c.
(Group r, Group r, Additive c) =>
(r -> r -> c) -> (r, r) -> (r, r) -> (c, c, c)
linearProduct
                ((IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol (IntMap r -> Unipol r)
-> (IntMap r -> IntMap r) -> IntMap r -> Unipol r
forall b c a. (b -> c) -> (a -> b) -> a -> c
.) ((IntMap r -> IntMap r) -> IntMap r -> Unipol r)
-> (IntMap r -> IntMap r -> IntMap r)
-> IntMap r
-> IntMap r
-> Unipol r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Natural -> IntMap r -> IntMap r -> IntMap r
loop (Natural
m Natural -> Natural -> Natural
forall a. Num a => a -> a -> a
P.- Natural
1) (IntMap r -> IntMap r -> Unipol r)
-> (Unipol r -> IntMap r) -> Unipol r -> Unipol r -> Unipol r
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` Unipol r -> IntMap r
forall r. Unipol r -> IntMap r
runUnipol)
                (IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol IntMap r
f1, IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol IntMap r
f2)
                (IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol IntMap r
g1, IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol IntMap r
g2)
         in (IntMap r -> IntMap r -> IntMap r) -> [IntMap r] -> IntMap r
forall a. (a -> a -> a) -> [a] -> a
foldl1'
              ((Int -> r -> r -> Maybe r)
-> (IntMap r -> IntMap r)
-> (IntMap r -> IntMap r)
-> IntMap r
-> IntMap r
-> IntMap r
forall a b c.
(Int -> a -> b -> Maybe c)
-> (IntMap a -> IntMap c)
-> (IntMap b -> IntMap c)
-> IntMap a
-> IntMap b
-> IntMap c
IM.mergeWithKey (\Int
_ r
i r
j -> r -> Maybe r
forall r. DecidableZero r => r -> Maybe r
decZero (r
i r -> r -> r
forall r. Additive r => r -> r -> r
+ r
j)) IntMap r -> IntMap r
forall a. a -> a
id IntMap r -> IntMap r
forall a. a -> a
id)
              [ (Int -> Int) -> IntMap r -> IntMap r
forall a. (Int -> Int) -> IntMap a -> IntMap a
IM.mapKeysMonotonic (Int
2 Int -> Natural -> Int
forall r. Unital r => r -> Natural -> r
^ Natural
m Int -> Int -> Int
forall r. Additive r => r -> r -> r
+) IntMap r
m2
              , (Int -> Int) -> IntMap r -> IntMap r
forall a. (Int -> Int) -> IntMap a -> IntMap a
IM.mapKeysMonotonic (Int
2 Int -> Natural -> Int
forall r. Unital r => r -> Natural -> r
^ (Natural
m Natural -> Natural -> Natural
forall a. Num a => a -> a -> a
P.- Natural
1) Int -> Int -> Int
forall r. Additive r => r -> r -> r
+) IntMap r
m1
              , IntMap r
c
              ]
{-# INLINEABLE karatsuba #-}

decZero :: DecidableZero r => r -> Maybe r
decZero :: r -> Maybe r
decZero r
r = if r -> Bool
forall r. DecidableZero r => r -> Bool
isZero r
r then Maybe r
forall a. Maybe a
Nothing else r -> Maybe r
forall a. a -> Maybe a
Just r
r

instance (DecidableZero r) => Additive (Unipol r) where
  Unipol IntMap r
f + :: Unipol r -> Unipol r -> Unipol r
+ Unipol IntMap r
g =
    IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol (IntMap r -> Unipol r) -> IntMap r -> Unipol r
forall a b. (a -> b) -> a -> b
$ (Int -> r -> r -> Maybe r)
-> (IntMap r -> IntMap r)
-> (IntMap r -> IntMap r)
-> IntMap r
-> IntMap r
-> IntMap r
forall a b c.
(Int -> a -> b -> Maybe c)
-> (IntMap a -> IntMap c)
-> (IntMap b -> IntMap c)
-> IntMap a
-> IntMap b
-> IntMap c
IM.mergeWithKey (\Int
_ r
a r
b -> r -> Maybe r
forall r. DecidableZero r => r -> Maybe r
decZero (r
a r -> r -> r
forall r. Additive r => r -> r -> r
+ r
b)) IntMap r -> IntMap r
forall a. a -> a
id IntMap r -> IntMap r
forall a. a -> a
id IntMap r
f IntMap r
g

instance (DecidableZero r, Abelian r) => Abelian (Unipol r)

instance (DecidableZero r, RightModule Natural r) => RightModule Natural (Unipol r) where
  Unipol IntMap r
r *. :: Unipol r -> Natural -> Unipol r
*. Natural
n = IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol (IntMap r -> Unipol r) -> IntMap r -> Unipol r
forall a b. (a -> b) -> a -> b
$ (r -> Maybe r) -> IntMap r -> IntMap r
forall a b. (a -> Maybe b) -> IntMap a -> IntMap b
IM.mapMaybe (r -> Maybe r
forall r. DecidableZero r => r -> Maybe r
decZero (r -> Maybe r) -> (r -> r) -> r -> Maybe r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (r -> Natural -> r
forall r m. RightModule r m => m -> r -> m
*. Natural
n)) IntMap r
r

instance (DecidableZero r, LeftModule Natural r) => LeftModule Natural (Unipol r) where
  Natural
n .* :: Natural -> Unipol r -> Unipol r
.* Unipol IntMap r
r = IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol (IntMap r -> Unipol r) -> IntMap r -> Unipol r
forall a b. (a -> b) -> a -> b
$ (r -> Maybe r) -> IntMap r -> IntMap r
forall a b. (a -> Maybe b) -> IntMap a -> IntMap b
IM.mapMaybe (r -> Maybe r
forall r. DecidableZero r => r -> Maybe r
decZero (r -> Maybe r) -> (r -> r) -> r -> Maybe r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Natural
n Natural -> r -> r
forall r m. LeftModule r m => r -> m -> m
.*)) IntMap r
r

instance (DecidableZero r, RightModule Integer r) => RightModule Integer (Unipol r) where
  Unipol IntMap r
r *. :: Unipol r -> Integer -> Unipol r
*. Integer
n = IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol (IntMap r -> Unipol r) -> IntMap r -> Unipol r
forall a b. (a -> b) -> a -> b
$ (r -> Maybe r) -> IntMap r -> IntMap r
forall a b. (a -> Maybe b) -> IntMap a -> IntMap b
IM.mapMaybe (r -> Maybe r
forall r. DecidableZero r => r -> Maybe r
decZero (r -> Maybe r) -> (r -> r) -> r -> Maybe r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (r -> Integer -> r
forall r m. RightModule r m => m -> r -> m
*. Integer
n)) IntMap r
r

instance (DecidableZero r, LeftModule Integer r) => LeftModule Integer (Unipol r) where
  Integer
n .* :: Integer -> Unipol r -> Unipol r
.* Unipol IntMap r
r = IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol (IntMap r -> Unipol r) -> IntMap r -> Unipol r
forall a b. (a -> b) -> a -> b
$ (r -> Maybe r) -> IntMap r -> IntMap r
forall a b. (a -> Maybe b) -> IntMap a -> IntMap b
IM.mapMaybe (r -> Maybe r
forall r. DecidableZero r => r -> Maybe r
decZero (r -> Maybe r) -> (r -> r) -> r -> Maybe r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Integer
n Integer -> r -> r
forall r m. LeftModule r m => r -> m -> m
.*)) IntMap r
r

instance (CoeffRing r, Multiplicative r) => Multiplicative (Unipol r) where
  Unipol r
f * :: Unipol r -> Unipol r -> Unipol r
* Unipol r
g =
    if Unipol r -> Int
forall poly. IsPolynomial poly => poly -> Int
totalDegree' Unipol r
f Int -> Int -> Int
forall a. Ord a => a -> a -> a
`min` Unipol r -> Int
forall poly. IsPolynomial poly => poly -> Int
totalDegree' Unipol r
g Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
50
      then Unipol r -> Unipol r -> Unipol r
forall r. CoeffRing r => Unipol r -> Unipol r -> Unipol r
karatsuba Unipol r
f Unipol r
g
      else Unipol r
f Unipol r -> Unipol r -> Unipol r
forall r.
(DecidableZero r, Multiplicative r) =>
Unipol r -> Unipol r -> Unipol r
`naiveMult` Unipol r
g

diffIMap :: (DecidableZero r, Group r) => IntMap r -> IntMap r -> IntMap r
diffIMap :: IntMap r -> IntMap r -> IntMap r
diffIMap = (Int -> r -> r -> Maybe r)
-> (IntMap r -> IntMap r)
-> (IntMap r -> IntMap r)
-> IntMap r
-> IntMap r
-> IntMap r
forall a b c.
(Int -> a -> b -> Maybe c)
-> (IntMap a -> IntMap c)
-> (IntMap b -> IntMap c)
-> IntMap a
-> IntMap b
-> IntMap c
IM.mergeWithKey (\Int
_ r
a r
b -> r -> Maybe r
forall r. DecidableZero r => r -> Maybe r
decZero (r
a r -> r -> r
forall r. Group r => r -> r -> r
- r
b)) IntMap r -> IntMap r
forall a. a -> a
id ((r -> r) -> IntMap r -> IntMap r
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap r -> r
forall r. Group r => r -> r
negate)
{-# INLINE diffIMap #-}

instance (DecidableZero r, Group r) => Group (Unipol r) where
  negate :: Unipol r -> Unipol r
negate (Unipol IntMap r
r) = IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol (IntMap r -> Unipol r) -> IntMap r -> Unipol r
forall a b. (a -> b) -> a -> b
$ (r -> r) -> IntMap r -> IntMap r
forall a b. (a -> b) -> IntMap a -> IntMap b
IM.map r -> r
forall r. Group r => r -> r
negate IntMap r
r
  {-# INLINE negate #-}

  Unipol IntMap r
f - :: Unipol r -> Unipol r -> Unipol r
- Unipol IntMap r
g = IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol (IntMap r -> Unipol r) -> IntMap r -> Unipol r
forall a b. (a -> b) -> a -> b
$ IntMap r -> IntMap r -> IntMap r
forall r.
(DecidableZero r, Group r) =>
IntMap r -> IntMap r -> IntMap r
diffIMap IntMap r
f IntMap r
g
  {-# INLINE (-) #-}

instance (CoeffRing r, Unital r) => Unital (Unipol r) where
  one :: Unipol r
one = IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol (IntMap r -> Unipol r) -> IntMap r -> Unipol r
forall a b. (a -> b) -> a -> b
$ Int -> r -> IntMap r
forall a. Int -> a -> IntMap a
IM.singleton Int
0 r
forall r. Unital r => r
one

instance (CoeffRing r, Commutative r) => Commutative (Unipol r)

instance (DecidableZero r, Semiring r) => LeftModule (Scalar r) (Unipol r) where
  Scalar r
q .* :: Scalar r -> Unipol r -> Unipol r
.* Unipol IntMap r
f
    | r -> Bool
forall r. DecidableZero r => r -> Bool
isZero r
q = Unipol r
forall m. Monoidal m => m
zero
    | Bool
otherwise = IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol (IntMap r -> Unipol r) -> IntMap r -> Unipol r
forall a b. (a -> b) -> a -> b
$ (r -> Maybe r) -> IntMap r -> IntMap r
forall a b. (a -> Maybe b) -> IntMap a -> IntMap b
IM.mapMaybe (r -> Maybe r
forall r. DecidableZero r => r -> Maybe r
decZero (r -> Maybe r) -> (r -> r) -> r -> Maybe r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (r
q r -> r -> r
forall r. Multiplicative r => r -> r -> r
*)) IntMap r
f

instance (CoeffRing r, DecidableZero r) => Semiring (Unipol r)

instance (CoeffRing r, DecidableZero r) => Rig (Unipol r) where
  fromNatural :: Natural -> Unipol r
fromNatural Natural
0 = IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol IntMap r
forall a. IntMap a
IM.empty
  fromNatural Natural
n = IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol (IntMap r -> Unipol r) -> IntMap r -> Unipol r
forall a b. (a -> b) -> a -> b
$ Int -> r -> IntMap r
forall a. Int -> a -> IntMap a
IM.singleton Int
0 (Natural -> r
forall r. Rig r => Natural -> r
fromNatural Natural
n)

instance (CoeffRing r, DecidableZero r) => Ring (Unipol r) where
  fromInteger :: Integer -> Unipol r
fromInteger Integer
0 = IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol IntMap r
forall a. IntMap a
IM.empty
  fromInteger Integer
n = IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol (IntMap r -> Unipol r) -> IntMap r -> Unipol r
forall a b. (a -> b) -> a -> b
$ Int -> r -> IntMap r
forall a. Int -> a -> IntMap a
IM.singleton Int
0 (Integer -> r
forall r. Ring r => Integer -> r
fromInteger' Integer
n)

instance (DecidableZero r, Semiring r) => RightModule (Scalar r) (Unipol r) where
  Unipol IntMap r
f *. :: Unipol r -> Scalar r -> Unipol r
*. Scalar r
q
    | r -> Bool
forall r. DecidableZero r => r -> Bool
isZero r
q = Unipol r
forall m. Monoidal m => m
zero
    | Bool
otherwise = IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol (IntMap r -> Unipol r) -> IntMap r -> Unipol r
forall a b. (a -> b) -> a -> b
$ (r -> Maybe r) -> IntMap r -> IntMap r
forall a b. (a -> Maybe b) -> IntMap a -> IntMap b
IM.mapMaybe (r -> Maybe r
forall r. DecidableZero r => r -> Maybe r
decZero (r -> Maybe r) -> (r -> r) -> r -> Maybe r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (r -> r -> r
forall r. Multiplicative r => r -> r -> r
* r
q)) IntMap r
f

instance DecidableZero r => Monoidal (Unipol r) where
  zero :: Unipol r
zero = IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol IntMap r
forall a. IntMap a
IM.empty

instance DecidableZero r => DecidableZero (Unipol r) where
  isZero :: Unipol r -> Bool
isZero = IntMap r -> Bool
forall a. IntMap a -> Bool
IM.null (IntMap r -> Bool) -> (Unipol r -> IntMap r) -> Unipol r -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Unipol r -> IntMap r
forall r. Unipol r -> IntMap r
runUnipol

instance CoeffRing r => IsPolynomial (Unipol r) where
  type Arity (Unipol r) = 1
  type Coefficient (Unipol r) = r
  injectCoeff :: Coefficient (Unipol r) -> Unipol r
injectCoeff Coefficient (Unipol r)
r =
    if r -> Bool
forall r. DecidableZero r => r -> Bool
isZero r
Coefficient (Unipol r)
r
      then Unipol r
forall m. Monoidal m => m
zero
      else IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol (IntMap r -> Unipol r) -> IntMap r -> Unipol r
forall a b. (a -> b) -> a -> b
$ Int -> r -> IntMap r
forall a. Int -> a -> IntMap a
IM.singleton Int
0 r
Coefficient (Unipol r)
r
  {-# INLINE injectCoeff #-}
  coeff' :: Monomial (Arity (Unipol r)) -> Unipol r -> Coefficient (Unipol r)
coeff' Monomial (Arity (Unipol r))
l = r -> Int -> IntMap r -> r
forall a. a -> Int -> IntMap a -> a
IM.findWithDefault r
forall m. Monoidal m => m
zero (Sized Vector 1 Int -> Int
forall (f :: * -> *) (n :: Nat) a.
(CFoldable f, Dom f a, 0 < n) =>
Sized f n a -> a
SV.head Sized Vector 1 Int
Monomial (Arity (Unipol r))
l) (IntMap r -> r) -> (Unipol r -> IntMap r) -> Unipol r -> r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Unipol r -> IntMap r
forall r. Unipol r -> IntMap r
runUnipol
  {-# INLINE coeff' #-}
  monomials :: Unipol r -> HashSet (Monomial (Arity (Unipol r)))
monomials = [Sized Vector 1 Int] -> HashSet (Sized Vector 1 Int)
forall a. (Eq a, Hashable a) => [a] -> HashSet a
HS.fromList ([Sized Vector 1 Int] -> HashSet (Sized Vector 1 Int))
-> (Unipol r -> [Sized Vector 1 Int])
-> Unipol r
-> HashSet (Sized Vector 1 Int)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int -> Sized Vector 1 Int) -> [Int] -> [Sized Vector 1 Int]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
map Int -> Sized Vector 1 Int
forall (f :: * -> *) a. (CPointed f, Dom f a) => a -> Sized f 1 a
singleton ([Int] -> [Sized Vector 1 Int])
-> (Unipol r -> [Int]) -> Unipol r -> [Sized Vector 1 Int]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntMap r -> [Int]
forall a. IntMap a -> [Int]
IM.keys (IntMap r -> [Int]) -> (Unipol r -> IntMap r) -> Unipol r -> [Int]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Unipol r -> IntMap r
forall r. Unipol r -> IntMap r
runUnipol
  {-# INLINE monomials #-}
  terms' :: Unipol r
-> Map (Monomial (Arity (Unipol r))) (Coefficient (Unipol r))
terms' = [(Sized Vector 1 Int, r)] -> Map (Sized Vector 1 Int) r
forall k a. Ord k => [(k, a)] -> Map k a
M.fromList ([(Sized Vector 1 Int, r)] -> Map (Sized Vector 1 Int) r)
-> (Unipol r -> [(Sized Vector 1 Int, r)])
-> Unipol r
-> Map (Sized Vector 1 Int) r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Int, r) -> (Sized Vector 1 Int, r))
-> [(Int, r)] -> [(Sized Vector 1 Int, r)]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
map ((Int -> Sized Vector 1 Int) -> (Int, r) -> (Sized Vector 1 Int, r)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first Int -> Sized Vector 1 Int
forall (f :: * -> *) a. (CPointed f, Dom f a) => a -> Sized f 1 a
singleton) ([(Int, r)] -> [(Sized Vector 1 Int, r)])
-> (Unipol r -> [(Int, r)])
-> Unipol r
-> [(Sized Vector 1 Int, r)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntMap r -> [(Int, r)]
forall a. IntMap a -> [(Int, a)]
IM.toList (IntMap r -> [(Int, r)])
-> (Unipol r -> IntMap r) -> Unipol r -> [(Int, r)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Unipol r -> IntMap r
forall r. Unipol r -> IntMap r
runUnipol
  {-# INLINE terms' #-}
  sArity :: proxy (Unipol r) -> SNat (Arity (Unipol r))
sArity proxy (Unipol r)
_ = SNat (Arity (Unipol r))
forall (n :: Nat). KnownNat n => SNat n
sNat
  sArity' :: Unipol r -> SNat (Arity (Unipol r))
sArity' Unipol r
_ = SNat (Arity (Unipol r))
forall (n :: Nat). KnownNat n => SNat n
sNat
  arity :: proxy (Unipol r) -> Integer
arity proxy (Unipol r)
_ = Integer
1
  constantTerm :: Unipol r -> Coefficient (Unipol r)
constantTerm = r -> Int -> IntMap r -> r
forall a. a -> Int -> IntMap a -> a
IM.findWithDefault r
forall m. Monoidal m => m
zero Int
0 (IntMap r -> r) -> (Unipol r -> IntMap r) -> Unipol r -> r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Unipol r -> IntMap r
forall r. Unipol r -> IntMap r
runUnipol
  {-# INLINE constantTerm #-}
  liftMap :: (Ordinal (Arity (Unipol r)) -> alg) -> Unipol r -> alg
liftMap = (Ordinal (Arity (Unipol r)) -> alg) -> Unipol r -> alg
forall k r.
(Module (Scalar k) r, Monoidal k, Unital r) =>
(Ordinal 1 -> r) -> Unipol k -> r
liftMapUnipol
  {-# INLINEABLE liftMap #-}
  substWith :: (Coefficient (Unipol r) -> m -> m)
-> Sized (Arity (Unipol r)) m -> Unipol r -> m
substWith = (Coefficient (Unipol r) -> m -> m)
-> Sized (Arity (Unipol r)) m -> Unipol r -> m
forall m k.
(Ring m, CoeffRing k) =>
(k -> m -> m) -> Sized 1 m -> Unipol k -> m
substWithUnipol
  {-# INLINE substWith #-}
  fromMonomial :: Monomial (Arity (Unipol r)) -> Unipol r
fromMonomial = IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol (IntMap r -> Unipol r)
-> (Sized Vector 1 Int -> IntMap r)
-> Sized Vector 1 Int
-> Unipol r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int -> r -> IntMap r) -> r -> Int -> IntMap r
forall a b c. (a -> b -> c) -> b -> a -> c
flip Int -> r -> IntMap r
forall a. Int -> a -> IntMap a
IM.singleton r
forall r. Unital r => r
one (Int -> IntMap r)
-> (Sized Vector 1 Int -> Int) -> Sized Vector 1 Int -> IntMap r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Sized Vector 1 Int -> Int
forall (f :: * -> *) (n :: Nat) a.
(CFoldable f, Dom f a, 0 < n) =>
Sized f n a -> a
SV.head
  {-# INLINE fromMonomial #-}
  toPolynomial' :: (Coefficient (Unipol r), Monomial (Arity (Unipol r))) -> Unipol r
toPolynomial' (Coefficient (Unipol r)
c, Monomial (Arity (Unipol r))
m) =
    if r -> Bool
forall r. DecidableZero r => r -> Bool
isZero r
Coefficient (Unipol r)
c
      then IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol IntMap r
forall a. IntMap a
IM.empty
      else IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol (IntMap r -> Unipol r) -> IntMap r -> Unipol r
forall a b. (a -> b) -> a -> b
$ Int -> r -> IntMap r
forall a. Int -> a -> IntMap a
IM.singleton (Sized Vector 1 Int -> Int
forall (f :: * -> *) (n :: Nat) a.
(CFoldable f, Dom f a, 0 < n) =>
Sized f n a -> a
SV.head Sized Vector 1 Int
Monomial (Arity (Unipol r))
m) r
Coefficient (Unipol r)
c
  {-# INLINE toPolynomial' #-}
  polynomial' :: Map (Monomial (Arity (Unipol r))) (Coefficient (Unipol r))
-> Unipol r
polynomial' =
    IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol (IntMap r -> Unipol r)
-> (Map (Sized Vector 1 Int) r -> IntMap r)
-> Map (Sized Vector 1 Int) r
-> Unipol r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(Int, r)] -> IntMap r
forall a. [(Int, a)] -> IntMap a
IM.fromList
      ([(Int, r)] -> IntMap r)
-> (Map (Sized Vector 1 Int) r -> [(Int, r)])
-> Map (Sized Vector 1 Int) r
-> IntMap r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Sized Vector 1 Int, r) -> Maybe (Int, r))
-> [(Sized Vector 1 Int, r)] -> [(Int, r)]
forall a b. (a -> Maybe b) -> [a] -> [b]
mapMaybe (\(Sized Vector 1 Int
s, r
v) -> if r -> Bool
forall r. DecidableZero r => r -> Bool
isZero r
v then Maybe (Int, r)
forall a. Maybe a
Nothing else (Int, r) -> Maybe (Int, r)
forall a. a -> Maybe a
Just (Sized Vector 1 Int -> Int
forall (f :: * -> *) (n :: Nat) a.
(CFoldable f, Dom f a, 0 < n) =>
Sized f n a -> a
SV.head Sized Vector 1 Int
s, r
v))
      ([(Sized Vector 1 Int, r)] -> [(Int, r)])
-> (Map (Sized Vector 1 Int) r -> [(Sized Vector 1 Int, r)])
-> Map (Sized Vector 1 Int) r
-> [(Int, r)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map (Sized Vector 1 Int) r -> [(Sized Vector 1 Int, r)]
forall k a. Map k a -> [(k, a)]
M.toList
  {-# INLINE polynomial' #-}
  totalDegree' :: Unipol r -> Int
totalDegree' = Int
-> (((Int, r), IntMap r) -> Int)
-> Maybe ((Int, r), IntMap r)
-> Int
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Int
0 ((Int, r) -> Int
forall a b. (a, b) -> a
fst ((Int, r) -> Int)
-> (((Int, r), IntMap r) -> (Int, r))
-> ((Int, r), IntMap r)
-> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Int, r), IntMap r) -> (Int, r)
forall a b. (a, b) -> a
fst) (Maybe ((Int, r), IntMap r) -> Int)
-> (Unipol r -> Maybe ((Int, r), IntMap r)) -> Unipol r -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntMap r -> Maybe ((Int, r), IntMap r)
forall a. IntMap a -> Maybe ((Int, a), IntMap a)
IM.maxViewWithKey (IntMap r -> Maybe ((Int, r), IntMap r))
-> (Unipol r -> IntMap r) -> Unipol r -> Maybe ((Int, r), IntMap r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Unipol r -> IntMap r
forall r. Unipol r -> IntMap r
runUnipol
  {-# INLINE totalDegree' #-}
  var :: Ordinal (Arity (Unipol r)) -> Unipol r
var = Ordinal (Arity (Unipol r)) -> Unipol r
forall r. Unital r => Ordinal 1 -> Unipol r
varUnipol
  mapCoeff' :: (Coefficient (Unipol r) -> Coefficient (Unipol r))
-> Unipol r -> Unipol r
mapCoeff' Coefficient (Unipol r) -> Coefficient (Unipol r)
f = IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol (IntMap r -> Unipol r)
-> (Unipol r -> IntMap r) -> Unipol r -> Unipol r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (r -> Maybe r) -> IntMap r -> IntMap r
forall a b. (a -> Maybe b) -> IntMap a -> IntMap b
IM.mapMaybe (r -> Maybe r
forall r. DecidableZero r => r -> Maybe r
decZero (r -> Maybe r) -> (r -> r) -> r -> Maybe r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. r -> r
Coefficient (Unipol r) -> Coefficient (Unipol r)
f) (IntMap r -> IntMap r)
-> (Unipol r -> IntMap r) -> Unipol r -> IntMap r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Unipol r -> IntMap r
forall r. Unipol r -> IntMap r
runUnipol
  {-# INLINE mapCoeff' #-}
  Monomial (Arity (Unipol r))
m >|* :: Monomial (Arity (Unipol r)) -> Unipol r -> Unipol r
>|* Unipol IntMap r
dic =
    let n :: Int
n = Sized Vector 1 Int -> Int
forall (f :: * -> *) (n :: Nat) a.
(CFoldable f, Dom f a, 0 < n) =>
Sized f n a -> a
SV.head Sized Vector 1 Int
Monomial (Arity (Unipol r))
m
     in if Int
n Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0
          then IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol IntMap r
dic
          else IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol (IntMap r -> Unipol r) -> IntMap r -> Unipol r
forall a b. (a -> b) -> a -> b
$ (Int -> Int) -> IntMap r -> IntMap r
forall a. (Int -> Int) -> IntMap a -> IntMap a
IM.mapKeysMonotonic (Int
n Int -> Int -> Int
forall r. Additive r => r -> r -> r
+) IntMap r
dic
  {-# INLINE (>|*) #-}

instance CoeffRing r => IsOrderedPolynomial (Unipol r) where
  type MOrder (Unipol r) = Grevlex
  terms :: Unipol r
-> Map
     (OrderedMonomial (MOrder (Unipol r)) (Arity (Unipol r)))
     (Coefficient (Unipol r))
terms = (Sized Vector 1 Int -> OrderedMonomial Grevlex 1)
-> Map (Sized Vector 1 Int) r -> Map (OrderedMonomial Grevlex 1) r
forall k1 k2 a. (k1 -> k2) -> Map k1 a -> Map k2 a
M.mapKeysMonotonic (Maybe Grevlex -> Sized Vector 1 Int -> OrderedMonomial Grevlex 1
forall k (proxy :: k -> *) (ord :: k) (n :: Nat).
proxy ord -> Monomial n -> OrderedMonomial ord n
orderMonomial (Maybe Grevlex
forall a. Maybe a
Nothing :: Maybe Grevlex)) (Map (Sized Vector 1 Int) r -> Map (OrderedMonomial Grevlex 1) r)
-> (Unipol r -> Map (Sized Vector 1 Int) r)
-> Unipol r
-> Map (OrderedMonomial Grevlex 1) r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Unipol r -> Map (Sized Vector 1 Int) r
forall poly.
IsPolynomial poly =>
poly -> Map (Monomial (Arity poly)) (Coefficient poly)
terms'
  leadingTerm :: Unipol r
-> (Coefficient (Unipol r),
    OrderedMonomial (MOrder (Unipol r)) (Arity (Unipol r)))
leadingTerm =
    (r, OrderedMonomial Grevlex 1)
-> (((Int, r), IntMap r) -> (r, OrderedMonomial Grevlex 1))
-> Maybe ((Int, r), IntMap r)
-> (r, OrderedMonomial Grevlex 1)
forall b a. b -> (a -> b) -> Maybe a -> b
maybe
      (r
forall m. Monoidal m => m
zero, OrderedMonomial Grevlex 1
forall r. Unital r => r
one)
      (\((Int
a, r
b), IntMap r
_) -> (r
b, Sized Vector 1 Int -> OrderedMonomial Grevlex 1
forall k (ordering :: k) (n :: Nat).
Monomial n -> OrderedMonomial ordering n
OrderedMonomial (Sized Vector 1 Int -> OrderedMonomial Grevlex 1)
-> Sized Vector 1 Int -> OrderedMonomial Grevlex 1
forall a b. (a -> b) -> a -> b
$ Int -> Sized Vector 1 Int
forall (f :: * -> *) a. (CPointed f, Dom f a) => a -> Sized f 1 a
SV.singleton Int
a))
      (Maybe ((Int, r), IntMap r) -> (r, OrderedMonomial Grevlex 1))
-> (Unipol r -> Maybe ((Int, r), IntMap r))
-> Unipol r
-> (r, OrderedMonomial Grevlex 1)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntMap r -> Maybe ((Int, r), IntMap r)
forall a. IntMap a -> Maybe ((Int, a), IntMap a)
IM.maxViewWithKey
      (IntMap r -> Maybe ((Int, r), IntMap r))
-> (Unipol r -> IntMap r) -> Unipol r -> Maybe ((Int, r), IntMap r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Unipol r -> IntMap r
forall r. Unipol r -> IntMap r
runUnipol
  {-# INLINE leadingTerm #-}
  splitLeadingTerm :: Unipol r
-> ((Coefficient (Unipol r),
     OrderedMonomial (MOrder (Unipol r)) (Arity (Unipol r))),
    Unipol r)
splitLeadingTerm =
    ((r, OrderedMonomial Grevlex 1), Unipol r)
-> (((Int, r), IntMap r)
    -> ((r, OrderedMonomial Grevlex 1), Unipol r))
-> Maybe ((Int, r), IntMap r)
-> ((r, OrderedMonomial Grevlex 1), Unipol r)
forall b a. b -> (a -> b) -> Maybe a -> b
maybe
      ((r
forall m. Monoidal m => m
zero, OrderedMonomial Grevlex 1
forall r. Unital r => r
one), Unipol r
forall m. Monoidal m => m
zero)
      (\((Int
a, r
b), IntMap r
d) -> ((r
b, Sized Vector 1 Int -> OrderedMonomial Grevlex 1
forall k (ordering :: k) (n :: Nat).
Monomial n -> OrderedMonomial ordering n
OrderedMonomial (Sized Vector 1 Int -> OrderedMonomial Grevlex 1)
-> Sized Vector 1 Int -> OrderedMonomial Grevlex 1
forall a b. (a -> b) -> a -> b
$ Int -> Sized Vector 1 Int
forall (f :: * -> *) a. (CPointed f, Dom f a) => a -> Sized f 1 a
SV.singleton Int
a), IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol IntMap r
d))
      (Maybe ((Int, r), IntMap r)
 -> ((r, OrderedMonomial Grevlex 1), Unipol r))
-> (Unipol r -> Maybe ((Int, r), IntMap r))
-> Unipol r
-> ((r, OrderedMonomial Grevlex 1), Unipol r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntMap r -> Maybe ((Int, r), IntMap r)
forall a. IntMap a -> Maybe ((Int, a), IntMap a)
IM.maxViewWithKey
      (IntMap r -> Maybe ((Int, r), IntMap r))
-> (Unipol r -> IntMap r) -> Unipol r -> Maybe ((Int, r), IntMap r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Unipol r -> IntMap r
forall r. Unipol r -> IntMap r
runUnipol
  {-# INLINE splitLeadingTerm #-}
  diff :: Ordinal (Arity (Unipol r)) -> Unipol r -> Unipol r
diff Ordinal (Arity (Unipol r))
_ =
    IntMap r -> Unipol r
forall r. IntMap r -> Unipol r
Unipol
      (IntMap r -> Unipol r)
-> (Unipol r -> IntMap r) -> Unipol r -> Unipol r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int -> Int) -> IntMap r -> IntMap r
forall a. (Int -> Int) -> IntMap a -> IntMap a
IM.mapKeysMonotonic Int -> Int
forall a. Enum a => a -> a
pred
      (IntMap r -> IntMap r)
-> (Unipol r -> IntMap r) -> Unipol r -> IntMap r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int -> r -> Maybe r) -> IntMap r -> IntMap r
forall a b. (Int -> a -> Maybe b) -> IntMap a -> IntMap b
IM.mapMaybeWithKey
        (\Int
i r
c -> Bool -> Maybe ()
forall (f :: * -> *). Alternative f => Bool -> f ()
guard (Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0) Maybe () -> Maybe r -> Maybe r
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> r -> Maybe r
forall r. DecidableZero r => r -> Maybe r
decZero (Int -> Integer
forall a. Integral a => a -> Integer
toInteger Int
i Integer -> r -> r
forall r m. LeftModule r m => r -> m -> m
.* r
c))
      (IntMap r -> IntMap r)
-> (Unipol r -> IntMap r) -> Unipol r -> IntMap r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Unipol r -> IntMap r
forall r. Unipol r -> IntMap r
runUnipol
  {-# INLINE diff #-}

instance (CoeffRing r, PrettyCoeff r) => Show (Unipol r) where
  showsPrec :: Int -> Unipol r -> ShowS
showsPrec = Sized (Arity (Unipol r)) [Char] -> Int -> Unipol r -> ShowS
forall poly.
(IsOrderedPolynomial poly, PrettyCoeff (Coefficient poly)) =>
Sized (Arity poly) [Char] -> Int -> poly -> ShowS
showsPolynomialWith ([Char] -> Sized Vector 1 [Char]
forall (f :: * -> *) a. (CPointed f, Dom f a) => a -> Sized f 1 a
SV.singleton [Char]
"x")

mapCoeffUnipol :: DecidableZero b => (a -> b) -> Unipol a -> Unipol b
mapCoeffUnipol :: (a -> b) -> Unipol a -> Unipol b
mapCoeffUnipol a -> b
f (Unipol IntMap a
a) =
  IntMap b -> Unipol b
forall r. IntMap r -> Unipol r
Unipol (IntMap b -> Unipol b) -> IntMap b -> Unipol b
forall a b. (a -> b) -> a -> b
$ (a -> Maybe b) -> IntMap a -> IntMap b
forall a b. (a -> Maybe b) -> IntMap a -> IntMap b
IM.mapMaybe (b -> Maybe b
forall r. DecidableZero r => r -> Maybe r
decZero (b -> Maybe b) -> (a -> b) -> a -> Maybe b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> b
f) IntMap a
a
{-# INLINE mapCoeffUnipol #-}

liftMapUnipol ::
  (Module (Scalar k) r, Monoidal k, Unital r) =>
  (Ordinal 1 -> r) ->
  Unipol k ->
  r
liftMapUnipol :: (Ordinal 1 -> r) -> Unipol k -> r
liftMapUnipol Ordinal 1 -> r
g f :: Unipol k
f@(Unipol IntMap k
dic) =
  let u :: r
u = Ordinal 1 -> r
g Ordinal 1
0
      n :: Int
n = Int
-> (((Int, k), IntMap k) -> Int)
-> Maybe ((Int, k), IntMap k)
-> Int
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Int
0 ((Int, k) -> Int
forall a b. (a, b) -> a
fst ((Int, k) -> Int)
-> (((Int, k), IntMap k) -> (Int, k))
-> ((Int, k), IntMap k)
-> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Int, k), IntMap k) -> (Int, k)
forall a b. (a, b) -> a
fst) (Maybe ((Int, k), IntMap k) -> Int)
-> Maybe ((Int, k), IntMap k) -> Int
forall a b. (a -> b) -> a -> b
$ IntMap k -> Maybe ((Int, k), IntMap k)
forall a. IntMap a -> Maybe ((Int, a), IntMap a)
IM.maxViewWithKey (IntMap k -> Maybe ((Int, k), IntMap k))
-> IntMap k -> Maybe ((Int, k), IntMap k)
forall a b. (a -> b) -> a -> b
$ Unipol k -> IntMap k
forall r. Unipol r -> IntMap r
runUnipol Unipol k
f
   in (k -> r -> r) -> r -> [k] -> r
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr
        (\k
a r
b -> k
a k -> r -> r
forall r m. Module (Scalar r) m => r -> m -> m
.*. r
forall r. Unital r => r
one r -> r -> r
forall r. Additive r => r -> r -> r
+ r
b r -> r -> r
forall r. Multiplicative r => r -> r -> r
* r
u)
        (k -> Int -> IntMap k -> k
forall a. a -> Int -> IntMap a -> a
IM.findWithDefault k
forall m. Monoidal m => m
zero Int
n IntMap k
dic k -> r -> r
forall r m. Module (Scalar r) m => r -> m -> m
.*. r
forall r. Unital r => r
one)
        [k -> Int -> IntMap k -> k
forall a. a -> Int -> IntMap a -> a
IM.findWithDefault k
forall m. Monoidal m => m
zero Int
k IntMap k
dic | Int
k <- [Int
0 .. Int
n Int -> Int -> Int
forall r. Group r => r -> r -> r
-Int
1]]
{-# INLINE liftMapUnipol #-}

substWithUnipol ::
  (Ring m, CoeffRing k) =>
  (k -> m -> m) ->
  Sized 1 m ->
  Unipol k ->
  m
substWithUnipol :: (k -> m -> m) -> Sized 1 m -> Unipol k -> m
substWithUnipol k -> m -> m
(|*) Sized 1 m
g f :: Unipol k
f@(Unipol IntMap k
dic) =
  let u :: m
u = Sized 1 m
g Sized 1 m -> Ordinal 1 -> m
forall (f :: * -> *) (n :: Nat) c.
(CFoldable f, Dom f c) =>
Sized f n c -> Ordinal n -> c
SV.%!! Ordinal 1
0
      n :: Int
n = Int
-> (((Int, k), IntMap k) -> Int)
-> Maybe ((Int, k), IntMap k)
-> Int
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Int
0 ((Int, k) -> Int
forall a b. (a, b) -> a
fst ((Int, k) -> Int)
-> (((Int, k), IntMap k) -> (Int, k))
-> ((Int, k), IntMap k)
-> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Int, k), IntMap k) -> (Int, k)
forall a b. (a, b) -> a
fst) (Maybe ((Int, k), IntMap k) -> Int)
-> Maybe ((Int, k), IntMap k) -> Int
forall a b. (a -> b) -> a -> b
$ IntMap k -> Maybe ((Int, k), IntMap k)
forall a. IntMap a -> Maybe ((Int, a), IntMap a)
IM.maxViewWithKey (IntMap k -> Maybe ((Int, k), IntMap k))
-> IntMap k -> Maybe ((Int, k), IntMap k)
forall a b. (a -> b) -> a -> b
$ Unipol k -> IntMap k
forall r. Unipol r -> IntMap r
runUnipol Unipol k
f
   in (k -> m -> m) -> m -> [k] -> m
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr
        (\k
a m
b -> (k
a k -> m -> m
|* m
forall r. Unital r => r
one) m -> m -> m
forall r. Additive r => r -> r -> r
+ (m
b m -> m -> m
forall r. Multiplicative r => r -> r -> r
* m
u))
        (k -> Int -> IntMap k -> k
forall a. a -> Int -> IntMap a -> a
IM.findWithDefault k
forall m. Monoidal m => m
zero Int
n IntMap k
dic k -> m -> m
|* m
forall r. Unital r => r
one)
        [k -> Int -> IntMap k -> k
forall a. a -> Int -> IntMap a -> a
IM.findWithDefault k
forall m. Monoidal m => m
zero Int
k IntMap k
dic | Int
k <- [Int
0 .. Int
n Int -> Int -> Int
forall r. Group r => r -> r -> r
-Int
1]]
{-# INLINE substWithUnipol #-}

-- | The list of coefficients, in ascending order.
coeffList :: Monoidal k => Unipol k -> [k]
coeffList :: Unipol k -> [k]
coeffList (Unipol IntMap k
dic) =
  IntMap k -> [k]
forall (t :: * -> *) a. Foldable t => t a -> [a]
F.toList (IntMap k -> [k]) -> IntMap k -> [k]
forall a b. (a -> b) -> a -> b
$
    (k -> k -> k) -> IntMap k -> IntMap k -> IntMap k
forall a. (a -> a -> a) -> IntMap a -> IntMap a -> IntMap a
IM.unionWith k -> k -> k
forall r. Additive r => r -> r -> r
(+) IntMap k
dic (IntMap k -> IntMap k) -> IntMap k -> IntMap k
forall a b. (a -> b) -> a -> b
$
      [(Int, k)] -> IntMap k
forall a. [(Int, a)] -> IntMap a
IM.fromList [(Int
n, k
forall m. Monoidal m => m
zero) | Int
n <- [Int
0 .. Int
-> (((Int, k), IntMap k) -> Int)
-> Maybe ((Int, k), IntMap k)
-> Int
forall b a. b -> (a -> b) -> Maybe a -> b
maybe (- Int
1) ((Int, k) -> Int
forall a b. (a, b) -> a
fst ((Int, k) -> Int)
-> (((Int, k), IntMap k) -> (Int, k))
-> ((Int, k), IntMap k)
-> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Int, k), IntMap k) -> (Int, k)
forall a b. (a, b) -> a
fst) (IntMap k -> Maybe ((Int, k), IntMap k)
forall a. IntMap a -> Maybe ((Int, a), IntMap a)
IM.maxViewWithKey IntMap k
dic)]]

{- | @'cutoff m f@ gives the polynomial \(f\) but with terms
   degree strictly less than \(m\); i.e. \(\sum_{0 \leq i < m} a_i X^i\) for
   \(f = \sum_{i = 0}^n a_n X^n\).
-}
cutoff :: forall k. Natural -> Unipol k -> Unipol k
cutoff :: Natural -> Unipol k -> Unipol k
cutoff Natural
n = (IntMap k -> IntMap k) -> Unipol k -> Unipol k
C.coerce ((IntMap k, IntMap k) -> IntMap k
forall a b. (a, b) -> a
fst ((IntMap k, IntMap k) -> IntMap k)
-> (IntMap k -> (IntMap k, IntMap k)) -> IntMap k -> IntMap k
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> IntMap k -> (IntMap k, IntMap k)
forall a. Int -> IntMap a -> (IntMap a, IntMap a)
IM.split (Natural -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Natural
n) :: IM.IntMap k -> IM.IntMap k)

termsUnipol ::
  Unipol k -> IM.IntMap k
termsUnipol :: Unipol k -> IntMap k
termsUnipol = Unipol k -> IntMap k
C.coerce