{-# LANGUAGE BangPatterns, ConstraintKinds, DataKinds, ExplicitNamespaces  #-}
{-# LANGUAGE TypeApplications #-}
{-# LANGUAGE FlexibleContexts, FlexibleInstances, GADTs                    #-}
{-# LANGUAGE LiberalTypeSynonyms, MultiParamTypeClasses, NoImplicitPrelude #-}
{-# LANGUAGE ParallelListComp, PolyKinds, RankNTypes, ScopedTypeVariables  #-}
{-# LANGUAGE TypeFamilies, TypeOperators, UndecidableInstances             #-}
{-# OPTIONS_GHC -fplugin Data.Type.Natural.Presburger.MinMaxSolver #-}
-- | This module provides abstract classes for finitary polynomial types.
module Algebra.Ring.Polynomial.Class
       ( IsPolynomial(..), IsOrderedPolynomial(..)
       , Term, OMonom
       , substCoeff, liftMapCoeff
       , CoeffRing, oneNorm, maxNorm, monoize,
         sPolynomial, pDivModPoly, content, pp,
         injectVars, injectVarsAtEnd, injectVarsOffset, vars,
         PrettyCoeff(..), ShowSCoeff(..),
         showsCoeffAsTerm, showsCoeffWithOp,
         showsPolynomialWith, showsPolynomialWith',
         showPolynomialWith, showPolynomialWith',
         -- * Polynomial division
         divModPolynomial, divPolynomial, modPolynomial,
         -- * Conversion between polynomial types
         convertPolynomial, convertPolynomial', mapPolynomial,
         -- * Default instances
         isUnitDefault, recipUnitDefault, isAssociateDefault
       , splitUnitDefault
       ) where
import           Algebra.Internal
import           Algebra.Normed
import           Algebra.Ring.Polynomial.Monomial
import           Algebra.Scalar
import           AlgebraicPrelude
import           Control.Lens                     (Iso', folded, ifoldMap, iso,
                                                   ix, maximumOf, (%~),
                                                   _Wrapped)
import qualified Data.Foldable                    as F
import qualified Data.HashSet                     as HS
import           Data.Int
import           Data.Kind                        (Type)
import qualified Data.List                        as L
import qualified Data.Map.Strict                  as M
import           Data.Maybe                       (fromJust)
import           Data.Monoid                      (First (..))
import           Data.MonoTraversable
import qualified Data.Ratio                       as R
import qualified Data.Set                         as S
import qualified Data.Sized               as V
import           Data.Vector.Instances            ()
import           Data.Word
import qualified Numeric.Algebra.Complex          as NA
import qualified Numeric.Field.Fraction           as NA
import qualified Numeric.Ring.Class               as NA
import qualified Prelude                          as P
import Data.Type.Natural.Lemma.Order (lneqSuccLeq, leqTrans, lneqToLT, minusPlus, plusMonotoneR)
import Data.Type.Natural.Lemma.Arithmetic (plusSuccR)

infixl 7 *<, >*, *|<, >|*, !*

-- | Constraint synonym for rings that can be used as polynomial coefficient.
class    (DecidableZero r, Ring r, Commutative r, Eq r, Module (Scalar r) (Scalar r)) => CoeffRing r
instance (DecidableZero r, Ring r, Commutative r, Eq r) => CoeffRing r

-- | Polynomial in terms of free associative commutative algebra generated
--   by n-elements.
--   To effectively compute all terms, we need @'monomials'@ in addition to
--   universality of free object.
class (CoeffRing (Coefficient poly), Eq poly, DecidableZero poly, KnownNat (Arity poly),
       Module (Scalar (Coefficient poly)) poly, Ring poly, Commutative poly)
   => IsPolynomial poly where
  {-# MINIMAL ((liftMap , monomials) | terms'), (sArity | sArity') , (fromMonomial | toPolynomial' | polynomial') #-}
  -- | Coefficient ring of polynomial type.
  type Coefficient poly :: Type
  -- | Arity of polynomial type.
  type Arity poly :: Nat

  -- | Universal mapping for free algebra.
  --   This corresponds to the algebraic substitution operation.
  liftMap :: (Module (Scalar (Coefficient poly)) alg, Ring alg, Commutative alg)
           => (Ordinal (Arity poly) -> alg) -> poly -> alg
  liftMap Ordinal (Arity poly) -> alg
mor poly
f =
    [alg] -> alg
forall (f :: * -> *) m. (Foldable f, Monoidal m) => f m -> m
sum [ Coefficient poly -> Scalar (Coefficient poly)
forall r. r -> Scalar r
Scalar Coefficient poly
r Scalar (Coefficient poly) -> alg -> alg
forall r m. LeftModule r m => r -> m -> m
.* [alg] -> alg
forall (f :: * -> *) m. (Foldable f, Monoidal m) => f m -> m
sum [ Coefficient poly -> Scalar (Coefficient poly)
forall r. r -> Scalar r
Scalar (Integer -> Coefficient poly
forall r. Ring r => Integer -> r
fromInteger' (Int -> Integer
forall a b. (Integral a, Num b) => a -> b
P.fromIntegral Int
i) :: Coefficient poly) Scalar (Coefficient poly) -> alg -> alg
forall r m. LeftModule r m => r -> m -> m
.* Ordinal (Arity poly) -> alg
mor Ordinal (Arity poly)
o
                          | Int
i <- Monomial (Arity poly) -> [Element (Monomial (Arity poly))]
forall mono. MonoFoldable mono => mono -> [Element mono]
otoList (Monomial (Arity poly)
m :: Monomial (Arity poly)) :: [Int]
                          | Ordinal (Arity poly)
o <- SNat (Arity poly) -> [Ordinal (Arity poly)]
forall (n :: Nat). SNat n -> [Ordinal n]
enumOrdinal (Maybe poly -> SNat (Arity poly)
forall poly (proxy :: * -> *).
IsPolynomial poly =>
proxy poly -> SNat (Arity poly)
sArity (Maybe poly
forall a. Maybe a
Nothing :: Maybe poly)) ]
        | (Monomial (Arity poly)
m, Coefficient poly
r) <- Map (Monomial (Arity poly)) (Coefficient poly)
-> [(Monomial (Arity poly), Coefficient poly)]
forall k a. Map k a -> [(k, a)]
M.toList (poly -> Map (Monomial (Arity poly)) (Coefficient poly)
forall poly.
IsPolynomial poly =>
poly -> Map (Monomial (Arity poly)) (Coefficient poly)
terms' poly
f) ]
  {-# INLINE liftMap #-}

  -- | A variant of @'liftMap'@, each value is given by @'Sized'@.
  subst :: (Ring alg, Commutative alg, Module (Scalar (Coefficient poly)) alg)
        => Sized (Arity poly) alg -> poly -> alg
  subst Sized (Arity poly) alg
dic = (Ordinal (Arity poly) -> alg) -> poly -> alg
forall poly alg.
(IsPolynomial poly, Module (Scalar (Coefficient poly)) alg,
 Ring alg, Commutative alg) =>
(Ordinal (Arity poly) -> alg) -> poly -> alg
liftMap (Sized (Arity poly) alg
dic Sized (Arity poly) alg -> Ordinal (Arity poly) -> alg
forall (f :: * -> *) (n :: Nat) c.
(CFoldable f, Dom f c) =>
Sized f n c -> Ordinal n -> c
V.%!!)
  {-# INLINE subst #-}

  -- | Another variant of @'liftMap'@.
  --   This function relies on @'terms''@; if you have more efficient implementation,
  --   it is encouraged to override this method.
  --
  --   Since 0.6.0.0
  substWith :: forall m. (Ring m)
            => (Coefficient poly -> m -> m) -> Sized (Arity poly) m -> poly -> m
  substWith Coefficient poly -> m -> m
o Sized (Arity poly) m
pt poly
poly =
    Add m -> m
forall a. Add a -> a
runAdd (Add m -> m) -> Add m -> m
forall a b. (a -> b) -> a -> b
$ (Monomial (Arity poly) -> Coefficient poly -> Add m)
-> Map (Monomial (Arity poly)) (Coefficient poly) -> Add m
forall i (f :: * -> *) m a.
(FoldableWithIndex i f, Monoid m) =>
(i -> a -> m) -> f a -> m
ifoldMap ((m -> Add m
forall a. a -> Add a
Add (m -> Add m)
-> (Coefficient poly -> m) -> Coefficient poly -> Add m
forall b c a. (b -> c) -> (a -> b) -> a -> c
.) ((Coefficient poly -> m) -> Coefficient poly -> Add m)
-> (Monomial (Arity poly) -> Coefficient poly -> m)
-> Monomial (Arity poly)
-> Coefficient poly
-> Add m
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Coefficient poly -> m -> m) -> m -> Coefficient poly -> m
forall a b c. (a -> b -> c) -> b -> a -> c
flip Coefficient poly -> m -> m
o (m -> Coefficient poly -> m)
-> (Monomial (Arity poly) -> m)
-> Monomial (Arity poly)
-> Coefficient poly
-> m
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Monomial (Arity poly) -> m
extractPower) (Map (Monomial (Arity poly)) (Coefficient poly) -> Add m)
-> Map (Monomial (Arity poly)) (Coefficient poly) -> Add m
forall a b. (a -> b) -> a -> b
$ poly -> Map (Monomial (Arity poly)) (Coefficient poly)
forall poly.
IsPolynomial poly =>
poly -> Map (Monomial (Arity poly)) (Coefficient poly)
terms' poly
poly
    where
      extractPower :: Monomial (Arity poly) -> m
      extractPower :: Monomial (Arity poly) -> m
extractPower = Mult m -> m
forall a. Mult a -> a
runMult (Mult m -> m)
-> (Monomial (Arity poly) -> Mult m) -> Monomial (Arity poly) -> m
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Ordinal (Arity poly) -> Int -> Mult m)
-> Monomial (Arity poly) -> Mult m
forall (n :: Nat) m.
(KnownNat n, Monoid m) =>
(Ordinal n -> Int -> m) -> Monomial n -> m
ifoldMapMonom (\Ordinal (Arity poly)
k Int
n -> m -> Mult m
forall a. a -> Mult a
Mult (m -> Natural -> m
forall r. Unital r => r -> Natural -> r
pow (Sized (Arity poly) m
pt Sized (Arity poly) m -> Ordinal (Arity poly) -> m
forall (f :: * -> *) (n :: Nat) c.
(CFoldable f, Dom f c) =>
Sized f n c -> Ordinal n -> c
V.%!! Ordinal (Arity poly)
k) (Int -> Natural
forall a b. (Integral a, Num b) => a -> b
P.fromIntegral Int
n)))
  {-# INLINE substWith #-}

  -- | Arity of given polynomial.
  sArity' :: poly -> SNat (Arity poly)
  sArity' = Maybe poly -> SNat (Arity poly)
forall poly (proxy :: * -> *).
IsPolynomial poly =>
proxy poly -> SNat (Arity poly)
sArity (Maybe poly -> SNat (Arity poly))
-> (poly -> Maybe poly) -> poly -> SNat (Arity poly)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. poly -> Maybe poly
forall a. a -> Maybe a
Just

  -- | Arity of given polynomial, using type proxy.
  sArity :: proxy poly -> SNat (Arity poly)
  sArity proxy poly
_ = poly -> SNat (Arity poly)
forall poly. IsPolynomial poly => poly -> SNat (Arity poly)
sArity' (poly
forall m. Monoidal m => m
zero :: poly)
  {-# INLINE sArity #-}

  -- | Non-dependent version of arity.
  arity :: proxy poly -> P.Integer
  arity proxy poly
_pxy = Natural -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Natural -> Integer) -> Natural -> Integer
forall a b. (a -> b) -> a -> b
$ SNat (Arity poly) -> Natural
forall (n :: Nat). SNat n -> Natural
toNatural (SNat (Arity poly) -> Natural) -> SNat (Arity poly) -> Natural
forall a b. (a -> b) -> a -> b
$ poly -> SNat (Arity poly)
forall poly. IsPolynomial poly => poly -> SNat (Arity poly)
sArity' (poly
forall m. Monoidal m => m
zero :: poly)
  {-# INLINE arity #-}

  -- | Inject coefficient into polynomial.
  injectCoeff :: Coefficient poly -> poly
  injectCoeff Coefficient poly
r = Coefficient poly -> Scalar (Coefficient poly)
forall r. r -> Scalar r
Scalar Coefficient poly
r Scalar (Coefficient poly) -> poly -> poly
forall r m. LeftModule r m => r -> m -> m
.* poly
forall r. Unital r => r
one
  {-# INLINE injectCoeff #-}

  -- | Inject coefficient into polynomial with result-type explicitly given.
  injectCoeff' :: proxy poly -> Coefficient poly -> poly
  injectCoeff' proxy poly
_ = Coefficient poly -> poly
forall poly. IsPolynomial poly => Coefficient poly -> poly
injectCoeff
  {-# INLINE injectCoeff' #-}

  -- | @'monomials' f@ returns the finite set of all monomials appearing in @f@.
  monomials :: poly -> HS.HashSet (Monomial (Arity poly))
  monomials = [Monomial (Arity poly)] -> HashSet (Monomial (Arity poly))
forall a. (Eq a, Hashable a) => [a] -> HashSet a
HS.fromList ([Monomial (Arity poly)] -> HashSet (Monomial (Arity poly)))
-> (poly -> [Monomial (Arity poly)])
-> poly
-> HashSet (Monomial (Arity poly))
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map (Monomial (Arity poly)) (Coefficient poly)
-> [Monomial (Arity poly)]
forall k a. Map k a -> [k]
M.keys (Map (Monomial (Arity poly)) (Coefficient poly)
 -> [Monomial (Arity poly)])
-> (poly -> Map (Monomial (Arity poly)) (Coefficient poly))
-> poly
-> [Monomial (Arity poly)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. poly -> Map (Monomial (Arity poly)) (Coefficient poly)
forall poly.
IsPolynomial poly =>
poly -> Map (Monomial (Arity poly)) (Coefficient poly)
terms'
  {-# INLINE monomials #-}

  -- | @'monomials' f@ returns the finite set of all terms appearing in @f@;
  --   Term is a finite map from monomials to non-zero coefficient.
  terms' :: poly -> M.Map (Monomial (Arity poly)) (Coefficient poly)
  terms' poly
f = [(Monomial (Arity poly), Coefficient poly)]
-> Map (Monomial (Arity poly)) (Coefficient poly)
forall k a. Ord k => [(k, a)] -> Map k a
M.fromList [ (Monomial (Arity poly)
m, Coefficient poly
c)
                        | Monomial (Arity poly)
m <- HashSet (Monomial (Arity poly)) -> [Monomial (Arity poly)]
forall a. HashSet a -> [a]
HS.toList (HashSet (Monomial (Arity poly)) -> [Monomial (Arity poly)])
-> HashSet (Monomial (Arity poly)) -> [Monomial (Arity poly)]
forall a b. (a -> b) -> a -> b
$ poly -> HashSet (Monomial (Arity poly))
forall poly.
IsPolynomial poly =>
poly -> HashSet (Monomial (Arity poly))
monomials poly
f
                        , let c :: Coefficient poly
c = Monomial (Arity poly) -> poly -> Coefficient poly
forall poly.
IsPolynomial poly =>
Monomial (Arity poly) -> poly -> Coefficient poly
coeff' Monomial (Arity poly)
m poly
f
                        , Bool -> Bool
not (Coefficient poly -> Bool
forall r. DecidableZero r => r -> Bool
isZero Coefficient poly
c)
                        ]
  {-# INLINE terms' #-}

  -- | @'coeff m f'@ returns the coefficient of monomial @m@ in polynomial @f@.
  coeff' :: Monomial (Arity poly) -> poly -> Coefficient poly
  coeff' Monomial (Arity poly)
m = Coefficient poly
-> Monomial (Arity poly)
-> Map (Monomial (Arity poly)) (Coefficient poly)
-> Coefficient poly
forall k a. Ord k => a -> k -> Map k a -> a
M.findWithDefault Coefficient poly
forall m. Monoidal m => m
zero Monomial (Arity poly)
m (Map (Monomial (Arity poly)) (Coefficient poly)
 -> Coefficient poly)
-> (poly -> Map (Monomial (Arity poly)) (Coefficient poly))
-> poly
-> Coefficient poly
forall b c a. (b -> c) -> (a -> b) -> a -> c
. poly -> Map (Monomial (Arity poly)) (Coefficient poly)
forall poly.
IsPolynomial poly =>
poly -> Map (Monomial (Arity poly)) (Coefficient poly)
terms'
  {-# INLINE coeff' #-}

  -- | Calculates constant coefficient.
  constantTerm :: poly -> Coefficient poly
  constantTerm = Scalar (Coefficient poly) -> Coefficient poly
forall r. Scalar r -> r
runScalar (Scalar (Coefficient poly) -> Coefficient poly)
-> (poly -> Scalar (Coefficient poly)) -> poly -> Coefficient poly
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Ordinal (Arity poly) -> Scalar (Coefficient poly))
-> poly -> Scalar (Coefficient poly)
forall poly alg.
(IsPolynomial poly, Module (Scalar (Coefficient poly)) alg,
 Ring alg, Commutative alg) =>
(Ordinal (Arity poly) -> alg) -> poly -> alg
liftMap (\ Ordinal (Arity poly)
_ -> Coefficient poly -> Scalar (Coefficient poly)
forall r. r -> Scalar r
Scalar Coefficient poly
forall m. Monoidal m => m
zero)
  {-# INLINE constantTerm #-}

  -- | Inject monic monomial.
  fromMonomial :: Monomial (Arity poly) -> poly
  fromMonomial Monomial (Arity poly)
m = (Coefficient poly, Monomial (Arity poly)) -> poly
forall poly.
IsPolynomial poly =>
(Coefficient poly, Monomial (Arity poly)) -> poly
toPolynomial' (Coefficient poly
forall r. Unital r => r
one , Monomial (Arity poly)
m)
  {-# INLINE fromMonomial #-}

  -- | Inject coefficient with monomial.
  toPolynomial' :: (Coefficient poly, Monomial (Arity poly)) -> poly
  toPolynomial' (Coefficient poly
r, Monomial (Arity poly)
deg) = Coefficient poly -> Scalar (Coefficient poly)
forall r. r -> Scalar r
Scalar Coefficient poly
r Scalar (Coefficient poly) -> poly -> poly
forall r m. LeftModule r m => r -> m -> m
.* Monomial (Arity poly) -> poly
forall poly. IsPolynomial poly => Monomial (Arity poly) -> poly
fromMonomial Monomial (Arity poly)
deg
  {-# INLINE toPolynomial' #-}

  -- | Construct polynomial from the given finite mapping from monomials to coefficients.
  polynomial' :: M.Map (Monomial (Arity poly)) (Coefficient poly) -> poly
  polynomial' Map (Monomial (Arity poly)) (Coefficient poly)
dic =
    [poly] -> poly
forall (f :: * -> *) m. (Foldable f, Monoidal m) => f m -> m
sum [ (Coefficient poly, Monomial (Arity poly)) -> poly
forall poly.
IsPolynomial poly =>
(Coefficient poly, Monomial (Arity poly)) -> poly
toPolynomial' (Coefficient poly
r, Monomial (Arity poly)
deg) | (Monomial (Arity poly)
deg, Coefficient poly
r) <- Map (Monomial (Arity poly)) (Coefficient poly)
-> [(Monomial (Arity poly), Coefficient poly)]
forall k a. Map k a -> [(k, a)]
M.toList Map (Monomial (Arity poly)) (Coefficient poly)
dic ]
  {-# INLINE polynomial' #-}

  -- | Returns total degree.
  totalDegree' :: poly -> Int
  totalDegree' = Int -> Maybe Int -> Int
forall a. a -> Maybe a -> a
fromMaybe Int
0 (Maybe Int -> Int) -> (poly -> Maybe Int) -> poly -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Getting (Endo (Endo (Maybe Int))) (HashSet Int) Int
-> HashSet Int -> Maybe Int
forall a s.
Ord a =>
Getting (Endo (Endo (Maybe a))) s a -> s -> Maybe a
maximumOf Getting (Endo (Endo (Maybe Int))) (HashSet Int) Int
forall (f :: * -> *) a. Foldable f => IndexedFold Int (f a) a
folded (HashSet Int -> Maybe Int)
-> (poly -> HashSet Int) -> poly -> Maybe Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Monomial (Arity poly) -> Int)
-> HashSet (Monomial (Arity poly)) -> HashSet Int
forall b a.
(Hashable b, Eq b) =>
(a -> b) -> HashSet a -> HashSet b
HS.map Monomial (Arity poly) -> Int
forall mono.
(MonoFoldable mono, Num (Element mono)) =>
mono -> Element mono
osum (HashSet (Monomial (Arity poly)) -> HashSet Int)
-> (poly -> HashSet (Monomial (Arity poly))) -> poly -> HashSet Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. poly -> HashSet (Monomial (Arity poly))
forall poly.
IsPolynomial poly =>
poly -> HashSet (Monomial (Arity poly))
monomials
  {-# INLINE totalDegree' #-}

  -- | @'var' n@ returns a polynomial representing n-th variable.
  var :: Ordinal (Arity poly) -> poly
  var Ordinal (Arity poly)
nth = Monomial (Arity poly) -> poly
forall poly. IsPolynomial poly => Monomial (Arity poly) -> poly
fromMonomial (Monomial (Arity poly) -> poly) -> Monomial (Arity poly) -> poly
forall a b. (a -> b) -> a -> b
$ SNat (Arity poly) -> Ordinal (Arity poly) -> Monomial (Arity poly)
forall (n :: Nat). SNat n -> Ordinal n -> Monomial n
varMonom (poly -> SNat (Arity poly)
forall poly. IsPolynomial poly => poly -> SNat (Arity poly)
sArity' (poly
forall m. Monoidal m => m
zero :: poly)) Ordinal (Arity poly)
nth

  -- | Adjusting coefficients of each term.
  mapCoeff' :: (Coefficient poly -> Coefficient poly) -> poly -> poly
  mapCoeff' Coefficient poly -> Coefficient poly
f = Map (Monomial (Arity poly)) (Coefficient poly) -> poly
forall poly.
IsPolynomial poly =>
Map (Monomial (Arity poly)) (Coefficient poly) -> poly
polynomial' (Map (Monomial (Arity poly)) (Coefficient poly) -> poly)
-> (poly -> Map (Monomial (Arity poly)) (Coefficient poly))
-> poly
-> poly
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Coefficient poly -> Coefficient poly)
-> Map (Monomial (Arity poly)) (Coefficient poly)
-> Map (Monomial (Arity poly)) (Coefficient poly)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Coefficient poly -> Coefficient poly
f (Map (Monomial (Arity poly)) (Coefficient poly)
 -> Map (Monomial (Arity poly)) (Coefficient poly))
-> (poly -> Map (Monomial (Arity poly)) (Coefficient poly))
-> poly
-> Map (Monomial (Arity poly)) (Coefficient poly)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. poly -> Map (Monomial (Arity poly)) (Coefficient poly)
forall poly.
IsPolynomial poly =>
poly -> Map (Monomial (Arity poly)) (Coefficient poly)
terms'

  -- | @m '>|*' f@ multiplies polynomial @f@ by monomial @m@.
  (>|*) :: Monomial (Arity poly) -> poly -> poly
  Monomial (Arity poly)
m >|* poly
f = (Coefficient poly, Monomial (Arity poly)) -> poly
forall poly.
IsPolynomial poly =>
(Coefficient poly, Monomial (Arity poly)) -> poly
toPolynomial' (Coefficient poly
forall r. Unital r => r
one, Monomial (Arity poly)
m) poly -> poly -> poly
forall r. Multiplicative r => r -> r -> r
* poly
f

  -- | Flipped version of @('>|*')@
  (*|<) :: poly -> Monomial (Arity poly) -> poly
  (*|<) = (Monomial (Arity poly) -> poly -> poly)
-> poly -> Monomial (Arity poly) -> poly
forall a b c. (a -> b -> c) -> b -> a -> c
flip Monomial (Arity poly) -> poly -> poly
forall poly.
IsPolynomial poly =>
Monomial (Arity poly) -> poly -> poly
(>|*)

  (!*) :: Coefficient poly -> poly -> poly
  (!*) = Coefficient poly -> poly -> poly
forall r m. Module (Scalar r) m => r -> m -> m
(.*.)


  _Terms' :: Iso' poly (Map (Monomial (Arity poly)) (Coefficient poly))
  _Terms' = (poly -> Map (Monomial (Arity poly)) (Coefficient poly))
-> (Map (Monomial (Arity poly)) (Coefficient poly) -> poly)
-> Iso
     poly
     poly
     (Map (Monomial (Arity poly)) (Coefficient poly))
     (Map (Monomial (Arity poly)) (Coefficient poly))
forall s a b t. (s -> a) -> (b -> t) -> Iso s t a b
iso poly -> Map (Monomial (Arity poly)) (Coefficient poly)
forall poly.
IsPolynomial poly =>
poly -> Map (Monomial (Arity poly)) (Coefficient poly)
terms' Map (Monomial (Arity poly)) (Coefficient poly) -> poly
forall poly.
IsPolynomial poly =>
Map (Monomial (Arity poly)) (Coefficient poly) -> poly
polynomial'
  {-# INLINE _Terms' #-}

  mapMonomial :: (Monomial (Arity poly) -> Monomial (Arity poly)) -> poly -> poly
  mapMonomial Monomial (Arity poly) -> Monomial (Arity poly)
tr  =
    (Map (Monomial (Arity poly)) (Coefficient poly)
 -> Identity (Map (Monomial (Arity poly)) (Coefficient poly)))
-> poly -> Identity poly
forall poly.
IsPolynomial poly =>
Iso
  poly
  poly
  (Map (Monomial (Arity poly)) (Coefficient poly))
  (Map (Monomial (Arity poly)) (Coefficient poly))
_Terms' ((Map (Monomial (Arity poly)) (Coefficient poly)
  -> Identity (Map (Monomial (Arity poly)) (Coefficient poly)))
 -> poly -> Identity poly)
-> (Map (Monomial (Arity poly)) (Coefficient poly)
    -> Map (Monomial (Arity poly)) (Coefficient poly))
-> poly
-> poly
forall s t a b. ASetter s t a b -> (a -> b) -> s -> t
%~ (Coefficient poly -> Coefficient poly -> Coefficient poly)
-> (Monomial (Arity poly) -> Monomial (Arity poly))
-> Map (Monomial (Arity poly)) (Coefficient poly)
-> Map (Monomial (Arity poly)) (Coefficient poly)
forall k2 a k1.
Ord k2 =>
(a -> a -> a) -> (k1 -> k2) -> Map k1 a -> Map k2 a
M.mapKeysWith Coefficient poly -> Coefficient poly -> Coefficient poly
forall r. Additive r => r -> r -> r
(+) Monomial (Arity poly) -> Monomial (Arity poly)
tr
  {-# INLINE mapMonomial #-}

-- | Class to lookup ordering from its (type-level) name.
class (IsMonomialOrder (Arity poly) (MOrder poly), IsPolynomial poly) => IsOrderedPolynomial poly where
  type MOrder poly :: Type
  {-# MINIMAL leadingTerm | (leadingMonomial , leadingCoeff) #-}

  -- | A variant of @'coeff''@ which takes @'OrderedMonomial'@ instead of @'Monomial'@
  coeff :: OrderedMonomial (MOrder poly) (Arity poly) -> poly -> Coefficient poly
  coeff OrderedMonomial (MOrder poly) (Arity poly)
m = Monomial (Arity poly) -> poly -> Coefficient poly
forall poly.
IsPolynomial poly =>
Monomial (Arity poly) -> poly -> Coefficient poly
coeff' (OrderedMonomial (MOrder poly) (Arity poly) -> Monomial (Arity poly)
forall k (ordering :: k) (n :: Nat).
OrderedMonomial ordering n -> Monomial n
getMonomial OrderedMonomial (MOrder poly) (Arity poly)
m)
  {-# INLINE coeff #-}

  -- | The default implementation  is not enough efficient.
  --   So it is strongly recomended to give explicit
  --   definition to @'terms'@.
  terms :: poly -> M.Map (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
  terms = poly
-> Map
     (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
forall poly.
IsOrderedPolynomial poly =>
poly
-> Map
     (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
defaultTerms

  -- | Leading term with respect to its monomial ordering.
  leadingTerm :: poly -> (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
  leadingTerm = (,) (Coefficient poly
 -> OrderedMonomial (MOrder poly) (Arity poly)
 -> (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly)))
-> (poly -> Coefficient poly)
-> poly
-> OrderedMonomial (MOrder poly) (Arity poly)
-> (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> poly -> Coefficient poly
forall poly. IsOrderedPolynomial poly => poly -> Coefficient poly
leadingCoeff (poly
 -> OrderedMonomial (MOrder poly) (Arity poly)
 -> (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly)))
-> (poly -> OrderedMonomial (MOrder poly) (Arity poly))
-> poly
-> (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> poly -> OrderedMonomial (MOrder poly) (Arity poly)
forall poly.
IsOrderedPolynomial poly =>
poly -> OrderedMonomial (MOrder poly) (Arity poly)
leadingMonomial
  {-# INLINE leadingTerm #-}

  -- | Leading monomial with respect to its monomial ordering.
  leadingMonomial :: poly -> OrderedMonomial (MOrder poly) (Arity poly)
  leadingMonomial = (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
-> OrderedMonomial (MOrder poly) (Arity poly)
forall a b. (a, b) -> b
snd ((Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
 -> OrderedMonomial (MOrder poly) (Arity poly))
-> (poly
    -> (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly)))
-> poly
-> OrderedMonomial (MOrder poly) (Arity poly)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. poly
-> (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
forall poly.
IsOrderedPolynomial poly =>
poly
-> (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
leadingTerm
  {-# INLINE leadingMonomial #-}

  -- | Leading coefficient with respect to its monomial ordering.
  leadingCoeff :: poly -> Coefficient poly
  leadingCoeff = (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
-> Coefficient poly
forall a b. (a, b) -> a
fst ((Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
 -> Coefficient poly)
-> (poly
    -> (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly)))
-> poly
-> Coefficient poly
forall b c a. (b -> c) -> (a -> b) -> a -> c
. poly
-> (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
forall poly.
IsOrderedPolynomial poly =>
poly
-> (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
leadingTerm
  {-# INLINE leadingCoeff #-}

  -- | Splitting leading term, returning a pair of the leading term and the new polynomial
  --   with the leading term subtracted.
  splitLeadingTerm :: poly -> (Term poly, poly)
  splitLeadingTerm poly
p =
    let t :: (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
t = poly
-> (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
forall poly.
IsOrderedPolynomial poly =>
poly
-> (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
leadingTerm poly
p
    in ((Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
t, poly
p poly -> poly -> poly
forall r. Group r => r -> r -> r
- (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
-> poly
forall poly.
IsOrderedPolynomial poly =>
(Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
-> poly
toPolynomial (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
t)
  {-# INLINE splitLeadingTerm #-}

  -- | The collection of all monomials in the given polynomial,
  --   with metadata of their ordering.
  orderedMonomials :: poly -> S.Set (OrderedMonomial (MOrder poly) (Arity poly))
  orderedMonomials = [OrderedMonomial (MOrder poly) (Arity poly)]
-> Set (OrderedMonomial (MOrder poly) (Arity poly))
forall a. Ord a => [a] -> Set a
S.fromList ([OrderedMonomial (MOrder poly) (Arity poly)]
 -> Set (OrderedMonomial (MOrder poly) (Arity poly)))
-> (poly -> [OrderedMonomial (MOrder poly) (Arity poly)])
-> poly
-> Set (OrderedMonomial (MOrder poly) (Arity poly))
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Monomial (Arity poly)
 -> OrderedMonomial (MOrder poly) (Arity poly))
-> [Monomial (Arity poly)]
-> [OrderedMonomial (MOrder poly) (Arity poly)]
forall a b. (a -> b) -> [a] -> [b]
P.map Monomial (Arity poly) -> OrderedMonomial (MOrder poly) (Arity poly)
forall k (ordering :: k) (n :: Nat).
Monomial n -> OrderedMonomial ordering n
OrderedMonomial ([Monomial (Arity poly)]
 -> [OrderedMonomial (MOrder poly) (Arity poly)])
-> (poly -> [Monomial (Arity poly)])
-> poly
-> [OrderedMonomial (MOrder poly) (Arity poly)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. HashSet (Monomial (Arity poly)) -> [Monomial (Arity poly)]
forall a. HashSet a -> [a]
HS.toList (HashSet (Monomial (Arity poly)) -> [Monomial (Arity poly)])
-> (poly -> HashSet (Monomial (Arity poly)))
-> poly
-> [Monomial (Arity poly)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. poly -> HashSet (Monomial (Arity poly))
forall poly.
IsPolynomial poly =>
poly -> HashSet (Monomial (Arity poly))
monomials
  {-# INLINE orderedMonomials #-}

  -- | A variant of @'fromMonomial'@ which takes @'OrderedMonomial'@ as argument.
  fromOrderedMonomial :: OrderedMonomial (MOrder poly) (Arity poly) -> poly
  fromOrderedMonomial = Monomial (Arity poly) -> poly
forall poly. IsPolynomial poly => Monomial (Arity poly) -> poly
fromMonomial (Monomial (Arity poly) -> poly)
-> (OrderedMonomial (MOrder poly) (Arity poly)
    -> Monomial (Arity poly))
-> OrderedMonomial (MOrder poly) (Arity poly)
-> poly
forall b c a. (b -> c) -> (a -> b) -> a -> c
. OrderedMonomial (MOrder poly) (Arity poly) -> Monomial (Arity poly)
forall k (ordering :: k) (n :: Nat).
OrderedMonomial ordering n -> Monomial n
getMonomial
  {-# INLINE fromOrderedMonomial #-}

  -- | A variant of @'toPolynomial''@ which takes @'OrderedMonomial'@ as argument.
  toPolynomial :: (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly)) -> poly
  toPolynomial (Coefficient poly
r, OrderedMonomial (MOrder poly) (Arity poly)
deg) = (Coefficient poly, Monomial (Arity poly)) -> poly
forall poly.
IsPolynomial poly =>
(Coefficient poly, Monomial (Arity poly)) -> poly
toPolynomial' (Coefficient poly
r, OrderedMonomial (MOrder poly) (Arity poly) -> Monomial (Arity poly)
forall k (ordering :: k) (n :: Nat).
OrderedMonomial ordering n -> Monomial n
getMonomial OrderedMonomial (MOrder poly) (Arity poly)
deg)
  {-# INLINE toPolynomial #-}

  -- | A variant of @'polynomial''@ which takes @'OrderedMonomial'@ as argument.
  --
  --   The default implementation combines @'Data.Map.mapKeys'@ and @'polynomial''@,
  --   hence is not enough efficient. So it is strongly recomended to give explicit
  -- definition to @'polynomial'@.
  polynomial :: M.Map (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
             -> poly
  polynomial Map (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
dic = Map (Monomial (Arity poly)) (Coefficient poly) -> poly
forall poly.
IsPolynomial poly =>
Map (Monomial (Arity poly)) (Coefficient poly) -> poly
polynomial' (Map (Monomial (Arity poly)) (Coefficient poly) -> poly)
-> Map (Monomial (Arity poly)) (Coefficient poly) -> poly
forall a b. (a -> b) -> a -> b
$ (OrderedMonomial (MOrder poly) (Arity poly)
 -> Monomial (Arity poly))
-> Map
     (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
-> Map (Monomial (Arity poly)) (Coefficient poly)
forall k2 k1 a. Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a
M.mapKeys OrderedMonomial (MOrder poly) (Arity poly) -> Monomial (Arity poly)
forall k (ordering :: k) (n :: Nat).
OrderedMonomial ordering n -> Monomial n
getMonomial Map (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
dic
  {-# INLINE polynomial #-}

  -- | A variant of @'(>|*)'@ which takes @'OrderedMonomial'@ as argument.
  (>*) :: OrderedMonomial (MOrder poly) (Arity poly) -> poly -> poly
  (>*) OrderedMonomial (MOrder poly) (Arity poly)
m = (OrderedMonomial (MOrder poly) (Arity poly)
 -> OrderedMonomial (MOrder poly) (Arity poly))
-> poly -> poly
forall poly.
IsOrderedPolynomial poly =>
(OrderedMonomial (MOrder poly) (Arity poly)
 -> OrderedMonomial (MOrder poly) (Arity poly))
-> poly -> poly
mapMonomialMonotonic (OrderedMonomial (MOrder poly) (Arity poly)
m OrderedMonomial (MOrder poly) (Arity poly)
-> OrderedMonomial (MOrder poly) (Arity poly)
-> OrderedMonomial (MOrder poly) (Arity poly)
forall r. Multiplicative r => r -> r -> r
*)
  {-# INLINE (>*) #-}

  -- | Flipped version of (>*)
  (*<) :: poly -> OrderedMonomial (MOrder poly) (Arity poly) -> poly
  (*<) = (OrderedMonomial (MOrder poly) (Arity poly) -> poly -> poly)
-> poly -> OrderedMonomial (MOrder poly) (Arity poly) -> poly
forall a b c. (a -> b -> c) -> b -> a -> c
flip OrderedMonomial (MOrder poly) (Arity poly) -> poly -> poly
forall poly.
IsOrderedPolynomial poly =>
OrderedMonomial (MOrder poly) (Arity poly) -> poly -> poly
(>*)
  {-# INLINE (*<) #-}

  _Terms :: Iso' poly (Map (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly))
  _Terms = (poly
 -> Map
      (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly))
-> (Map
      (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
    -> poly)
-> Iso
     poly
     poly
     (Map
        (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly))
     (Map
        (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly))
forall s a b t. (s -> a) -> (b -> t) -> Iso s t a b
iso poly
-> Map
     (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
forall poly.
IsOrderedPolynomial poly =>
poly
-> Map
     (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
terms Map (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
-> poly
forall poly.
IsOrderedPolynomial poly =>
Map (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
-> poly
polynomial
  {-# INLINE _Terms #-}

  -- | @diff n f@ partially diffrenciates @n@-th variable in the given polynomial @f@.
  --   The default implementation uses @'terms'@ and @'polynomial'@
  --   and is really naive; please consider overrideing for efficiency.
  diff :: Ordinal (Arity poly) -> poly -> poly
  diff Ordinal (Arity poly)
n = (Map
   (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
 -> Identity
      (Map
         (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)))
-> poly -> Identity poly
forall poly.
IsOrderedPolynomial poly =>
Iso
  poly
  poly
  (Map
     (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly))
  (Map
     (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly))
_Terms ((Map
    (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
  -> Identity
       (Map
          (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)))
 -> poly -> Identity poly)
-> (Map
      (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
    -> Map
         (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly))
-> poly
-> poly
forall s t a b. ASetter s t a b -> (a -> b) -> s -> t
%~ (Coefficient poly -> Coefficient poly -> Coefficient poly)
-> (OrderedMonomial (MOrder poly) (Arity poly)
    -> OrderedMonomial (MOrder poly) (Arity poly))
-> Map
     (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
-> Map
     (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
forall k2 a k1.
Ord k2 =>
(a -> a -> a) -> (k1 -> k2) -> Map k1 a -> Map k2 a
M.mapKeysWith Coefficient poly -> Coefficient poly -> Coefficient poly
forall r. Additive r => r -> r -> r
(+) ((Monomial (Arity poly) -> Identity (Monomial (Arity poly)))
-> OrderedMonomial (MOrder poly) (Arity poly)
-> Identity (OrderedMonomial (MOrder poly) (Arity poly))
forall s t. Rewrapping s t => Iso s t (Unwrapped s) (Unwrapped t)
_Wrapped((Monomial (Arity poly) -> Identity (Monomial (Arity poly)))
 -> OrderedMonomial (MOrder poly) (Arity poly)
 -> Identity (OrderedMonomial (MOrder poly) (Arity poly)))
-> ((Int -> Identity Int)
    -> Monomial (Arity poly) -> Identity (Monomial (Arity poly)))
-> (Int -> Identity Int)
-> OrderedMonomial (MOrder poly) (Arity poly)
-> Identity (OrderedMonomial (MOrder poly) (Arity poly))
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Index (Monomial (Arity poly))
-> Traversal'
     (Monomial (Arity poly)) (IxValue (Monomial (Arity poly)))
forall m. Ixed m => Index m -> Traversal' m (IxValue m)
ix Index (Monomial (Arity poly))
Ordinal (Arity poly)
n ((Int -> Identity Int)
 -> OrderedMonomial (MOrder poly) (Arity poly)
 -> Identity (OrderedMonomial (MOrder poly) (Arity poly)))
-> (Int -> Int)
-> OrderedMonomial (MOrder poly) (Arity poly)
-> OrderedMonomial (MOrder poly) (Arity poly)
forall s t a b. ASetter s t a b -> (a -> b) -> s -> t
%~ Int -> Int -> Int
forall a. Ord a => a -> a -> a
max Int
0 (Int -> Int) -> (Int -> Int) -> Int -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Int
forall a. Enum a => a -> a
pred)
                   (Map
   (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
 -> Map
      (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly))
-> (Map
      (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
    -> Map
         (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly))
-> Map
     (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
-> Map
     (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (OrderedMonomial (MOrder poly) (Arity poly)
 -> Coefficient poly -> Maybe (Coefficient poly))
-> Map
     (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
-> Map
     (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
forall k a b. (k -> a -> Maybe b) -> Map k a -> Map k b
M.mapMaybeWithKey OrderedMonomial (MOrder poly) (Arity poly)
-> Coefficient poly -> Maybe (Coefficient poly)
df
    where
      df :: OrderedMonomial (MOrder poly) (Arity poly)
-> Coefficient poly -> Maybe (Coefficient poly)
df OrderedMonomial (MOrder poly) (Arity poly)
m Coefficient poly
v =
        let p :: Int
p  = OrderedMonomial (MOrder poly) (Arity poly) -> Monomial (Arity poly)
forall k (ordering :: k) (n :: Nat).
OrderedMonomial ordering n -> Monomial n
getMonomial OrderedMonomial (MOrder poly) (Arity poly)
m Monomial (Arity poly) -> Ordinal (Arity poly) -> Int
forall (f :: * -> *) (n :: Nat) c.
(CFoldable f, Dom f c) =>
Sized f n c -> Ordinal n -> c
V.%!! Ordinal (Arity poly)
n
            v' :: Coefficient poly
v' = Int -> Coefficient poly
forall n r. (Integral n, Ring r) => n -> r
NA.fromIntegral Int
p Coefficient poly -> Coefficient poly -> Coefficient poly
forall r. Multiplicative r => r -> r -> r
* Coefficient poly
v
        in if Int
p Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0 Bool -> Bool -> Bool
|| Coefficient poly -> Bool
forall r. DecidableZero r => r -> Bool
isZero Coefficient poly
v'
           then Maybe (Coefficient poly)
forall a. Maybe a
Nothing
           else Coefficient poly -> Maybe (Coefficient poly)
forall a. a -> Maybe a
Just Coefficient poly
v'
  {-# INLINE diff #-}

  -- | Same as @'mapMonomial'@, but maping function is
  --   assumed to be strictly monotonic (i.e. @a < b@ implies @f a < f b@).
  mapMonomialMonotonic
    :: (OrderedMonomial (MOrder poly) (Arity poly) -> OrderedMonomial (MOrder poly) (Arity poly))
    -> poly -> poly
  mapMonomialMonotonic OrderedMonomial (MOrder poly) (Arity poly)
-> OrderedMonomial (MOrder poly) (Arity poly)
tr  =
    (Map
   (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
 -> Identity
      (Map
         (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)))
-> poly -> Identity poly
forall poly.
IsOrderedPolynomial poly =>
Iso
  poly
  poly
  (Map
     (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly))
  (Map
     (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly))
_Terms ((Map
    (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
  -> Identity
       (Map
          (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)))
 -> poly -> Identity poly)
-> (Map
      (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
    -> Map
         (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly))
-> poly
-> poly
forall s t a b. ASetter s t a b -> (a -> b) -> s -> t
%~ (OrderedMonomial (MOrder poly) (Arity poly)
 -> OrderedMonomial (MOrder poly) (Arity poly))
-> Map
     (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
-> Map
     (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
forall k1 k2 a. (k1 -> k2) -> Map k1 a -> Map k2 a
M.mapKeysMonotonic OrderedMonomial (MOrder poly) (Arity poly)
-> OrderedMonomial (MOrder poly) (Arity poly)
tr
  {-# INLINE mapMonomialMonotonic #-}


type OMonom poly = OrderedMonomial (MOrder poly) (Arity poly)
type Term poly = (Coefficient poly, OMonom poly)

defaultTerms :: IsOrderedPolynomial poly
             => poly -> Map (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
defaultTerms :: poly
-> Map
     (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
defaultTerms = (Monomial (Arity poly)
 -> OrderedMonomial (MOrder poly) (Arity poly))
-> Map (Monomial (Arity poly)) (Coefficient poly)
-> Map
     (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
forall k2 k1 a. Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a
M.mapKeys Monomial (Arity poly) -> OrderedMonomial (MOrder poly) (Arity poly)
forall k (ordering :: k) (n :: Nat).
Monomial n -> OrderedMonomial ordering n
OrderedMonomial (Map (Monomial (Arity poly)) (Coefficient poly)
 -> Map
      (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly))
-> (poly -> Map (Monomial (Arity poly)) (Coefficient poly))
-> poly
-> Map
     (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. poly -> Map (Monomial (Arity poly)) (Coefficient poly)
forall poly.
IsPolynomial poly =>
poly -> Map (Monomial (Arity poly)) (Coefficient poly)
terms'
{-# NOINLINE [1] defaultTerms #-}

{-# RULES
 "polynomial/terms" forall (f :: IsOrderedPolynomial poly => poly).
   polynomial (defaultTerms f) = f
 #-}

liftMapCoeff :: IsPolynomial poly => (Ordinal (Arity poly) -> Coefficient poly) -> poly -> Coefficient poly
liftMapCoeff :: (Ordinal (Arity poly) -> Coefficient poly)
-> poly -> Coefficient poly
liftMapCoeff Ordinal (Arity poly) -> Coefficient poly
l = Scalar (Coefficient poly) -> Coefficient poly
forall r. Scalar r -> r
runScalar (Scalar (Coefficient poly) -> Coefficient poly)
-> (poly -> Scalar (Coefficient poly)) -> poly -> Coefficient poly
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Ordinal (Arity poly) -> Scalar (Coefficient poly))
-> poly -> Scalar (Coefficient poly)
forall poly alg.
(IsPolynomial poly, Module (Scalar (Coefficient poly)) alg,
 Ring alg, Commutative alg) =>
(Ordinal (Arity poly) -> alg) -> poly -> alg
liftMap (Coefficient poly -> Scalar (Coefficient poly)
forall r. r -> Scalar r
Scalar (Coefficient poly -> Scalar (Coefficient poly))
-> (Ordinal (Arity poly) -> Coefficient poly)
-> Ordinal (Arity poly)
-> Scalar (Coefficient poly)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Ordinal (Arity poly) -> Coefficient poly
l)
{-# INLINE liftMapCoeff #-}

substCoeff :: IsPolynomial poly => Sized (Arity poly) (Coefficient poly) -> poly -> Coefficient poly
substCoeff :: Sized (Arity poly) (Coefficient poly) -> poly -> Coefficient poly
substCoeff Sized (Arity poly) (Coefficient poly)
l = Scalar (Coefficient poly) -> Coefficient poly
forall r. Scalar r -> r
runScalar (Scalar (Coefficient poly) -> Coefficient poly)
-> (poly -> Scalar (Coefficient poly)) -> poly -> Coefficient poly
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Sized (Arity poly) (Scalar (Coefficient poly))
-> poly -> Scalar (Coefficient poly)
forall poly alg.
(IsPolynomial poly, Ring alg, Commutative alg,
 Module (Scalar (Coefficient poly)) alg) =>
Sized (Arity poly) alg -> poly -> alg
subst ((Coefficient poly -> Scalar (Coefficient poly))
-> Sized (Arity poly) (Coefficient poly)
-> Sized (Arity poly) (Scalar (Coefficient poly))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Coefficient poly -> Scalar (Coefficient poly)
forall r. r -> Scalar r
Scalar Sized (Arity poly) (Coefficient poly)
l)
{-# INLINE substCoeff #-}

-- | 1-norm of given polynomial, taking sum of @'norm'@s of each coefficients.
oneNorm :: (IsPolynomial poly, Normed (Coefficient poly),
            Monoidal (Norm (Coefficient poly))) => poly -> Norm (Coefficient poly)
oneNorm :: poly -> Norm (Coefficient poly)
oneNorm = [Norm (Coefficient poly)] -> Norm (Coefficient poly)
forall (f :: * -> *) m. (Foldable f, Monoidal m) => f m -> m
sum ([Norm (Coefficient poly)] -> Norm (Coefficient poly))
-> (poly -> [Norm (Coefficient poly)])
-> poly
-> Norm (Coefficient poly)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Coefficient poly -> Norm (Coefficient poly))
-> [Coefficient poly] -> [Norm (Coefficient poly)]
forall a b. (a -> b) -> [a] -> [b]
P.map Coefficient poly -> Norm (Coefficient poly)
forall a. Normed a => a -> Norm a
norm ([Coefficient poly] -> [Norm (Coefficient poly)])
-> (poly -> [Coefficient poly])
-> poly
-> [Norm (Coefficient poly)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map (Monomial (Arity poly)) (Coefficient poly)
-> [Coefficient poly]
forall (t :: * -> *) a. Foldable t => t a -> [a]
F.toList (Map (Monomial (Arity poly)) (Coefficient poly)
 -> [Coefficient poly])
-> (poly -> Map (Monomial (Arity poly)) (Coefficient poly))
-> poly
-> [Coefficient poly]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. poly -> Map (Monomial (Arity poly)) (Coefficient poly)
forall poly.
IsPolynomial poly =>
poly -> Map (Monomial (Arity poly)) (Coefficient poly)
terms'
{-# INLINE oneNorm #-}

-- | Maximum norm of given polynomial, taking maximum of the @'norm'@s of each coefficients.
maxNorm :: (IsPolynomial poly, Normed (Coefficient poly)) => poly -> Norm (Coefficient poly)
maxNorm :: poly -> Norm (Coefficient poly)
maxNorm = [Norm (Coefficient poly)] -> Norm (Coefficient poly)
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
maximum ([Norm (Coefficient poly)] -> Norm (Coefficient poly))
-> (poly -> [Norm (Coefficient poly)])
-> poly
-> Norm (Coefficient poly)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Coefficient poly -> Norm (Coefficient poly))
-> [Coefficient poly] -> [Norm (Coefficient poly)]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
map Coefficient poly -> Norm (Coefficient poly)
forall a. Normed a => a -> Norm a
norm ([Coefficient poly] -> [Norm (Coefficient poly)])
-> (poly -> [Coefficient poly])
-> poly
-> [Norm (Coefficient poly)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map (Monomial (Arity poly)) (Coefficient poly)
-> [Coefficient poly]
forall (t :: * -> *) a. Foldable t => t a -> [a]
F.toList (Map (Monomial (Arity poly)) (Coefficient poly)
 -> [Coefficient poly])
-> (poly -> Map (Monomial (Arity poly)) (Coefficient poly))
-> poly
-> [Coefficient poly]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. poly -> Map (Monomial (Arity poly)) (Coefficient poly)
forall poly.
IsPolynomial poly =>
poly -> Map (Monomial (Arity poly)) (Coefficient poly)
terms'
{-# INLINE maxNorm #-}

-- | Make the given polynomial monic.
--   If the given polynomial is zero, it returns as it is.
monoize :: (Field (Coefficient poly), IsOrderedPolynomial poly)
        => poly -> poly
monoize :: poly -> poly
monoize poly
f | poly -> Bool
forall r. DecidableZero r => r -> Bool
isZero poly
f  = poly
forall m. Monoidal m => m
zero
          | Bool
otherwise = Coefficient poly -> Coefficient poly
forall r. Division r => r -> r
recip (poly -> Coefficient poly
forall poly. IsOrderedPolynomial poly => poly -> Coefficient poly
leadingCoeff poly
f) Coefficient poly -> poly -> poly
forall r m. Module (Scalar r) m => r -> m -> m
.*. poly
f
{-# INLINE monoize #-}

-- | @'sPolynomial'@ calculates the S-Polynomial of given two polynomials.
sPolynomial :: (IsOrderedPolynomial poly, Field (Coefficient poly))
            => poly
            -> poly -> poly
sPolynomial :: poly -> poly -> poly
sPolynomial poly
f poly
g =
    let h :: (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
h = (Coefficient poly
forall r. Unital r => r
one, OrderedMonomial (MOrder poly) (Arity poly)
-> OrderedMonomial (MOrder poly) (Arity poly)
-> OrderedMonomial (MOrder poly) (Arity poly)
forall k (n :: Nat) (ord :: k).
KnownNat n =>
OrderedMonomial ord n
-> OrderedMonomial ord n -> OrderedMonomial ord n
lcmMonomial (poly -> OrderedMonomial (MOrder poly) (Arity poly)
forall poly.
IsOrderedPolynomial poly =>
poly -> OrderedMonomial (MOrder poly) (Arity poly)
leadingMonomial poly
f) (poly -> OrderedMonomial (MOrder poly) (Arity poly)
forall poly.
IsOrderedPolynomial poly =>
poly -> OrderedMonomial (MOrder poly) (Arity poly)
leadingMonomial poly
g))
    in (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
-> poly
forall poly.
IsOrderedPolynomial poly =>
(Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
-> poly
toPolynomial ((Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
h (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
-> (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
-> (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
forall k (n :: Nat) r (ord :: k).
(KnownNat n, Field r) =>
(r, OrderedMonomial ord n)
-> (r, OrderedMonomial ord n) -> (r, OrderedMonomial ord n)
`tryDiv` poly
-> (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
forall poly.
IsOrderedPolynomial poly =>
poly
-> (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
leadingTerm poly
f) poly -> poly -> poly
forall r. Multiplicative r => r -> r -> r
* poly
f poly -> poly -> poly
forall r. Group r => r -> r -> r
- (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
-> poly
forall poly.
IsOrderedPolynomial poly =>
(Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
-> poly
toPolynomial ((Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
h (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
-> (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
-> (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
forall k (n :: Nat) r (ord :: k).
(KnownNat n, Field r) =>
(r, OrderedMonomial ord n)
-> (r, OrderedMonomial ord n) -> (r, OrderedMonomial ord n)
`tryDiv` poly
-> (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
forall poly.
IsOrderedPolynomial poly =>
poly
-> (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
leadingTerm poly
g) poly -> poly -> poly
forall r. Multiplicative r => r -> r -> r
* poly
g

-- | @pDivModPoly f g@ calculates the pseudo quotient and reminder of @f@ by @g@.
pDivModPoly :: (k ~ Coefficient poly, Euclidean k, IsOrderedPolynomial poly)
            => poly -> poly
            -> (poly, poly)
poly
f0 pDivModPoly :: poly -> poly -> (poly, poly)
`pDivModPoly` poly
g =
  let k :: Integer
k = Int -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int -> Integer) -> Int -> Integer
forall a b. (a -> b) -> a -> b
$ poly -> Int
forall poly. IsPolynomial poly => poly -> Int
totalDegree' poly
f0 :: Integer
      l :: Integer
l = Int -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int -> Integer) -> Int -> Integer
forall a b. (a -> b) -> a -> b
$ poly -> Int
forall poly. IsPolynomial poly => poly -> Int
totalDegree' poly
g  :: Integer
  in poly -> poly -> (poly, poly)
step (Coefficient poly -> poly
forall poly. IsPolynomial poly => Coefficient poly -> poly
injectCoeff (k -> Natural -> k
forall r. Unital r => r -> Natural -> r
pow (poly -> Coefficient poly
forall poly. IsOrderedPolynomial poly => poly -> Coefficient poly
leadingCoeff poly
g) (Integer -> Natural
forall a. Num a => Integer -> a
P.fromInteger (Integer -> Integer -> Integer
forall a. Ord a => a -> a -> a
max Integer
0 (Integer -> Integer) -> Integer -> Integer
forall a b. (a -> b) -> a -> b
$ Integer
1 Integer -> Integer -> Integer
forall r. Additive r => r -> r -> r
+ Integer
k Integer -> Integer -> Integer
forall r. Group r => r -> r -> r
- Integer
l) :: Natural)) poly -> poly -> poly
forall r. Multiplicative r => r -> r -> r
* poly
f0) poly
forall m. Monoidal m => m
zero
  where
    lm :: OrderedMonomial (MOrder poly) (Arity poly)
lm = poly -> OrderedMonomial (MOrder poly) (Arity poly)
forall poly.
IsOrderedPolynomial poly =>
poly -> OrderedMonomial (MOrder poly) (Arity poly)
leadingMonomial poly
g
    step :: poly -> poly -> (poly, poly)
step poly
p poly
quo
        | poly -> Bool
forall r. DecidableZero r => r -> Bool
isZero poly
p = (poly
quo, poly
p)
        | OrderedMonomial (MOrder poly) (Arity poly)
lm OrderedMonomial (MOrder poly) (Arity poly)
-> OrderedMonomial (MOrder poly) (Arity poly) -> Bool
forall k (n :: Nat) (ord :: k).
KnownNat n =>
OrderedMonomial ord n -> OrderedMonomial ord n -> Bool
`divs` poly -> OrderedMonomial (MOrder poly) (Arity poly)
forall poly.
IsOrderedPolynomial poly =>
poly -> OrderedMonomial (MOrder poly) (Arity poly)
leadingMonomial poly
p =
            let coe :: k
coe = poly -> Coefficient poly
forall poly. IsOrderedPolynomial poly => poly -> Coefficient poly
leadingCoeff poly
p k -> k -> k
forall d. Euclidean d => d -> d -> d
`quot` poly -> Coefficient poly
forall poly. IsOrderedPolynomial poly => poly -> Coefficient poly
leadingCoeff poly
g
                mon :: OrderedMonomial (MOrder poly) (Arity poly)
mon = poly -> OrderedMonomial (MOrder poly) (Arity poly)
forall poly.
IsOrderedPolynomial poly =>
poly -> OrderedMonomial (MOrder poly) (Arity poly)
leadingMonomial poly
p OrderedMonomial (MOrder poly) (Arity poly)
-> OrderedMonomial (MOrder poly) (Arity poly)
-> OrderedMonomial (MOrder poly) (Arity poly)
forall r. Division r => r -> r -> r
/ poly -> OrderedMonomial (MOrder poly) (Arity poly)
forall poly.
IsOrderedPolynomial poly =>
poly -> OrderedMonomial (MOrder poly) (Arity poly)
leadingMonomial poly
g
                q :: poly
q   = (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
-> poly
forall poly.
IsOrderedPolynomial poly =>
(Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
-> poly
toPolynomial (k
Coefficient poly
coe, OrderedMonomial (MOrder poly) (Arity poly)
mon)
            in poly -> poly -> (poly, poly)
step (poly
p poly -> poly -> poly
forall r. Group r => r -> r -> r
- (poly
q poly -> poly -> poly
forall r. Multiplicative r => r -> r -> r
* poly
g)) (poly
quo poly -> poly -> poly
forall r. Additive r => r -> r -> r
+ poly
q)
        | Bool
otherwise = (poly
quo, poly
p)

-- | The content of a polynomial f is the @'gcd'@ of all its coefficients.
content :: (IsPolynomial poly, Euclidean (Coefficient poly)) => poly -> Coefficient poly
content :: poly -> Coefficient poly
content = (Coefficient poly -> Coefficient poly -> Coefficient poly)
-> Coefficient poly
-> Map (Monomial (Arity poly)) (Coefficient poly)
-> Coefficient poly
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr Coefficient poly -> Coefficient poly -> Coefficient poly
forall d. GCDDomain d => d -> d -> d
gcd Coefficient poly
forall m. Monoidal m => m
zero (Map (Monomial (Arity poly)) (Coefficient poly)
 -> Coefficient poly)
-> (poly -> Map (Monomial (Arity poly)) (Coefficient poly))
-> poly
-> Coefficient poly
forall b c a. (b -> c) -> (a -> b) -> a -> c
. poly -> Map (Monomial (Arity poly)) (Coefficient poly)
forall poly.
IsPolynomial poly =>
poly -> Map (Monomial (Arity poly)) (Coefficient poly)
terms'
{-# INLINE content #-}

-- | @'pp' f@ calculates the primitive part of given polynomial @f@,
--   namely @f / content(f)@.
pp :: (Euclidean (Coefficient poly), IsPolynomial poly) => poly -> poly
pp :: poly -> poly
pp poly
f = (Coefficient poly -> Coefficient poly) -> poly -> poly
forall poly.
IsPolynomial poly =>
(Coefficient poly -> Coefficient poly) -> poly -> poly
mapCoeff' (Coefficient poly -> Coefficient poly -> Coefficient poly
forall d. Euclidean d => d -> d -> d
`quot` poly -> Coefficient poly
forall poly.
(IsPolynomial poly, Euclidean (Coefficient poly)) =>
poly -> Coefficient poly
content poly
f) poly
f
{-# INLINE pp #-}

-- | See also @'injectVarsOffset'@ and @'injectVarsAtEnd'@.
injectVars :: ((Arity r <= Arity r'),
               IsPolynomial r,
               IsPolynomial r',
               Coefficient r ~ Coefficient r') => r -> r'
injectVars :: r -> r'
injectVars = (Ordinal (Arity r) -> r') -> r -> r'
forall poly alg.
(IsPolynomial poly, Module (Scalar (Coefficient poly)) alg,
 Ring alg, Commutative alg) =>
(Ordinal (Arity poly) -> alg) -> poly -> alg
liftMap (Ordinal (Arity r') -> r'
forall poly. IsPolynomial poly => Ordinal (Arity poly) -> poly
var (Ordinal (Arity r') -> r')
-> (Ordinal (Arity r) -> Ordinal (Arity r'))
-> Ordinal (Arity r)
-> r'
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Ordinal (Arity r) -> Ordinal (Arity r')
forall (n :: Nat) (m :: Nat). (n <= m) => Ordinal n -> Ordinal m
inclusion)
{-# INLINE [1] injectVars #-}
{-# RULES "injectVars/identity" injectVars = P.id #-}

-- | Similar to @'injectVars'@, but injects variables at the end of
--   the target polynomial ring.
--
--   See also @'injectVars'@ and @'injectVarsOffset'@.
injectVarsAtEnd :: forall r r'. ((Arity r <= Arity r'),
                    IsPolynomial r,
                    IsPolynomial r',
                    Coefficient r ~ Coefficient r') => r -> r'
injectVarsAtEnd :: r -> r'
injectVarsAtEnd =
  let sn :: SNat (Arity r)
sn = Proxy r -> SNat (Arity r)
forall poly (proxy :: * -> *).
IsPolynomial poly =>
proxy poly -> SNat (Arity poly)
sArity (Proxy r
forall k (t :: k). Proxy t
Proxy @r)
      sm :: SNat (Arity r')
sm = Proxy r' -> SNat (Arity r')
forall poly (proxy :: * -> *).
IsPolynomial poly =>
proxy poly -> SNat (Arity poly)
sArity (Proxy r'
forall k (t :: k). Proxy t
Proxy @r')
  in (((Arity r' - Arity r) + Arity r) :~: Arity r')
-> ((((Arity r' - Arity r) + Arity r) ~ Arity r') => r -> r')
-> r
-> r'
forall k (a :: k) (b :: k) r. (a :~: b) -> ((a ~ b) => r) -> r
withRefl (SNat (Arity r')
-> SNat (Arity r)
-> IsTrue (Arity r <=? Arity r')
-> ((Arity r' - Arity r) + Arity r) :~: Arity r'
forall (n :: Nat) (m :: Nat).
SNat n -> SNat m -> IsTrue (m <=? n) -> ((n - m) + m) :~: n
minusPlus SNat (Arity r')
sm SNat (Arity r)
sn IsTrue (Arity r <=? Arity r')
IsTrue 'True
Witness) (((((Arity r' - Arity r) + Arity r) ~ Arity r') => r -> r')
 -> r -> r')
-> ((((Arity r' - Arity r) + Arity r) ~ Arity r') => r -> r')
-> r
-> r'
forall a b. (a -> b) -> a -> b
$ SNat (Arity r' - Arity r) -> r -> r'
forall (n :: Nat) r r'.
((n + Arity r) <= Arity r', IsPolynomial r, IsPolynomial r',
 Coefficient r ~ Coefficient r') =>
SNat n -> r -> r'
injectVarsOffset (SNat (Arity r')
sm SNat (Arity r') -> SNat (Arity r) -> SNat (Arity r' - Arity r)
forall (n :: Nat) (m :: Nat). SNat n -> SNat m -> SNat (n - m)
%- SNat (Arity r)
sn)
{-# INLINE injectVarsAtEnd #-}

shift :: forall n m k. ((n + m <= k), KnownNat m, KnownNat k) => SNat n -> Ordinal m -> Ordinal k
shift :: SNat n -> Ordinal m -> Ordinal k
shift SNat n
sn (OLt (SNat n1
sl :: SNat l)) =
  let sm :: SNat m
sm = SNat m
forall (n :: Nat). KnownNat n => SNat n
sNat :: SNat m
      sk :: SNat k
sk = SNat k
forall (n :: Nat). KnownNat n => SNat n
sNat :: SNat k
  in (CmpNat n1 m :~: 'LT)
-> ((CmpNat n1 m ~ 'LT) => Ordinal k) -> Ordinal k
forall k (a :: k) (b :: k) r. (a :~: b) -> ((a ~ b) => r) -> r
withRefl (SNat n1 -> SNat m -> IsTrue (n1 <? m) -> CmpNat n1 m :~: 'LT
forall (n :: Nat) (m :: Nat).
SNat n -> SNat m -> IsTrue (n <? m) -> CmpNat n m :~: 'LT
lneqToLT SNat n1
sl SNat m
sm IsTrue (n1 <? m)
IsTrue 'True
Witness) (((CmpNat n1 m ~ 'LT) => Ordinal k) -> Ordinal k)
-> ((CmpNat n1 m ~ 'LT) => Ordinal k) -> Ordinal k
forall a b. (a -> b) -> a -> b
$
     IsTrue (((n + n1) + 1) <=? (n + m))
-> (((((n + n1) + 1) <=? (n + m)) ~ 'True) => Ordinal k)
-> Ordinal k
forall (b :: Bool) r. IsTrue b -> ((b ~ 'True) => r) -> r
withWitness (SNat n
-> SNat n1
-> SNat m
-> IsTrue (n1 <? m)
-> IsTrue (((n + n1) + 1) <=? (n + m))
forall (n :: Nat) (m :: Nat) (l :: Nat).
SNat n
-> SNat m
-> SNat l
-> IsTrue (m <? l)
-> IsTrue ((n + m) <? (n + l))
lneqMonotoneR SNat n
sn SNat n1
sl SNat m
sm IsTrue (n1 <? m)
IsTrue 'True
Witness) ((((((n + n1) + 1) <=? (n + m)) ~ 'True) => Ordinal k)
 -> Ordinal k)
-> (((((n + n1) + 1) <=? (n + m)) ~ 'True) => Ordinal k)
-> Ordinal k
forall a b. (a -> b) -> a -> b
$
     IsTrue 'True -> (('True ~ 'True) => Ordinal k) -> Ordinal k
forall (b :: Bool) r. IsTrue b -> ((b ~ 'True) => r) -> r
withWitness (SNat (n + n1)
-> SNat (n + m)
-> SNat k
-> IsTrue (((n + n1) + 1) <=? (n + m))
-> IsTrue ((n + m) <=? k)
-> IsTrue ((n + n1) <? k)
forall (n :: Nat) (m :: Nat) (l :: Nat).
SNat n
-> SNat m
-> SNat l
-> IsTrue (n <? m)
-> IsTrue (m <=? l)
-> IsTrue (n <? l)
lneqLeqTrans (SNat n
sn SNat n -> SNat n1 -> SNat (n + n1)
forall (n :: Nat) (m :: Nat). SNat n -> SNat m -> SNat (n + m)
%+ SNat n1
sl) (SNat n
sn SNat n -> SNat m -> SNat (n + m)
forall (n :: Nat) (m :: Nat). SNat n -> SNat m -> SNat (n + m)
%+ SNat m
sm) SNat k
sk IsTrue (((n + n1) + 1) <=? (n + m))
IsTrue 'True
Witness IsTrue ((n + m) <=? k)
IsTrue 'True
Witness) ((('True ~ 'True) => Ordinal k) -> Ordinal k)
-> (('True ~ 'True) => Ordinal k) -> Ordinal k
forall a b. (a -> b) -> a -> b
$
     SNat (n + n1) -> Ordinal k
forall (n1 :: Nat) (n :: Nat). (n1 < n) => SNat n1 -> Ordinal n
OLt (SNat n
sn SNat n -> SNat n1 -> SNat (n + n1)
forall (n :: Nat) (m :: Nat). SNat n -> SNat m -> SNat (n + m)
%+ SNat n1
sl)
{-# INLINE [1] shift #-}
{-# RULES
"shift/zero" forall (ns :: SNat 0).
  shift ns = inclusion
  #-}

lneqLeqTrans :: SNat (n :: Nat) -> SNat m -> SNat l
             -> IsTrue (n <? m) -> IsTrue (m <=? l) -> IsTrue (n <? l)
lneqLeqTrans :: SNat n
-> SNat m
-> SNat l
-> IsTrue (n <? m)
-> IsTrue (m <=? l)
-> IsTrue (n <? l)
lneqLeqTrans SNat n
sn SNat m
sm SNat l
sl IsTrue (n <? m)
nLTm IsTrue (m <=? l)
mLEl =
  (((n <? l) ~ 'True) :~: ((n <? l) ~ 'True))
-> ((((n <? l) ~ 'True) ~ ((n <? l) ~ 'True)) => IsTrue (n <? l))
-> IsTrue (n <? l)
forall k (a :: k) (b :: k) r. (a :~: b) -> ((a ~ b) => r) -> r
withRefl (SNat n -> SNat l -> ((n <? l) ~ 'True) :~: ((n <? l) ~ 'True)
forall (n :: Nat) (m :: Nat).
SNat n -> SNat m -> (n < m) :~: (n < m)
lneqSuccLeq SNat n
sn SNat l
sl) (((((n <? l) ~ 'True) ~ ((n <? l) ~ 'True)) => IsTrue (n <? l))
 -> IsTrue (n <? l))
-> ((((n <? l) ~ 'True) ~ ((n <? l) ~ 'True)) => IsTrue (n <? l))
-> IsTrue (n <? l)
forall a b. (a -> b) -> a -> b
$
  (((n <? m) ~ 'True) :~: ((n <? m) ~ 'True))
-> ((((n <? m) ~ 'True) ~ ((n <? m) ~ 'True)) => IsTrue (n <? l))
-> IsTrue (n <? l)
forall k (a :: k) (b :: k) r. (a :~: b) -> ((a ~ b) => r) -> r
withRefl (SNat n -> SNat m -> ((n <? m) ~ 'True) :~: ((n <? m) ~ 'True)
forall (n :: Nat) (m :: Nat).
SNat n -> SNat m -> (n < m) :~: (n < m)
lneqSuccLeq SNat n
sn SNat m
sm) (((((n <? m) ~ 'True) ~ ((n <? m) ~ 'True)) => IsTrue (n <? l))
 -> IsTrue (n <? l))
-> ((((n <? m) ~ 'True) ~ ((n <? m) ~ 'True)) => IsTrue (n <? l))
-> IsTrue (n <? l)
forall a b. (a -> b) -> a -> b
$
  SNat (n + 1)
-> SNat m
-> SNat l
-> IsTrue (n <? m)
-> IsTrue (m <=? l)
-> IsTrue (n <? l)
forall (n :: Nat) (m :: Nat) (l :: Nat).
SNat n
-> SNat m
-> SNat l
-> IsTrue (n <=? m)
-> IsTrue (m <=? l)
-> IsTrue (n <=? l)
leqTrans (SNat n -> SNat (n + 1)
forall (n :: Nat). SNat n -> SNat (Succ n)
sSucc SNat n
sn) SNat m
sm SNat l
sl IsTrue (n <? m)
nLTm IsTrue (m <=? l)
mLEl

lneqMonotoneR :: forall n m l. SNat n -> SNat m -> SNat l
              -> IsTrue (m <? l) -> IsTrue ((n + m) <? (n + l))
lneqMonotoneR :: SNat n
-> SNat m
-> SNat l
-> IsTrue (m <? l)
-> IsTrue ((n + m) <? (n + l))
lneqMonotoneR SNat n
sn SNat m
sm SNat l
sl IsTrue (m <? l)
mLTl =
  (((m <? l) ~ 'True) :~: ((m <? l) ~ 'True))
-> ((((m <? l) ~ 'True) ~ ((m <? l) ~ 'True)) =>
    IsTrue ((n + m) <? (n + l)))
-> IsTrue ((n + m) <? (n + l))
forall k (a :: k) (b :: k) r. (a :~: b) -> ((a ~ b) => r) -> r
withRefl (SNat m -> SNat l -> ((m <? l) ~ 'True) :~: ((m <? l) ~ 'True)
forall (n :: Nat) (m :: Nat).
SNat n -> SNat m -> (n < m) :~: (n < m)
lneqSuccLeq SNat m
sm SNat l
sl) (((((m <? l) ~ 'True) ~ ((m <? l) ~ 'True)) =>
  IsTrue ((n + m) <? (n + l)))
 -> IsTrue ((n + m) <? (n + l)))
-> ((((m <? l) ~ 'True) ~ ((m <? l) ~ 'True)) =>
    IsTrue ((n + m) <? (n + l)))
-> IsTrue ((n + m) <? (n + l))
forall a b. (a -> b) -> a -> b
$
  ((((n + m) <? (n + l)) ~ 'True) :~: (((n + m) <? (n + l)) ~ 'True))
-> (((((n + m) <? (n + l)) ~ 'True)
     ~ (((n + m) <? (n + l)) ~ 'True)) =>
    IsTrue ((n + m) <? (n + l)))
-> IsTrue ((n + m) <? (n + l))
forall k (a :: k) (b :: k) r. (a :~: b) -> ((a ~ b) => r) -> r
withRefl (SNat (n + m)
-> SNat (n + l)
-> (((n + m) <? (n + l)) ~ 'True)
   :~: (((n + m) <? (n + l)) ~ 'True)
forall (n :: Nat) (m :: Nat).
SNat n -> SNat m -> (n < m) :~: (n < m)
lneqSuccLeq (SNat n
sn SNat n -> SNat m -> SNat (n + m)
forall (n :: Nat) (m :: Nat). SNat n -> SNat m -> SNat (n + m)
%+ SNat m
sm) (SNat n
sn SNat n -> SNat l -> SNat (n + l)
forall (n :: Nat) (m :: Nat). SNat n -> SNat m -> SNat (n + m)
%+ SNat l
sl)) ((((((n + m) <? (n + l)) ~ 'True)
   ~ (((n + m) <? (n + l)) ~ 'True)) =>
  IsTrue ((n + m) <? (n + l)))
 -> IsTrue ((n + m) <? (n + l)))
-> (((((n + m) <? (n + l)) ~ 'True)
     ~ (((n + m) <? (n + l)) ~ 'True)) =>
    IsTrue ((n + m) <? (n + l)))
-> IsTrue ((n + m) <? (n + l))
forall a b. (a -> b) -> a -> b
$
  ((n + (m + 1)) :~: ((n + m) + 1))
-> (((n + (m + 1)) ~ ((n + m) + 1)) => IsTrue ((n + m) <? (n + l)))
-> IsTrue ((n + m) <? (n + l))
forall k (a :: k) (b :: k) r. (a :~: b) -> ((a ~ b) => r) -> r
withRefl (SNat n -> SNat m -> (n + (m + 1)) :~: ((n + m) + 1)
forall (n :: Nat) (m :: Nat).
SNat n -> SNat m -> (n + S m) :~: S (n + m)
plusSuccR SNat n
sn SNat m
sm) ((((n + (m + 1)) ~ ((n + m) + 1)) => IsTrue ((n + m) <? (n + l)))
 -> IsTrue ((n + m) <? (n + l)))
-> (((n + (m + 1)) ~ ((n + m) + 1)) => IsTrue ((n + m) <? (n + l)))
-> IsTrue ((n + m) <? (n + l))
forall a b. (a -> b) -> a -> b
$
  SNat n
-> SNat (m + 1)
-> SNat l
-> IsTrue (m <? l)
-> IsTrue ((n + (m + 1)) <=? (n + l))
forall (n :: Nat) (m :: Nat) (l :: Nat).
SNat n
-> SNat m
-> SNat l
-> IsTrue (m <=? l)
-> IsTrue ((n + m) <=? (n + l))
plusMonotoneR SNat n
sn (SNat m
sm SNat m -> SNat 1 -> SNat (m + 1)
forall (n :: Nat) (m :: Nat). SNat n -> SNat m -> SNat (n + m)
%+ KnownNat 1 => SNat 1
forall (n :: Nat). KnownNat n => SNat n
sNat @1) SNat l
sl (IsTrue (m <? l)
mLTl :: IsTrue ((m + 1) <=? l))

-- | Similar to @'injectVars'@, but @'injectVarsOffset' n f@
--   injects variables into the first but @n@ variables.
--
--   See also @'injectVars'@ and @'injectVarsAtEnd'@.
injectVarsOffset :: forall n r r' . ((n + Arity r <= Arity r'),
                  IsPolynomial r,
                  IsPolynomial r',
                  Coefficient r ~ Coefficient r') => SNat n -> r -> r'
injectVarsOffset :: SNat n -> r -> r'
injectVarsOffset SNat n
sn = (Ordinal (Arity r) -> r') -> r -> r'
forall poly alg.
(IsPolynomial poly, Module (Scalar (Coefficient poly)) alg,
 Ring alg, Commutative alg) =>
(Ordinal (Arity poly) -> alg) -> poly -> alg
liftMap (Ordinal (Arity r') -> r'
forall poly. IsPolynomial poly => Ordinal (Arity poly) -> poly
var (Ordinal (Arity r') -> r')
-> (Ordinal (Arity r) -> Ordinal (Arity r'))
-> Ordinal (Arity r)
-> r'
forall b c a. (b -> c) -> (a -> b) -> a -> c
. SNat n -> Ordinal (Arity r) -> Ordinal (Arity r')
forall (n :: Nat) (m :: Nat) (k :: Nat).
((n + m) <= k, KnownNat m, KnownNat k) =>
SNat n -> Ordinal m -> Ordinal k
shift SNat n
sn)
{-# INLINE [1] injectVarsOffset #-}
{-# RULES
"injectVarsOffset eql" forall (sn :: SNat 0).
 injectVarsOffset sn = injectVars
 #-}

vars :: forall poly. IsPolynomial poly => [poly]
vars :: [poly]
vars = (Ordinal (Arity poly) -> poly) -> [Ordinal (Arity poly)] -> [poly]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
map Ordinal (Arity poly) -> poly
forall poly. IsPolynomial poly => Ordinal (Arity poly) -> poly
var ([Ordinal (Arity poly)] -> [poly])
-> [Ordinal (Arity poly)] -> [poly]
forall a b. (a -> b) -> a -> b
$ SNat (Arity poly) -> [Ordinal (Arity poly)]
forall (n :: Nat). SNat n -> [Ordinal n]
enumOrdinal (Maybe poly -> SNat (Arity poly)
forall poly (proxy :: * -> *).
IsPolynomial poly =>
proxy poly -> SNat (Arity poly)
sArity (Maybe poly
forall a. Maybe a
Nothing :: Maybe poly))

-- | Coefficients which admits pretty-printing
class (P.Show r) => PrettyCoeff r where
  showsCoeff :: Int -> r -> ShowSCoeff
  showsCoeff Int
d r
a = ShowS -> ShowSCoeff
Positive (Int -> r -> ShowS
forall a. Show a => Int -> a -> ShowS
P.showsPrec Int
d r
a)

defaultShowsOrdCoeff :: (P.Show r, Unital r, Group r, P.Ord r)
                     => Int -> r -> ShowSCoeff
defaultShowsOrdCoeff :: Int -> r -> ShowSCoeff
defaultShowsOrdCoeff Int
d r
r
  | r
r r -> r -> Bool
forall a. Eq a => a -> a -> Bool
P.== r -> r
forall r. Group r => r -> r
negate r
forall r. Unital r => r
one = Maybe ShowS -> ShowSCoeff
Negative Maybe ShowS
forall a. Maybe a
Nothing
  | r
r r -> r -> Bool
forall a. Ord a => a -> a -> Bool
P.<  r
forall m. Monoidal m => m
zero = Maybe ShowS -> ShowSCoeff
Negative (ShowS -> Maybe ShowS
forall a. a -> Maybe a
Just (ShowS -> Maybe ShowS) -> ShowS -> Maybe ShowS
forall a b. (a -> b) -> a -> b
$ Int -> r -> ShowS
forall a. Show a => Int -> a -> ShowS
P.showsPrec Int
d (r -> r
forall r. Group r => r -> r
negate r
r))
  | r
r r -> r -> Bool
forall a. Eq a => a -> a -> Bool
P.== r
forall m. Monoidal m => m
zero = ShowSCoeff
Vanished
  | r
r r -> r -> Bool
forall a. Eq a => a -> a -> Bool
P.== r
forall r. Unital r => r
one  = ShowSCoeff
OneCoeff
  | Bool
otherwise   = ShowS -> ShowSCoeff
Positive (Int -> r -> ShowS
forall a. Show a => Int -> a -> ShowS
P.showsPrec Int
d r
r)

instance PrettyCoeff P.Integer where
  showsCoeff :: Int -> Integer -> ShowSCoeff
showsCoeff = Int -> Integer -> ShowSCoeff
forall r.
(Show r, Unital r, Group r, Ord r) =>
Int -> r -> ShowSCoeff
defaultShowsOrdCoeff

instance PrettyCoeff Natural where
  showsCoeff :: Int -> Natural -> ShowSCoeff
showsCoeff Int
d Natural
r
    | Natural
r Natural -> Natural -> Bool
forall a. Eq a => a -> a -> Bool
== Natural
0    = ShowSCoeff
Vanished
    | Bool
otherwise = ShowS -> ShowSCoeff
Positive (Int -> Natural -> ShowS
forall a. Show a => Int -> a -> ShowS
P.showsPrec Int
d Natural
r)

instance PrettyCoeff P.Int where
  showsCoeff :: Int -> Int -> ShowSCoeff
showsCoeff = Int -> Int -> ShowSCoeff
forall r.
(Show r, Unital r, Group r, Ord r) =>
Int -> r -> ShowSCoeff
defaultShowsOrdCoeff

instance PrettyCoeff Int64 where
  showsCoeff :: Int -> Int64 -> ShowSCoeff
showsCoeff = Int -> Int64 -> ShowSCoeff
forall r.
(Show r, Unital r, Group r, Ord r) =>
Int -> r -> ShowSCoeff
defaultShowsOrdCoeff
instance PrettyCoeff Int16 where
  showsCoeff :: Int -> Int16 -> ShowSCoeff
showsCoeff = Int -> Int16 -> ShowSCoeff
forall r.
(Show r, Unital r, Group r, Ord r) =>
Int -> r -> ShowSCoeff
defaultShowsOrdCoeff
instance PrettyCoeff Int32 where
  showsCoeff :: Int -> Int32 -> ShowSCoeff
showsCoeff = Int -> Int32 -> ShowSCoeff
forall r.
(Show r, Unital r, Group r, Ord r) =>
Int -> r -> ShowSCoeff
defaultShowsOrdCoeff
instance PrettyCoeff Int8 where
  showsCoeff :: Int -> Int8 -> ShowSCoeff
showsCoeff = Int -> Int8 -> ShowSCoeff
forall r.
(Show r, Unital r, Group r, Ord r) =>
Int -> r -> ShowSCoeff
defaultShowsOrdCoeff

instance PrettyCoeff Word64 where
  showsCoeff :: Int -> Word64 -> ShowSCoeff
showsCoeff = Int -> Word64 -> ShowSCoeff
forall r.
(Show r, Unital r, Group r, Ord r) =>
Int -> r -> ShowSCoeff
defaultShowsOrdCoeff

instance PrettyCoeff Word16 where
  showsCoeff :: Int -> Word16 -> ShowSCoeff
showsCoeff = Int -> Word16 -> ShowSCoeff
forall r.
(Show r, Unital r, Group r, Ord r) =>
Int -> r -> ShowSCoeff
defaultShowsOrdCoeff

instance PrettyCoeff Word32 where
  showsCoeff :: Int -> Word32 -> ShowSCoeff
showsCoeff = Int -> Word32 -> ShowSCoeff
forall r.
(Show r, Unital r, Group r, Ord r) =>
Int -> r -> ShowSCoeff
defaultShowsOrdCoeff

instance PrettyCoeff Word8 where
  showsCoeff :: Int -> Word8 -> ShowSCoeff
showsCoeff = Int -> Word8 -> ShowSCoeff
forall r.
(Show r, Unital r, Group r, Ord r) =>
Int -> r -> ShowSCoeff
defaultShowsOrdCoeff

instance (P.Integral a, PrettyCoeff a) => PrettyCoeff (R.Ratio a) where
  showsCoeff :: Int -> Ratio a -> ShowSCoeff
showsCoeff Int
d Ratio a
r =
    if Ratio a -> a
forall a. Ratio a -> a
R.denominator Ratio a
r a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
1
    then Int -> a -> ShowSCoeff
forall r. PrettyCoeff r => Int -> r -> ShowSCoeff
showsCoeff Int
10 (Ratio a -> a
forall a. Ratio a -> a
R.numerator Ratio a
r)
    else Int -> Ratio a -> ShowSCoeff
forall r.
(Show r, Unital r, Group r, Ord r) =>
Int -> r -> ShowSCoeff
defaultShowsOrdCoeff Int
d Ratio a
r

instance (PrettyCoeff r) => PrettyCoeff (NA.Complex r) where
  showsCoeff :: Int -> Complex r -> ShowSCoeff
showsCoeff Int
d (NA.Complex r
r r
i) =
    case (Int -> r -> ShowSCoeff
forall r. PrettyCoeff r => Int -> r -> ShowSCoeff
showsCoeff Int
10 r
r, Int -> r -> ShowSCoeff
forall r. PrettyCoeff r => Int -> r -> ShowSCoeff
showsCoeff Int
10 r
i) of
      (ShowSCoeff
Vanished, ShowSCoeff
Vanished)     -> ShowSCoeff
Vanished
      (ShowSCoeff
Vanished, Positive ShowS
s)   -> ShowS -> ShowSCoeff
Positive (ShowS
s ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> ShowS
P.showString String
" I")
      (ShowSCoeff
Vanished, Negative Maybe ShowS
s)   -> Maybe ShowS -> ShowSCoeff
Negative (ShowS -> Maybe ShowS
forall a. a -> Maybe a
Just (ShowS -> Maybe ShowS) -> ShowS -> Maybe ShowS
forall a b. (a -> b) -> a -> b
$ ShowS -> Maybe ShowS -> ShowS
forall a. a -> Maybe a -> a
fromMaybe ShowS
forall a. a -> a
P.id Maybe ShowS
s ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> ShowS
P.showString String
" I")
      (Positive ShowS
s, ShowSCoeff
Vanished)   -> ShowS -> ShowSCoeff
Positive ShowS
s
      (Negative Maybe ShowS
s, ShowSCoeff
Vanished)   -> Maybe ShowS -> ShowSCoeff
Negative Maybe ShowS
s
      (ShowSCoeff
s, ShowSCoeff
t) ->
        ShowS -> ShowSCoeff
Positive (ShowS -> ShowSCoeff) -> ShowS -> ShowSCoeff
forall a b. (a -> b) -> a -> b
$ Bool -> ShowS -> ShowS
P.showParen (Int
d Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
P.> Int
10) (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$
        ShowSCoeff -> ShowS
showsCoeffAsTerm ShowSCoeff
s ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ShowSCoeff -> ShowS
showsCoeffWithOp ShowSCoeff
t

instance {-# OVERLAPPING #-} PrettyCoeff (Fraction P.Integer) where
  showsCoeff :: Int -> Fraction Integer -> ShowSCoeff
showsCoeff Int
d Fraction Integer
r =
      if Fraction Integer -> Integer
forall t. Fraction t -> t
NA.denominator Fraction Integer
r Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
forall r. Unital r => r
one
      then Int -> Integer -> ShowSCoeff
forall r. PrettyCoeff r => Int -> r -> ShowSCoeff
showsCoeff Int
d (Fraction Integer -> Integer
forall t. Fraction t -> t
NA.numerator Fraction Integer
r)
      else Int -> Fraction Integer -> ShowSCoeff
forall r.
(Show r, Unital r, Group r, Ord r) =>
Int -> r -> ShowSCoeff
defaultShowsOrdCoeff Int
d Fraction Integer
r

instance {-# OVERLAPS #-}
  (PrettyCoeff r, Eq r, Euclidean r) => PrettyCoeff (Fraction r) where
    showsCoeff :: Int -> Fraction r -> ShowSCoeff
showsCoeff Int
d Fraction r
r =
      if Fraction r -> r
forall t. Fraction t -> t
NA.denominator Fraction r
r r -> r -> Bool
forall a. Eq a => a -> a -> Bool
== r
forall r. Unital r => r
one
      then Int -> r -> ShowSCoeff
forall r. PrettyCoeff r => Int -> r -> ShowSCoeff
showsCoeff Int
d (Fraction r -> r
forall t. Fraction t -> t
NA.numerator Fraction r
r)
      else ShowS -> ShowSCoeff
Positive (Int -> Fraction r -> ShowS
forall a. Show a => Int -> a -> ShowS
P.showsPrec Int
d Fraction r
r)

-- | Pretty-printing conditional for coefficients.
--   Each returning @'P.ShowS'@ must not have any sign.
data ShowSCoeff = Negative (Maybe P.ShowS)
                | Vanished
                | OneCoeff
                | Positive P.ShowS

-- | ShowS coefficients as term.
--
-- @
-- showsCoeffAsTerm 'Vanished' "" = ""
-- showsCoeffAsTerm ('Negative' (shows "12")) "" = "-12"
-- showsCoeffAsTerm ('Positive' (shows "12")) "" = "12"
-- @
showsCoeffAsTerm :: ShowSCoeff -> P.ShowS
showsCoeffAsTerm :: ShowSCoeff -> ShowS
showsCoeffAsTerm ShowSCoeff
Vanished     = ShowS
forall a. a -> a
P.id
showsCoeffAsTerm (Negative Maybe ShowS
s) = Char -> ShowS
P.showChar Char
'-' ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ShowS -> Maybe ShowS -> ShowS
forall a. a -> Maybe a -> a
fromMaybe (Char -> ShowS
P.showChar Char
'1') Maybe ShowS
s
showsCoeffAsTerm ShowSCoeff
OneCoeff     = Char -> ShowS
P.showChar Char
'1'
showsCoeffAsTerm (Positive ShowS
s) = ShowS
s

-- | ShowS coefficients prefixed with infix operator.
--
-- @
-- (shows 12 . showsCoeffWithOp 'Vanished') "" = "12"
-- (shows 12 . showsCoeffWithOp ('Negative' (shows 34))) "" = "12 - 34"
-- (shows 12 . showsCoeffWithOp ('Positive' (shows 34))) "" = "12 + 34"
-- @
showsCoeffWithOp :: ShowSCoeff -> P.ShowS
showsCoeffWithOp :: ShowSCoeff -> ShowS
showsCoeffWithOp ShowSCoeff
Vanished = ShowS
forall a. a -> a
P.id
showsCoeffWithOp (Negative Maybe ShowS
s) = String -> ShowS
P.showString String
" - " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ShowS -> Maybe ShowS -> ShowS
forall a. a -> Maybe a -> a
fromMaybe (Char -> ShowS
P.showChar Char
'1') Maybe ShowS
s
showsCoeffWithOp ShowSCoeff
OneCoeff     = String -> ShowS
P.showString String
" + 1"
showsCoeffWithOp (Positive ShowS
s) = String -> ShowS
P.showString String
" + " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ShowS
s

showPolynomialWith :: (IsOrderedPolynomial poly, PrettyCoeff (Coefficient poly))
                    => Sized (Arity poly) P.String
                    -> Int
                    -> poly
                    -> P.String
showPolynomialWith :: Sized (Arity poly) String -> Int -> poly -> String
showPolynomialWith Sized (Arity poly) String
vs Int
i poly
p = Sized (Arity poly) String -> Int -> poly -> ShowS
forall poly.
(IsOrderedPolynomial poly, PrettyCoeff (Coefficient poly)) =>
Sized (Arity poly) String -> Int -> poly -> ShowS
showsPolynomialWith Sized (Arity poly) String
vs Int
i poly
p String
""

showPolynomialWith' :: (IsOrderedPolynomial poly)
                     => Bool
                     -> (Int -> Coefficient poly -> ShowSCoeff)
                     -> Sized (Arity poly) P.String
                     -> Int
                     -> poly
                     -> P.String
showPolynomialWith' :: Bool
-> (Int -> Coefficient poly -> ShowSCoeff)
-> Sized (Arity poly) String
-> Int
-> poly
-> String
showPolynomialWith' Bool
b Int -> Coefficient poly -> ShowSCoeff
showsCoe Sized (Arity poly) String
vs Int
i poly
p = Bool
-> (Int -> Coefficient poly -> ShowSCoeff)
-> Sized (Arity poly) String
-> Int
-> poly
-> ShowS
forall poly.
IsOrderedPolynomial poly =>
Bool
-> (Int -> Coefficient poly -> ShowSCoeff)
-> Sized (Arity poly) String
-> Int
-> poly
-> ShowS
showsPolynomialWith' Bool
b Int -> Coefficient poly -> ShowSCoeff
showsCoe Sized (Arity poly) String
vs Int
i poly
p String
""

showsPolynomialWith :: (IsOrderedPolynomial poly, PrettyCoeff (Coefficient poly))
                     => Sized (Arity poly) P.String
                     -> Int
                     -> poly
                     -> P.ShowS
showsPolynomialWith :: Sized (Arity poly) String -> Int -> poly -> ShowS
showsPolynomialWith = Bool
-> (Int -> Coefficient poly -> ShowSCoeff)
-> Sized (Arity poly) String
-> Int
-> poly
-> ShowS
forall poly.
IsOrderedPolynomial poly =>
Bool
-> (Int -> Coefficient poly -> ShowSCoeff)
-> Sized (Arity poly) String
-> Int
-> poly
-> ShowS
showsPolynomialWith' Bool
True Int -> Coefficient poly -> ShowSCoeff
forall r. PrettyCoeff r => Int -> r -> ShowSCoeff
showsCoeff

showsPolynomialWith' :: (IsOrderedPolynomial poly)
                     => Bool
                        -- ^ Whether print multiplication as @*@ or not.
                     -> (Int -> Coefficient poly -> ShowSCoeff)
                        -- ^ Coefficient printer
                     -> Sized (Arity poly) P.String
                        -- ^ Variables
                     -> Int
                        -- ^ Precision
                     -> poly
                        -- ^ Polynomial
                     -> P.ShowS
showsPolynomialWith' :: Bool
-> (Int -> Coefficient poly -> ShowSCoeff)
-> Sized (Arity poly) String
-> Int
-> poly
-> ShowS
showsPolynomialWith' Bool
showMult Int -> Coefficient poly -> ShowSCoeff
showsCoe Sized (Arity poly) String
vsVec Int
d poly
f = Bool -> ShowS -> ShowS
P.showParen (Int
d Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
P.> Int
10) (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$
  let tms :: [(Maybe ShowS, ShowSCoeff)]
tms  = ((OrderedMonomial (MOrder poly) (Arity poly), Coefficient poly)
 -> (Maybe ShowS, ShowSCoeff))
-> [(OrderedMonomial (MOrder poly) (Arity poly), Coefficient poly)]
-> [(Maybe ShowS, ShowSCoeff)]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
map (OrderedMonomial (MOrder poly) (Arity poly) -> Maybe ShowS
showMonom (OrderedMonomial (MOrder poly) (Arity poly) -> Maybe ShowS)
-> (Coefficient poly -> ShowSCoeff)
-> (OrderedMonomial (MOrder poly) (Arity poly), Coefficient poly)
-> (Maybe ShowS, ShowSCoeff)
forall (a :: * -> * -> *) b c b' c'.
Arrow a =>
a b c -> a b' c' -> a (b, b') (c, c')
*** Int -> Coefficient poly -> ShowSCoeff
showsCoe Int
10) ([(OrderedMonomial (MOrder poly) (Arity poly), Coefficient poly)]
 -> [(Maybe ShowS, ShowSCoeff)])
-> [(OrderedMonomial (MOrder poly) (Arity poly), Coefficient poly)]
-> [(Maybe ShowS, ShowSCoeff)]
forall a b. (a -> b) -> a -> b
$ Map (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
-> [(OrderedMonomial (MOrder poly) (Arity poly), Coefficient poly)]
forall k a. Map k a -> [(k, a)]
M.toDescList (Map
   (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
 -> [(OrderedMonomial (MOrder poly) (Arity poly),
      Coefficient poly)])
-> Map
     (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
-> [(OrderedMonomial (MOrder poly) (Arity poly), Coefficient poly)]
forall a b. (a -> b) -> a -> b
$ poly
-> Map
     (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
forall poly.
IsOrderedPolynomial poly =>
poly
-> Map
     (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
terms poly
f
  in case [(Maybe ShowS, ShowSCoeff)]
tms of
    [] -> String -> ShowS
P.showString String
"0"
    ((Maybe ShowS, ShowSCoeff)
mc : [(Maybe ShowS, ShowSCoeff)]
ts) -> (ShowS -> ShowS -> ShowS) -> [ShowS] -> ShowS
forall (t :: * -> *) a. Foldable t => (a -> a -> a) -> t a -> a
P.foldr1 ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
(.) ([ShowS] -> ShowS) -> [ShowS] -> ShowS
forall a b. (a -> b) -> a -> b
$ (Maybe ShowS, ShowSCoeff) -> ShowS
showTermOnly (Maybe ShowS, ShowSCoeff)
mc ShowS -> [ShowS] -> [ShowS]
forall a. a -> [a] -> [a]
: ((Maybe ShowS, ShowSCoeff) -> ShowS)
-> [(Maybe ShowS, ShowSCoeff)] -> [ShowS]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
map (Maybe ShowS, ShowSCoeff) -> ShowS
showRestTerm [(Maybe ShowS, ShowSCoeff)]
ts
  where
    showTermOnly :: (Maybe ShowS, ShowSCoeff) -> ShowS
showTermOnly (Maybe ShowS
Nothing, ShowSCoeff
Vanished) = ShowS
forall a. a -> a
P.id
    showTermOnly (Maybe ShowS
Nothing, ShowSCoeff
s)        = ShowSCoeff -> ShowS
showsCoeffAsTerm ShowSCoeff
s
    showTermOnly (Just ShowS
m, ShowSCoeff
OneCoeff)  = ShowS
m
    showTermOnly (Just ShowS
m, Negative Maybe ShowS
Nothing) = Char -> ShowS
P.showChar Char
'-' ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ShowS
m
    showTermOnly (Just ShowS
_, ShowSCoeff
Vanished)  = ShowS
forall a. a -> a
P.id
    showTermOnly (Just ShowS
m, ShowSCoeff
t)         = ShowSCoeff -> ShowS
showsCoeffAsTerm ShowSCoeff
t ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> ShowS
P.showChar Char
multSymb ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ShowS
m
    showRestTerm :: (Maybe ShowS, ShowSCoeff) -> ShowS
showRestTerm (Maybe ShowS
Nothing, ShowSCoeff
Vanished) = ShowS
forall a. a -> a
P.id
    showRestTerm (Maybe ShowS
Nothing, ShowSCoeff
s)        = ShowSCoeff -> ShowS
showsCoeffWithOp ShowSCoeff
s
    showRestTerm (Just ShowS
m, ShowSCoeff
OneCoeff)  = String -> ShowS
P.showString String
" + " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ShowS
m
    showRestTerm (Just ShowS
m, Negative Maybe ShowS
Nothing)  = String -> ShowS
P.showString String
" - " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ShowS
m
    showRestTerm (Just ShowS
_, ShowSCoeff
Vanished)  = ShowS
forall a. a -> a
P.id
    showRestTerm (Just ShowS
m, ShowSCoeff
t)         = ShowSCoeff -> ShowS
showsCoeffWithOp ShowSCoeff
t ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> ShowS
P.showChar Char
multSymb ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ShowS
m
    vs :: [String]
vs = Sized (Arity poly) String -> [String]
forall (t :: * -> *) a. Foldable t => t a -> [a]
F.toList Sized (Arity poly) String
vsVec
    multSymb :: Char
multSymb | Bool
showMult  = Char
'*'
             | Bool
otherwise = Char
' '
    showMonom :: OrderedMonomial (MOrder poly) (Arity poly) -> Maybe ShowS
showMonom OrderedMonomial (MOrder poly) (Arity poly)
m =
      let fs :: [String]
fs = [Maybe String] -> [String]
forall a. [Maybe a] -> [a]
catMaybes ([Maybe String] -> [String]) -> [Maybe String] -> [String]
forall a b. (a -> b) -> a -> b
$ (String -> Int -> Maybe String)
-> [String] -> [Int] -> [Maybe String]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
P.zipWith String -> Int -> Maybe String
forall a. (Eq a, Num a, Show a) => String -> a -> Maybe String
showFactor [String]
vs ([Int] -> [Maybe String]) -> [Int] -> [Maybe String]
forall a b. (a -> b) -> a -> b
$ Monomial (Arity poly) -> [Element (Monomial (Arity poly))]
forall mono. MonoFoldable mono => mono -> [Element mono]
otoList (Monomial (Arity poly) -> [Element (Monomial (Arity poly))])
-> Monomial (Arity poly) -> [Element (Monomial (Arity poly))]
forall a b. (a -> b) -> a -> b
$ OrderedMonomial (MOrder poly) (Arity poly) -> Monomial (Arity poly)
forall k (ordering :: k) (n :: Nat).
OrderedMonomial ordering n -> Monomial n
getMonomial OrderedMonomial (MOrder poly) (Arity poly)
m
      in if [String] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
P.null [String]
fs
         then Maybe ShowS
forall a. Maybe a
Nothing
         else ShowS -> Maybe ShowS
forall a. a -> Maybe a
Just (ShowS -> Maybe ShowS) -> ShowS -> Maybe ShowS
forall a b. (a -> b) -> a -> b
$ (ShowS -> ShowS -> ShowS) -> ShowS -> [ShowS] -> ShowS
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
(.) ShowS
forall a. a -> a
P.id ([ShowS] -> ShowS) -> [ShowS] -> ShowS
forall a b. (a -> b) -> a -> b
$ ShowS -> [ShowS] -> [ShowS]
forall a. a -> [a] -> [a]
L.intersperse (Char -> ShowS
P.showChar Char
multSymb) ((String -> ShowS) -> [String] -> [ShowS]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
map String -> ShowS
P.showString [String]
fs)
    showFactor :: String -> a -> Maybe String
showFactor String
_ a
0 = Maybe String
forall a. Maybe a
Nothing
    showFactor String
v a
1 = String -> Maybe String
forall a. a -> Maybe a
Just String
v
    showFactor String
v a
n = String -> Maybe String
forall a. a -> Maybe a
Just (String -> Maybe String) -> String -> Maybe String
forall a b. (a -> b) -> a -> b
$ String
v String -> ShowS
forall a. [a] -> [a] -> [a]
P.++ String
"^" String -> ShowS
forall a. [a] -> [a] -> [a]
P.++ a -> String
forall a. Show a => a -> String
P.show a
n

-- | Calculate a polynomial quotient and remainder w.r.t. second argument.
divModPolynomial :: forall poly. (IsOrderedPolynomial poly, Field (Coefficient poly))
                 => poly -> [poly]
                 -> ([(poly, poly)], poly)
divModPolynomial :: poly -> [poly] -> ([(poly, poly)], poly)
divModPolynomial poly
f0 [poly]
fs = poly
-> poly
-> [(((Coefficient poly,
       OrderedMonomial (MOrder poly) (Arity poly)),
      poly),
     poly)]
-> ([(poly, poly)], poly)
forall r t.
(IsOrderedPolynomial r, IsOrderedPolynomial t,
 Euclidean (Coefficient r), Division (Coefficient r),
 Coefficient t ~ Coefficient r, MOrder r ~ MOrder t) =>
r
-> t
-> [(((Coefficient r, OrderedMonomial (MOrder t) (Arity r)), r),
     r)]
-> ([(r, r)], t)
loop poly
f0 poly
forall m. Monoidal m => m
zero ([((Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly)),
  poly)]
-> [poly]
-> [(((Coefficient poly,
       OrderedMonomial (MOrder poly) (Arity poly)),
      poly),
     poly)]
forall a b. [a] -> [b] -> [(a, b)]
P.zip ((poly
 -> ((Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly)),
     poly))
-> [poly]
-> [((Coefficient poly,
      OrderedMonomial (MOrder poly) (Arity poly)),
     poly)]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
map poly
-> ((Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly)),
    poly)
forall poly.
IsOrderedPolynomial poly =>
poly
-> ((Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly)),
    poly)
splitLeadingTerm ([poly]
 -> [((Coefficient poly,
       OrderedMonomial (MOrder poly) (Arity poly)),
      poly)])
-> [poly]
-> [((Coefficient poly,
      OrderedMonomial (MOrder poly) (Arity poly)),
     poly)]
forall a b. (a -> b) -> a -> b
$ [poly] -> [poly]
forall a. Eq a => [a] -> [a]
L.nub [poly]
fs) (poly -> [poly]
forall a. a -> [a]
P.repeat poly
forall m. Monoidal m => m
zero))
  where
    loop :: r
-> t
-> [(((Coefficient r, OrderedMonomial (MOrder t) (Arity r)), r),
     r)]
-> ([(r, r)], t)
loop r
p t
r [(((Coefficient r, OrderedMonomial (MOrder t) (Arity r)), r), r)]
dic
        | r -> Bool
forall r. DecidableZero r => r -> Bool
isZero r
p = (((((Coefficient r, OrderedMonomial (MOrder t) (Arity r)), r), r)
 -> (r, r))
-> [(((Coefficient r, OrderedMonomial (MOrder t) (Arity r)), r),
     r)]
-> [(r, r)]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
map ((((Coefficient r, OrderedMonomial (MOrder r) (Arity r)), r) -> r)
-> (((Coefficient r, OrderedMonomial (MOrder r) (Arity r)), r), r)
-> (r, r)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first ((((Coefficient r, OrderedMonomial (MOrder r) (Arity r)), r) -> r)
 -> (((Coefficient r, OrderedMonomial (MOrder r) (Arity r)), r), r)
 -> (r, r))
-> (((Coefficient r, OrderedMonomial (MOrder r) (Arity r)), r)
    -> r)
-> (((Coefficient r, OrderedMonomial (MOrder r) (Arity r)), r), r)
-> (r, r)
forall a b. (a -> b) -> a -> b
$ \((Coefficient r, OrderedMonomial (MOrder r) (Arity r))
lt, r
q) -> (Coefficient r, OrderedMonomial (MOrder r) (Arity r)) -> r
forall poly.
IsOrderedPolynomial poly =>
(Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
-> poly
toPolynomial (Coefficient r, OrderedMonomial (MOrder r) (Arity r))
lt r -> r -> r
forall r. Additive r => r -> r -> r
+ r
q) [(((Coefficient r, OrderedMonomial (MOrder t) (Arity r)), r), r)]
dic, t
r)
        | Bool
otherwise =
            let ((Coefficient r, OrderedMonomial (MOrder t) (Arity r))
ltP, r
p') = r -> ((Coefficient r, OrderedMonomial (MOrder r) (Arity r)), r)
forall poly.
IsOrderedPolynomial poly =>
poly
-> ((Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly)),
    poly)
splitLeadingTerm r
p
            in case ((((Coefficient r, OrderedMonomial (MOrder t) (Arity r)), r), r)
 -> Bool)
-> [(((Coefficient r, OrderedMonomial (MOrder t) (Arity r)), r),
     r)]
-> ([(((Coefficient r, OrderedMonomial (MOrder t) (Arity r)), r),
      r)],
    [(((Coefficient r, OrderedMonomial (MOrder t) (Arity r)), r), r)])
forall a. (a -> Bool) -> [a] -> ([a], [a])
L.break ((OrderedMonomial (MOrder t) (Arity r)
-> OrderedMonomial (MOrder t) (Arity r) -> Bool
forall k (n :: Nat) (ord :: k).
KnownNat n =>
OrderedMonomial ord n -> OrderedMonomial ord n -> Bool
`divs` (Coefficient r, OrderedMonomial (MOrder t) (Arity r))
-> OrderedMonomial (MOrder t) (Arity r)
forall a b. (a, b) -> b
snd (Coefficient r, OrderedMonomial (MOrder t) (Arity r))
ltP) (OrderedMonomial (MOrder t) (Arity r) -> Bool)
-> ((((Coefficient r, OrderedMonomial (MOrder t) (Arity r)), r), r)
    -> OrderedMonomial (MOrder t) (Arity r))
-> (((Coefficient r, OrderedMonomial (MOrder t) (Arity r)), r), r)
-> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Coefficient r, OrderedMonomial (MOrder t) (Arity r))
-> OrderedMonomial (MOrder t) (Arity r)
forall a b. (a, b) -> b
snd ((Coefficient r, OrderedMonomial (MOrder t) (Arity r))
 -> OrderedMonomial (MOrder t) (Arity r))
-> ((((Coefficient r, OrderedMonomial (MOrder t) (Arity r)), r), r)
    -> (Coefficient r, OrderedMonomial (MOrder t) (Arity r)))
-> (((Coefficient r, OrderedMonomial (MOrder t) (Arity r)), r), r)
-> OrderedMonomial (MOrder t) (Arity r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Coefficient r, OrderedMonomial (MOrder t) (Arity r)), r)
-> (Coefficient r, OrderedMonomial (MOrder t) (Arity r))
forall a b. (a, b) -> a
fst (((Coefficient r, OrderedMonomial (MOrder t) (Arity r)), r)
 -> (Coefficient r, OrderedMonomial (MOrder t) (Arity r)))
-> ((((Coefficient r, OrderedMonomial (MOrder t) (Arity r)), r), r)
    -> ((Coefficient r, OrderedMonomial (MOrder t) (Arity r)), r))
-> (((Coefficient r, OrderedMonomial (MOrder t) (Arity r)), r), r)
-> (Coefficient r, OrderedMonomial (MOrder t) (Arity r))
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (((Coefficient r, OrderedMonomial (MOrder t) (Arity r)), r), r)
-> ((Coefficient r, OrderedMonomial (MOrder t) (Arity r)), r)
forall a b. (a, b) -> a
fst) [(((Coefficient r, OrderedMonomial (MOrder t) (Arity r)), r), r)]
dic of
                 ([(((Coefficient r, OrderedMonomial (MOrder t) (Arity r)), r), r)]
_, []) -> r
-> t
-> [(((Coefficient r, OrderedMonomial (MOrder t) (Arity r)), r),
     r)]
-> ([(r, r)], t)
loop r
p' (t
r t -> t -> t
forall r. Additive r => r -> r -> r
+ (Coefficient t, OrderedMonomial (MOrder t) (Arity t)) -> t
forall poly.
IsOrderedPolynomial poly =>
(Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
-> poly
toPolynomial (Coefficient t, OrderedMonomial (MOrder t) (Arity t))
(Coefficient r, OrderedMonomial (MOrder t) (Arity r))
ltP) [(((Coefficient r, OrderedMonomial (MOrder t) (Arity r)), r), r)]
dic
                 ([(((Coefficient r, OrderedMonomial (MOrder t) (Arity r)), r), r)]
xs, (((Coefficient r, OrderedMonomial (MOrder t) (Arity r))
ltG, r
g), r
old):[(((Coefficient r, OrderedMonomial (MOrder t) (Arity r)), r), r)]
ys) ->
                     let q :: r
q = (Coefficient r, OrderedMonomial (MOrder r) (Arity r)) -> r
forall poly.
IsOrderedPolynomial poly =>
(Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
-> poly
toPolynomial ((Coefficient r, OrderedMonomial (MOrder r) (Arity r)) -> r)
-> (Coefficient r, OrderedMonomial (MOrder r) (Arity r)) -> r
forall a b. (a -> b) -> a -> b
$ (Coefficient r, OrderedMonomial (MOrder t) (Arity r))
ltP (Coefficient r, OrderedMonomial (MOrder t) (Arity r))
-> (Coefficient r, OrderedMonomial (MOrder t) (Arity r))
-> (Coefficient r, OrderedMonomial (MOrder t) (Arity r))
forall k (n :: Nat) r (ord :: k).
(KnownNat n, Field r) =>
(r, OrderedMonomial ord n)
-> (r, OrderedMonomial ord n) -> (r, OrderedMonomial ord n)
`tryDiv` (Coefficient r, OrderedMonomial (MOrder t) (Arity r))
ltG
                         dic' :: [(((Coefficient r, OrderedMonomial (MOrder t) (Arity r)), r), r)]
dic' = [(((Coefficient r, OrderedMonomial (MOrder t) (Arity r)), r), r)]
xs [(((Coefficient r, OrderedMonomial (MOrder t) (Arity r)), r), r)]
-> [(((Coefficient r, OrderedMonomial (MOrder t) (Arity r)), r),
     r)]
-> [(((Coefficient r, OrderedMonomial (MOrder t) (Arity r)), r),
     r)]
forall a. [a] -> [a] -> [a]
P.++ (((Coefficient r, OrderedMonomial (MOrder t) (Arity r))
ltG, r
g), r
old r -> r -> r
forall r. Additive r => r -> r -> r
+ r
q) (((Coefficient r, OrderedMonomial (MOrder t) (Arity r)), r), r)
-> [(((Coefficient r, OrderedMonomial (MOrder t) (Arity r)), r),
     r)]
-> [(((Coefficient r, OrderedMonomial (MOrder t) (Arity r)), r),
     r)]
forall a. a -> [a] -> [a]
: [(((Coefficient r, OrderedMonomial (MOrder t) (Arity r)), r), r)]
ys
                     in r
-> t
-> [(((Coefficient r, OrderedMonomial (MOrder t) (Arity r)), r),
     r)]
-> ([(r, r)], t)
loop (r
p' r -> r -> r
forall r. Group r => r -> r -> r
- (r
q r -> r -> r
forall r. Multiplicative r => r -> r -> r
* r
g)) t
r [(((Coefficient r, OrderedMonomial (MOrder t) (Arity r)), r), r)]
dic'
{-# INLINABLE [2] divModPolynomial #-}

-- | Remainder of given polynomial w.r.t. the second argument.
modPolynomial :: (IsOrderedPolynomial poly, Field (Coefficient poly), Functor t, Foldable t)
              => poly -> t poly -> poly
modPolynomial :: poly -> t poly -> poly
modPolynomial poly
p t poly
rs0 = poly -> poly -> poly
loop poly
p poly
forall m. Monoidal m => m
zero
  where
    rs :: t ((Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly)),
   poly)
rs = (poly
 -> ((Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly)),
     poly))
-> t poly
-> t ((Coefficient poly,
       OrderedMonomial (MOrder poly) (Arity poly)),
      poly)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
map poly
-> ((Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly)),
    poly)
forall poly.
IsOrderedPolynomial poly =>
poly
-> ((Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly)),
    poly)
splitLeadingTerm t poly
rs0
    step :: b
-> ((Coefficient b, OrderedMonomial (MOrder b) (Arity b)), b)
-> m b
step b
r ((Coefficient b, OrderedMonomial (MOrder b) (Arity b))
ltQ, b
q) =  do
      let ((Coefficient b, OrderedMonomial (MOrder b) (Arity b))
ltR, b
r') = b -> ((Coefficient b, OrderedMonomial (MOrder b) (Arity b)), b)
forall poly.
IsOrderedPolynomial poly =>
poly
-> ((Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly)),
    poly)
splitLeadingTerm b
r
          lt :: (Coefficient b, OrderedMonomial (MOrder b) (Arity b))
lt  = (Coefficient b, OrderedMonomial (MOrder b) (Arity b))
ltR (Coefficient b, OrderedMonomial (MOrder b) (Arity b))
-> (Coefficient b, OrderedMonomial (MOrder b) (Arity b))
-> (Coefficient b, OrderedMonomial (MOrder b) (Arity b))
forall k (n :: Nat) r (ord :: k).
(KnownNat n, Field r) =>
(r, OrderedMonomial ord n)
-> (r, OrderedMonomial ord n) -> (r, OrderedMonomial ord n)
`tryDiv` (Coefficient b, OrderedMonomial (MOrder b) (Arity b))
ltQ
      Bool -> m ()
forall (f :: * -> *). Alternative f => Bool -> f ()
guard (Bool -> m ()) -> Bool -> m ()
forall a b. (a -> b) -> a -> b
$ Bool -> Bool
not (b -> Bool
forall r. DecidableZero r => r -> Bool
isZero b
r Bool -> Bool -> Bool
|| Coefficient b -> Bool
forall r. DecidableZero r => r -> Bool
isZero ((Coefficient b, OrderedMonomial (MOrder b) (Arity b))
-> Coefficient b
forall a b. (a, b) -> a
fst (Coefficient b, OrderedMonomial (MOrder b) (Arity b))
ltQ)) Bool -> Bool -> Bool
&& (Coefficient b, OrderedMonomial (MOrder b) (Arity b))
-> OrderedMonomial (MOrder b) (Arity b)
forall a b. (a, b) -> b
snd (Coefficient b, OrderedMonomial (MOrder b) (Arity b))
ltQ OrderedMonomial (MOrder b) (Arity b)
-> OrderedMonomial (MOrder b) (Arity b) -> Bool
forall k (n :: Nat) (ord :: k).
KnownNat n =>
OrderedMonomial ord n -> OrderedMonomial ord n -> Bool
`divs` (Coefficient b, OrderedMonomial (MOrder b) (Arity b))
-> OrderedMonomial (MOrder b) (Arity b)
forall a b. (a, b) -> b
snd (Coefficient b, OrderedMonomial (MOrder b) (Arity b))
ltR
      b -> m b
forall (m :: * -> *) a. Monad m => a -> m a
return (b -> m b) -> b -> m b
forall a b. (a -> b) -> a -> b
$ b
r' b -> b -> b
forall r. Group r => r -> r -> r
- (Coefficient b, OrderedMonomial (MOrder b) (Arity b)) -> b
forall poly.
IsOrderedPolynomial poly =>
(Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
-> poly
toPolynomial (Coefficient b, OrderedMonomial (MOrder b) (Arity b))
lt b -> b -> b
forall r. Multiplicative r => r -> r -> r
* b
q
    loop :: poly -> poly -> poly
loop !poly
q !poly
r
      | poly -> Bool
forall r. DecidableZero r => r -> Bool
isZero poly
q = poly
r
      | Bool
otherwise =
          case First poly -> Maybe poly
forall a. First a -> Maybe a
getFirst (First poly -> Maybe poly) -> First poly -> Maybe poly
forall a b. (a -> b) -> a -> b
$ (((Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly)),
  poly)
 -> First poly)
-> t ((Coefficient poly,
       OrderedMonomial (MOrder poly) (Arity poly)),
      poly)
-> First poly
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap (Maybe poly -> First poly
forall a. Maybe a -> First a
First (Maybe poly -> First poly)
-> (((Coefficient poly,
      OrderedMonomial (MOrder poly) (Arity poly)),
     poly)
    -> Maybe poly)
-> ((Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly)),
    poly)
-> First poly
forall b c a. (b -> c) -> (a -> b) -> a -> c
. poly
-> ((Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly)),
    poly)
-> Maybe poly
forall b (m :: * -> *).
(IsOrderedPolynomial b, Euclidean (Coefficient b),
 Division (Coefficient b), Monad m, Alternative m) =>
b
-> ((Coefficient b, OrderedMonomial (MOrder b) (Arity b)), b)
-> m b
step poly
q) t ((Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly)),
   poly)
rs of
            Just poly
q' -> poly -> poly -> poly
loop poly
q' poly
r
            Maybe poly
Nothing ->
              let ((Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
lt, poly
q') = poly
-> ((Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly)),
    poly)
forall poly.
IsOrderedPolynomial poly =>
poly
-> ((Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly)),
    poly)
splitLeadingTerm poly
q
              in poly -> poly -> poly
loop poly
q' (poly
r poly -> poly -> poly
forall r. Additive r => r -> r -> r
+ (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
-> poly
forall poly.
IsOrderedPolynomial poly =>
(Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
-> poly
toPolynomial (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
lt)
{-# SPECIALISE
 modPolynomial :: (IsOrderedPolynomial poly, Field (Coefficient poly))
                => poly -> [poly] -> poly
 #-}

{-# RULES
"snd . divModPolynomial"
  (snd .) . divModPolynomial = modPolynomial
"snd . divModPolynomial p" forall p.
  snd . divModPolynomial p = modPolynomial p
"snd (divModPolynomial p qs)" forall p qs.
  snd (divModPolynomial p qs) = modPolynomial p qs
 #-}

-- | A Quotient of given polynomial w.r.t. the second argument.
divPolynomial :: (IsOrderedPolynomial poly, Field (Coefficient poly))
              => poly -> [poly] -> [(poly, poly)]
divPolynomial :: poly -> [poly] -> [(poly, poly)]
divPolynomial = (([(poly, poly)], poly) -> [(poly, poly)]
forall a b. (a, b) -> a
fst (([(poly, poly)], poly) -> [(poly, poly)])
-> ([poly] -> ([(poly, poly)], poly)) -> [poly] -> [(poly, poly)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
.) (([poly] -> ([(poly, poly)], poly)) -> [poly] -> [(poly, poly)])
-> (poly -> [poly] -> ([(poly, poly)], poly))
-> poly
-> [poly]
-> [(poly, poly)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. poly -> [poly] -> ([(poly, poly)], poly)
forall poly.
(IsOrderedPolynomial poly, Field (Coefficient poly)) =>
poly -> [poly] -> ([(poly, poly)], poly)
divModPolynomial

infixl 7 `divPolynomial`
infixl 7 `modPolynomial`
infixl 7 `divModPolynomial`

isUnitDefault :: (DecidableUnits r, Coefficient poly ~ r, IsPolynomial poly)
              => poly -> Bool
isUnitDefault :: poly -> Bool
isUnitDefault poly
p = poly -> Int
forall poly. IsPolynomial poly => poly -> Int
totalDegree' poly
p Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0 Bool -> Bool -> Bool
&& r -> Bool
forall r. DecidableUnits r => r -> Bool
isUnit (poly -> Coefficient poly
forall poly. IsPolynomial poly => poly -> Coefficient poly
constantTerm poly
p)

recipUnitDefault :: (DecidableUnits r, Coefficient poly ~ r, IsPolynomial poly)
                 => poly -> Maybe poly
recipUnitDefault :: poly -> Maybe poly
recipUnitDefault poly
p
  | poly -> Bool
forall r poly.
(DecidableUnits r, Coefficient poly ~ r, IsPolynomial poly) =>
poly -> Bool
isUnitDefault poly
p = (r -> poly) -> Maybe r -> Maybe poly
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap r -> poly
forall poly. IsPolynomial poly => Coefficient poly -> poly
injectCoeff (Maybe r -> Maybe poly) -> Maybe r -> Maybe poly
forall a b. (a -> b) -> a -> b
$ r -> Maybe r
forall r. DecidableUnits r => r -> Maybe r
recipUnit (r -> Maybe r) -> r -> Maybe r
forall a b. (a -> b) -> a -> b
$ poly -> Coefficient poly
forall poly. IsPolynomial poly => poly -> Coefficient poly
constantTerm poly
p
  | Bool
otherwise = Maybe poly
forall a. Maybe a
Nothing

isAssociateDefault :: (UnitNormalForm r, Coefficient poly ~ r, IsOrderedPolynomial poly)
                 => poly -> poly -> Bool
isAssociateDefault :: poly -> poly -> Bool
isAssociateDefault poly
p poly
q =
  let up :: r
up = Maybe r -> r
forall a. HasCallStack => Maybe a -> a
fromJust (Maybe r -> r) -> Maybe r -> r
forall a b. (a -> b) -> a -> b
$ r -> Maybe r
forall r. DecidableUnits r => r -> Maybe r
recipUnit (r -> Maybe r) -> r -> Maybe r
forall a b. (a -> b) -> a -> b
$ r -> r
forall r. UnitNormalForm r => r -> r
leadingUnit (r -> r) -> r -> r
forall a b. (a -> b) -> a -> b
$ (r, OrderedMonomial (MOrder poly) (Arity poly)) -> r
forall a b. (a, b) -> a
fst ((r, OrderedMonomial (MOrder poly) (Arity poly)) -> r)
-> (r, OrderedMonomial (MOrder poly) (Arity poly)) -> r
forall a b. (a -> b) -> a -> b
$ poly
-> (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
forall poly.
IsOrderedPolynomial poly =>
poly
-> (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
leadingTerm poly
p
      uq :: r
uq = Maybe r -> r
forall a. HasCallStack => Maybe a -> a
fromJust (Maybe r -> r) -> Maybe r -> r
forall a b. (a -> b) -> a -> b
$ r -> Maybe r
forall r. DecidableUnits r => r -> Maybe r
recipUnit (r -> Maybe r) -> r -> Maybe r
forall a b. (a -> b) -> a -> b
$ r -> r
forall r. UnitNormalForm r => r -> r
leadingUnit (r -> r) -> r -> r
forall a b. (a -> b) -> a -> b
$ (r, OrderedMonomial (MOrder poly) (Arity poly)) -> r
forall a b. (a, b) -> a
fst ((r, OrderedMonomial (MOrder poly) (Arity poly)) -> r)
-> (r, OrderedMonomial (MOrder poly) (Arity poly)) -> r
forall a b. (a -> b) -> a -> b
$ poly
-> (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
forall poly.
IsOrderedPolynomial poly =>
poly
-> (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
leadingTerm poly
q
  in (r
Coefficient poly
up Coefficient poly -> poly -> poly
forall poly. IsPolynomial poly => Coefficient poly -> poly -> poly
!* poly
q) poly -> poly -> Bool
forall a. Eq a => a -> a -> Bool
== (r
Coefficient poly
uq Coefficient poly -> poly -> poly
forall poly. IsPolynomial poly => Coefficient poly -> poly -> poly
!* poly
p)

splitUnitDefault :: (UnitNormalForm r, Coefficient poly ~ r, IsOrderedPolynomial poly)
                 => poly -> (poly, poly)
splitUnitDefault :: poly -> (poly, poly)
splitUnitDefault poly
f =
  let u :: r
u = r -> r
forall r. UnitNormalForm r => r -> r
leadingUnit (r -> r) -> r -> r
forall a b. (a -> b) -> a -> b
$ poly -> Coefficient poly
forall poly. IsOrderedPolynomial poly => poly -> Coefficient poly
leadingCoeff poly
f
      u' :: r
u' = Maybe r -> r
forall a. HasCallStack => Maybe a -> a
fromJust (Maybe r -> r) -> Maybe r -> r
forall a b. (a -> b) -> a -> b
$ r -> Maybe r
forall r. DecidableUnits r => r -> Maybe r
recipUnit r
u
  in (Coefficient poly -> poly
forall poly. IsPolynomial poly => Coefficient poly -> poly
injectCoeff r
Coefficient poly
u, r
Coefficient poly
u' Coefficient poly -> poly -> poly
forall poly. IsPolynomial poly => Coefficient poly -> poly -> poly
!* poly
f)


-- | Conversion between polynomials with the same monomial orderings,
--   coefficents and variables.
convertPolynomial :: ( IsOrderedPolynomial poly, IsOrderedPolynomial poly'
                     , Coefficient poly ~ Coefficient poly'
                     , MOrder poly ~ MOrder poly', Arity poly ~ Arity poly'
                     )
                  => poly -> poly'
convertPolynomial :: poly -> poly'
convertPolynomial = Map
  (OrderedMonomial (MOrder poly') (Arity poly')) (Coefficient poly')
-> poly'
forall poly.
IsOrderedPolynomial poly =>
Map (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
-> poly
polynomial (Map
   (OrderedMonomial (MOrder poly') (Arity poly')) (Coefficient poly')
 -> poly')
-> (poly
    -> Map
         (OrderedMonomial (MOrder poly') (Arity poly')) (Coefficient poly'))
-> poly
-> poly'
forall b c a. (b -> c) -> (a -> b) -> a -> c
. poly
-> Map
     (OrderedMonomial (MOrder poly') (Arity poly')) (Coefficient poly')
forall poly.
IsOrderedPolynomial poly =>
poly
-> Map
     (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
terms
{-# INLINE [3] convertPolynomial #-}
{-# RULES
"convertPolynomial id" [~3] convertPolynomial = id
  #-}

-- | Conversion between polynomials with the same monomial coefficents and variables.
convertPolynomial' :: ( IsOrderedPolynomial poly, IsOrderedPolynomial poly'
                      , Coefficient poly ~ Coefficient poly'
                      , Arity poly ~ Arity poly'
                      )
                   => poly -> poly'
convertPolynomial' :: poly -> poly'
convertPolynomial' = Map (Sized Vector (Arity poly') Int) (Coefficient poly') -> poly'
forall poly.
IsPolynomial poly =>
Map (Monomial (Arity poly)) (Coefficient poly) -> poly
polynomial' (Map (Sized Vector (Arity poly') Int) (Coefficient poly') -> poly')
-> (poly
    -> Map (Sized Vector (Arity poly') Int) (Coefficient poly'))
-> poly
-> poly'
forall b c a. (b -> c) -> (a -> b) -> a -> c
. poly -> Map (Sized Vector (Arity poly') Int) (Coefficient poly')
forall poly.
IsPolynomial poly =>
poly -> Map (Monomial (Arity poly)) (Coefficient poly)
terms'
{-# INLINE [3] convertPolynomial' #-}
{-# RULES
"convertPolynomial' id" [~3] convertPolynomial' = id
  #-}

mapPolynomial :: (IsOrderedPolynomial poly, IsOrderedPolynomial poly')
              => (Coefficient poly -> Coefficient poly') -> (Ordinal (Arity poly) -> Ordinal (Arity poly'))
              -> poly -> poly'
mapPolynomial :: (Coefficient poly -> Coefficient poly')
-> (Ordinal (Arity poly) -> Ordinal (Arity poly')) -> poly -> poly'
mapPolynomial Coefficient poly -> Coefficient poly'
mapCoe Ordinal (Arity poly) -> Ordinal (Arity poly')
injVar =
  (Coefficient poly -> poly' -> poly')
-> Sized (Arity poly) poly' -> poly -> poly'
forall poly m.
(IsPolynomial poly, Ring m) =>
(Coefficient poly -> m -> m) -> Sized (Arity poly) m -> poly -> m
substWith (\Coefficient poly
coe poly'
g -> Coefficient poly -> Coefficient poly'
mapCoe Coefficient poly
coe Coefficient poly' -> poly' -> poly'
forall poly. IsPolynomial poly => Coefficient poly -> poly -> poly
!* poly'
g) (SNat (Arity poly)
-> (Ordinal (Arity poly) -> poly') -> Sized (Arity poly) poly'
forall (f :: * -> *) (n :: Nat) a.
(CFreeMonoid f, Dom f a) =>
SNat n -> (Ordinal n -> a) -> Sized f n a
generate SNat (Arity poly)
forall (n :: Nat). KnownNat n => SNat n
sNat (Ordinal (Arity poly') -> poly'
forall poly. IsPolynomial poly => Ordinal (Arity poly) -> poly
var (Ordinal (Arity poly') -> poly')
-> (Ordinal (Arity poly) -> Ordinal (Arity poly'))
-> Ordinal (Arity poly)
-> poly'
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Ordinal (Arity poly) -> Ordinal (Arity poly')
injVar))
{-# INLINE [3] mapPolynomial #-}
{-# RULES
"mapPolynomial/id" mapPolynomial id id = id
 #-}