{-# LANGUAGE CPP #-}
{-# LANGUAGE ConstraintKinds #-}
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE ExplicitNamespaces #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE LiberalTypeSynonyms #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE PolyKinds #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE RoleAnnotations #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE StandaloneDeriving #-}
{-# LANGUAGE TypeApplications #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE TypeSynonymInstances #-}
{-# LANGUAGE UndecidableInstances #-}
{-# LANGUAGE ViewPatterns #-}
{-# LANGUAGE NoMonomorphismRestriction #-}
{-# OPTIONS_GHC -Wno-redundant-constraints #-}
{-# OPTIONS_GHC -fno-warn-orphans -fno-warn-type-defaults #-}
{-# OPTIONS_GHC -fplugin Data.Type.Natural.Presburger.MinMaxSolver #-}
{-# OPTIONS_GHC -fplugin GHC.TypeLits.KnownNat.Solver #-}

module Algebra.Ring.Polynomial.Internal
  ( module Algebra.Ring.Polynomial.Monomial,
    module Algebra.Ring.Polynomial.Class,
    Polynomial,
    transformMonomial,
    castPolynomial,
    changeOrder,
    changeOrderProxy,
    scastPolynomial,
    OrderedPolynomial (..),
    allVars,
    substVar,
    homogenize,
    unhomogenize,
    normalize,
    varX,
    getTerms,
    shiftR,
    orderedBy,
    mapCoeff,
    reversal,
    padeApprox,
    eval,
    evalUnivariate,
    substUnivariate,
    minpolRecurrent,
    IsOrder (..),
    PadPolyL (..),
    padLeftPoly,
  )
where

import Algebra.Internal
import Algebra.Ring.Polynomial.Class
import Algebra.Ring.Polynomial.Monomial
import Algebra.Scalar
import AlgebraicPrelude
import Control.DeepSeq (NFData)
import Control.Lens
import qualified Data.Coerce as C
import qualified Data.HashSet as HS
import qualified Data.Map.Merge.Strict as MM
import qualified Data.Map.Strict as M
import Data.MonoTraversable (osum)
import qualified Data.Set as Set
#if MIN_VERSION_singletons(3,0,0)
import Data.List.Singletons (Replicate)
#else
import Data.Singletons.Prelude.List (Replicate)
#endif
import qualified Data.Sized as S
import Data.Type.Natural.Lemma.Order
import qualified Numeric.Algebra as NA
import qualified Prelude as P

instance Hashable r => Hashable (OrderedPolynomial r ord n) where
  hashWithSalt :: Int -> OrderedPolynomial r ord n -> Int
hashWithSalt Int
salt OrderedPolynomial r ord n
poly = Int -> [(r, OrderedMonomial ord n)] -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
salt ([(r, OrderedMonomial ord n)] -> Int)
-> [(r, OrderedMonomial ord n)] -> Int
forall a b. (a -> b) -> a -> b
$ OrderedPolynomial r ord n -> [(r, OrderedMonomial ord n)]
forall k k (order :: k) (n :: Nat).
OrderedPolynomial k order n -> [(k, OrderedMonomial order n)]
getTerms OrderedPolynomial r ord n
poly

deriving instance (CoeffRing r, IsOrder n ord, Ord r) => Ord (OrderedPolynomial r ord n)

-- | n-ary polynomial ring over some noetherian ring R.
newtype OrderedPolynomial r order n = Polynomial {OrderedPolynomial r order n -> Map (OrderedMonomial order n) r
_terms :: Map (OrderedMonomial order n) r}
  deriving (OrderedPolynomial r order n -> ()
(OrderedPolynomial r order n -> ())
-> NFData (OrderedPolynomial r order n)
forall a. (a -> ()) -> NFData a
forall r k (order :: k) (n :: Nat).
NFData r =>
OrderedPolynomial r order n -> ()
rnf :: OrderedPolynomial r order n -> ()
$crnf :: forall r k (order :: k) (n :: Nat).
NFData r =>
OrderedPolynomial r order n -> ()
NFData)

type role OrderedPolynomial representational nominal nominal

type Polynomial r = OrderedPolynomial r Grevlex

instance (KnownNat n, IsMonomialOrder n ord, CoeffRing r) => IsPolynomial (OrderedPolynomial r ord n) where
  type Coefficient (OrderedPolynomial r ord n) = r
  type Arity (OrderedPolynomial r ord n) = n

  injectCoeff :: Coefficient (OrderedPolynomial r ord n)
-> OrderedPolynomial r ord n
injectCoeff Coefficient (OrderedPolynomial r ord n)
r
    | r -> Bool
forall r. DecidableZero r => r -> Bool
isZero r
Coefficient (OrderedPolynomial r ord n)
r = Map (OrderedMonomial ord n) r -> OrderedPolynomial r ord n
forall k r (order :: k) (n :: Nat).
Map (OrderedMonomial order n) r -> OrderedPolynomial r order n
Polynomial Map (OrderedMonomial ord n) r
forall k a. Map k a
M.empty
    | Bool
otherwise = Map (OrderedMonomial ord n) r -> OrderedPolynomial r ord n
forall k r (order :: k) (n :: Nat).
Map (OrderedMonomial order n) r -> OrderedPolynomial r order n
Polynomial (Map (OrderedMonomial ord n) r -> OrderedPolynomial r ord n)
-> Map (OrderedMonomial ord n) r -> OrderedPolynomial r ord n
forall a b. (a -> b) -> a -> b
$ OrderedMonomial ord n -> r -> Map (OrderedMonomial ord n) r
forall k a. k -> a -> Map k a
M.singleton OrderedMonomial ord n
forall r. Unital r => r
one r
Coefficient (OrderedPolynomial r ord n)
r
  {-# INLINE injectCoeff #-}

  sArity' :: OrderedPolynomial r ord n
-> SNat (Arity (OrderedPolynomial r ord n))
sArity' = Sized Vector n Int -> SNat n
forall (n :: Nat) (f :: * -> *) a.
(KnownNat n, DomC f a) =>
Sized f n a -> SNat n
sizedLength (Sized Vector n Int -> SNat n)
-> (OrderedPolynomial r ord n -> Sized Vector n Int)
-> OrderedPolynomial r ord n
-> SNat n
forall b c a. (b -> c) -> (a -> b) -> a -> c
. OrderedMonomial ord n -> Sized Vector n Int
forall k (ordering :: k) (n :: Nat).
OrderedMonomial ordering n -> Monomial n
getMonomial (OrderedMonomial ord n -> Sized Vector n Int)
-> (OrderedPolynomial r ord n -> OrderedMonomial ord n)
-> OrderedPolynomial r ord n
-> Sized Vector n Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. OrderedPolynomial r ord n -> OrderedMonomial ord n
forall poly.
IsOrderedPolynomial poly =>
poly -> OrderedMonomial (MOrder poly) (Arity poly)
leadingMonomial
  {-# INLINE sArity' #-}

  mapCoeff' :: (Coefficient (OrderedPolynomial r ord n)
 -> Coefficient (OrderedPolynomial r ord n))
-> OrderedPolynomial r ord n -> OrderedPolynomial r ord n
mapCoeff' = (Coefficient (OrderedPolynomial r ord n)
 -> Coefficient (OrderedPolynomial r ord n))
-> OrderedPolynomial r ord n -> OrderedPolynomial r ord n
forall (n :: Nat) b ord a.
(KnownNat n, CoeffRing b, IsMonomialOrder n ord) =>
(a -> b) -> OrderedPolynomial a ord n -> OrderedPolynomial b ord n
mapCoeff
  {-# INLINE mapCoeff' #-}

  monomials :: OrderedPolynomial r ord n
-> HashSet (Monomial (Arity (OrderedPolynomial r ord n)))
monomials = [Sized Vector n Int] -> HashSet (Sized Vector n Int)
forall a. (Eq a, Hashable a) => [a] -> HashSet a
HS.fromList ([Sized Vector n Int] -> HashSet (Sized Vector n Int))
-> (OrderedPolynomial r ord n -> [Sized Vector n Int])
-> OrderedPolynomial r ord n
-> HashSet (Sized Vector n Int)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (OrderedMonomial ord n -> Sized Vector n Int)
-> [OrderedMonomial ord n] -> [Sized Vector n Int]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
map OrderedMonomial ord n -> Sized Vector n Int
forall k (ordering :: k) (n :: Nat).
OrderedMonomial ordering n -> Monomial n
getMonomial ([OrderedMonomial ord n] -> [Sized Vector n Int])
-> (OrderedPolynomial r ord n -> [OrderedMonomial ord n])
-> OrderedPolynomial r ord n
-> [Sized Vector n Int]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Set (OrderedMonomial ord n) -> [OrderedMonomial ord n]
forall a. Set a -> [a]
Set.toList (Set (OrderedMonomial ord n) -> [OrderedMonomial ord n])
-> (OrderedPolynomial r ord n -> Set (OrderedMonomial ord n))
-> OrderedPolynomial r ord n
-> [OrderedMonomial ord n]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. OrderedPolynomial r ord n -> Set (OrderedMonomial ord n)
forall poly.
IsOrderedPolynomial poly =>
poly -> Set (OrderedMonomial (MOrder poly) (Arity poly))
orderedMonomials
  {-# INLINE monomials #-}

  fromMonomial :: Monomial (Arity (OrderedPolynomial r ord n))
-> OrderedPolynomial r ord n
fromMonomial Monomial (Arity (OrderedPolynomial r ord n))
m = Map (OrderedMonomial ord n) r -> OrderedPolynomial r ord n
forall k r (order :: k) (n :: Nat).
Map (OrderedMonomial order n) r -> OrderedPolynomial r order n
Polynomial (Map (OrderedMonomial ord n) r -> OrderedPolynomial r ord n)
-> Map (OrderedMonomial ord n) r -> OrderedPolynomial r ord n
forall a b. (a -> b) -> a -> b
$ OrderedMonomial ord n -> r -> Map (OrderedMonomial ord n) r
forall k a. k -> a -> Map k a
M.singleton (Sized Vector n Int -> OrderedMonomial ord n
forall k (ordering :: k) (n :: Nat).
Monomial n -> OrderedMonomial ordering n
OrderedMonomial Sized Vector n Int
Monomial (Arity (OrderedPolynomial r ord n))
m) r
forall r. Unital r => r
one
  {-# INLINE fromMonomial #-}

  toPolynomial' :: (Coefficient (OrderedPolynomial r ord n),
 Monomial (Arity (OrderedPolynomial r ord n)))
-> OrderedPolynomial r ord n
toPolynomial' (Coefficient (OrderedPolynomial r ord n)
r, Monomial (Arity (OrderedPolynomial r ord n))
m) = Map (OrderedMonomial ord n) r -> OrderedPolynomial r ord n
forall k r (order :: k) (n :: Nat).
Map (OrderedMonomial order n) r -> OrderedPolynomial r order n
Polynomial (Map (OrderedMonomial ord n) r -> OrderedPolynomial r ord n)
-> Map (OrderedMonomial ord n) r -> OrderedPolynomial r ord n
forall a b. (a -> b) -> a -> b
$ OrderedMonomial ord n -> r -> Map (OrderedMonomial ord n) r
forall k a. k -> a -> Map k a
M.singleton (Sized Vector n Int -> OrderedMonomial ord n
forall k (ordering :: k) (n :: Nat).
Monomial n -> OrderedMonomial ordering n
OrderedMonomial Sized Vector n Int
Monomial (Arity (OrderedPolynomial r ord n))
m) r
Coefficient (OrderedPolynomial r ord n)
r
  {-# INLINE toPolynomial' #-}

  polynomial' :: Map
  (Monomial (Arity (OrderedPolynomial r ord n)))
  (Coefficient (OrderedPolynomial r ord n))
-> OrderedPolynomial r ord n
polynomial' Map
  (Monomial (Arity (OrderedPolynomial r ord n)))
  (Coefficient (OrderedPolynomial r ord n))
dic = OrderedPolynomial r ord n -> OrderedPolynomial r ord n
forall k r (order :: k) (n :: Nat).
DecidableZero r =>
OrderedPolynomial r order n -> OrderedPolynomial r order n
normalize (OrderedPolynomial r ord n -> OrderedPolynomial r ord n)
-> OrderedPolynomial r ord n -> OrderedPolynomial r ord n
forall a b. (a -> b) -> a -> b
$ Map (OrderedMonomial ord n) r -> OrderedPolynomial r ord n
forall k r (order :: k) (n :: Nat).
Map (OrderedMonomial order n) r -> OrderedPolynomial r order n
Polynomial (Map (OrderedMonomial ord n) r -> OrderedPolynomial r ord n)
-> Map (OrderedMonomial ord n) r -> OrderedPolynomial r ord n
forall a b. (a -> b) -> a -> b
$ (Sized Vector n Int -> OrderedMonomial ord n)
-> Map (Sized Vector n Int) r -> Map (OrderedMonomial ord n) r
forall k2 k1 a. Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a
M.mapKeys Sized Vector n Int -> OrderedMonomial ord n
forall k (ordering :: k) (n :: Nat).
Monomial n -> OrderedMonomial ordering n
OrderedMonomial Map (Sized Vector n Int) r
Map
  (Monomial (Arity (OrderedPolynomial r ord n)))
  (Coefficient (OrderedPolynomial r ord n))
dic
  {-# INLINE polynomial' #-}

  terms' :: OrderedPolynomial r ord n
-> Map
     (Monomial (Arity (OrderedPolynomial r ord n)))
     (Coefficient (OrderedPolynomial r ord n))
terms' = (OrderedMonomial ord n -> Sized Vector n Int)
-> Map (OrderedMonomial ord n) r -> Map (Sized Vector n Int) r
forall k2 k1 a. Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a
M.mapKeys OrderedMonomial ord n -> Sized Vector n Int
forall k (ordering :: k) (n :: Nat).
OrderedMonomial ordering n -> Monomial n
getMonomial (Map (OrderedMonomial ord n) r -> Map (Sized Vector n Int) r)
-> (OrderedPolynomial r ord n -> Map (OrderedMonomial ord n) r)
-> OrderedPolynomial r ord n
-> Map (Sized Vector n Int) r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. OrderedPolynomial r ord n -> Map (OrderedMonomial ord n) r
forall poly.
IsOrderedPolynomial poly =>
poly
-> Map
     (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
terms
  {-# INLINE terms' #-}

  liftMap :: (Ordinal (Arity (OrderedPolynomial r ord n)) -> alg)
-> OrderedPolynomial r ord n -> alg
liftMap Ordinal (Arity (OrderedPolynomial r ord n)) -> alg
mor OrderedPolynomial r ord n
poly = [alg] -> alg
forall (f :: * -> *) m. (Foldable f, Monoidal m) => f m -> m
sum ([alg] -> alg) -> [alg] -> alg
forall a b. (a -> b) -> a -> b
$ ((r, OrderedMonomial ord n) -> alg)
-> [(r, OrderedMonomial ord n)] -> [alg]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
map ((Scalar r -> alg -> alg) -> (Scalar r, alg) -> alg
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry Scalar r -> alg -> alg
forall r m. LeftModule r m => r -> m -> m
(.*) ((Scalar r, alg) -> alg)
-> ((r, OrderedMonomial ord n) -> (Scalar r, alg))
-> (r, OrderedMonomial ord n)
-> alg
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (r -> Scalar r
forall r. r -> Scalar r
Scalar (r -> Scalar r)
-> (OrderedMonomial ord n -> alg)
-> (r, OrderedMonomial ord n)
-> (Scalar r, alg)
forall (a :: * -> * -> *) b c b' c'.
Arrow a =>
a b c -> a b' c' -> a (b, b') (c, c')
*** OrderedMonomial ord n -> alg
extractPower)) ([(r, OrderedMonomial ord n)] -> [alg])
-> [(r, OrderedMonomial ord n)] -> [alg]
forall a b. (a -> b) -> a -> b
$ OrderedPolynomial r ord n -> [(r, OrderedMonomial ord n)]
forall k k (order :: k) (n :: Nat).
OrderedPolynomial k order n -> [(k, OrderedMonomial order n)]
getTerms OrderedPolynomial r ord n
poly
    where
      extractPower :: OrderedMonomial ord n -> alg
extractPower = Mult alg -> alg
forall a. Mult a -> a
runMult (Mult alg -> alg)
-> (OrderedMonomial ord n -> Mult alg)
-> OrderedMonomial ord n
-> alg
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Ordinal n -> Int -> Mult alg) -> Sized Vector n Int -> Mult alg
forall (n :: Nat) m.
(KnownNat n, Monoid m) =>
(Ordinal n -> Int -> m) -> Monomial n -> m
ifoldMapMonom (\Ordinal n
o -> alg -> Mult alg
forall a. a -> Mult a
Mult (alg -> Mult alg) -> (Int -> alg) -> Int -> Mult alg
forall b c a. (b -> c) -> (a -> b) -> a -> c
. alg -> Natural -> alg
forall r. Unital r => r -> Natural -> r
pow (Ordinal (Arity (OrderedPolynomial r ord n)) -> alg
mor Ordinal n
Ordinal (Arity (OrderedPolynomial r ord n))
o) (Natural -> alg) -> (Int -> Natural) -> Int -> alg
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Natural
forall a b. (Integral a, Num b) => a -> b
fromIntegral) (Sized Vector n Int -> Mult alg)
-> (OrderedMonomial ord n -> Sized Vector n Int)
-> OrderedMonomial ord n
-> Mult alg
forall b c a. (b -> c) -> (a -> b) -> a -> c
. OrderedMonomial ord n -> Sized Vector n Int
forall k (ordering :: k) (n :: Nat).
OrderedMonomial ordering n -> Monomial n
getMonomial
  {-# INLINE liftMap #-}

instance
  (KnownNat n, CoeffRing r, IsMonomialOrder n ord) =>
  IsOrderedPolynomial (OrderedPolynomial r ord n)
  where
  type MOrder (OrderedPolynomial r ord n) = ord
  coeff :: OrderedMonomial
  (MOrder (OrderedPolynomial r ord n))
  (Arity (OrderedPolynomial r ord n))
-> OrderedPolynomial r ord n
-> Coefficient (OrderedPolynomial r ord n)
coeff OrderedMonomial
  (MOrder (OrderedPolynomial r ord n))
  (Arity (OrderedPolynomial r ord n))
d = r -> OrderedMonomial ord n -> Map (OrderedMonomial ord n) r -> r
forall k a. Ord k => a -> k -> Map k a -> a
M.findWithDefault r
forall m. Monoidal m => m
zero OrderedMonomial ord n
OrderedMonomial
  (MOrder (OrderedPolynomial r ord n))
  (Arity (OrderedPolynomial r ord n))
d (Map (OrderedMonomial ord n) r -> r)
-> (OrderedPolynomial r ord n -> Map (OrderedMonomial ord n) r)
-> OrderedPolynomial r ord n
-> r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. OrderedPolynomial r ord n -> Map (OrderedMonomial ord n) r
forall poly.
IsOrderedPolynomial poly =>
poly
-> Map
     (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
terms
  {-# INLINE coeff #-}

  terms :: OrderedPolynomial r ord n
-> Map
     (OrderedMonomial
        (MOrder (OrderedPolynomial r ord n))
        (Arity (OrderedPolynomial r ord n)))
     (Coefficient (OrderedPolynomial r ord n))
terms = OrderedPolynomial r ord n
-> Map
     (OrderedMonomial
        (MOrder (OrderedPolynomial r ord n))
        (Arity (OrderedPolynomial r ord n)))
     (Coefficient (OrderedPolynomial r ord n))
C.coerce
  {-# INLINE terms #-}

  orderedMonomials :: OrderedPolynomial r ord n
-> Set
     (OrderedMonomial
        (MOrder (OrderedPolynomial r ord n))
        (Arity (OrderedPolynomial r ord n)))
orderedMonomials = Map (OrderedMonomial ord n) r -> Set (OrderedMonomial ord n)
forall k a. Map k a -> Set k
M.keysSet (Map (OrderedMonomial ord n) r -> Set (OrderedMonomial ord n))
-> (OrderedPolynomial r ord n -> Map (OrderedMonomial ord n) r)
-> OrderedPolynomial r ord n
-> Set (OrderedMonomial ord n)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. OrderedPolynomial r ord n -> Map (OrderedMonomial ord n) r
forall poly.
IsOrderedPolynomial poly =>
poly
-> Map
     (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
terms
  {-# INLINE orderedMonomials #-}

  toPolynomial :: (Coefficient (OrderedPolynomial r ord n),
 OrderedMonomial
   (MOrder (OrderedPolynomial r ord n))
   (Arity (OrderedPolynomial r ord n)))
-> OrderedPolynomial r ord n
toPolynomial (Coefficient (OrderedPolynomial r ord n)
c, OrderedMonomial
  (MOrder (OrderedPolynomial r ord n))
  (Arity (OrderedPolynomial r ord n))
deg) =
    if r -> Bool
forall r. DecidableZero r => r -> Bool
isZero r
Coefficient (OrderedPolynomial r ord n)
c
      then Map (OrderedMonomial ord n) r -> OrderedPolynomial r ord n
forall k r (order :: k) (n :: Nat).
Map (OrderedMonomial order n) r -> OrderedPolynomial r order n
Polynomial Map (OrderedMonomial ord n) r
forall k a. Map k a
M.empty
      else Map (OrderedMonomial ord n) r -> OrderedPolynomial r ord n
forall k r (order :: k) (n :: Nat).
Map (OrderedMonomial order n) r -> OrderedPolynomial r order n
Polynomial (Map (OrderedMonomial ord n) r -> OrderedPolynomial r ord n)
-> Map (OrderedMonomial ord n) r -> OrderedPolynomial r ord n
forall a b. (a -> b) -> a -> b
$ OrderedMonomial ord n -> r -> Map (OrderedMonomial ord n) r
forall k a. k -> a -> Map k a
M.singleton OrderedMonomial ord n
OrderedMonomial
  (MOrder (OrderedPolynomial r ord n))
  (Arity (OrderedPolynomial r ord n))
deg r
Coefficient (OrderedPolynomial r ord n)
c
  {-# INLINE toPolynomial #-}

  polynomial :: Map
  (OrderedMonomial
     (MOrder (OrderedPolynomial r ord n))
     (Arity (OrderedPolynomial r ord n)))
  (Coefficient (OrderedPolynomial r ord n))
-> OrderedPolynomial r ord n
polynomial = OrderedPolynomial r ord n -> OrderedPolynomial r ord n
forall k r (order :: k) (n :: Nat).
DecidableZero r =>
OrderedPolynomial r order n -> OrderedPolynomial r order n
normalize (OrderedPolynomial r ord n -> OrderedPolynomial r ord n)
-> (Map (OrderedMonomial ord n) r -> OrderedPolynomial r ord n)
-> Map (OrderedMonomial ord n) r
-> OrderedPolynomial r ord n
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map (OrderedMonomial ord n) r -> OrderedPolynomial r ord n
C.coerce
  {-# INLINE polynomial #-}

  >* :: OrderedMonomial
  (MOrder (OrderedPolynomial r ord n))
  (Arity (OrderedPolynomial r ord n))
-> OrderedPolynomial r ord n -> OrderedPolynomial r ord n
(>*) OrderedMonomial
  (MOrder (OrderedPolynomial r ord n))
  (Arity (OrderedPolynomial r ord n))
m = Map (OrderedMonomial ord n) r -> OrderedPolynomial r ord n
forall k r (order :: k) (n :: Nat).
Map (OrderedMonomial order n) r -> OrderedPolynomial r order n
Polynomial (Map (OrderedMonomial ord n) r -> OrderedPolynomial r ord n)
-> (OrderedPolynomial r ord n -> Map (OrderedMonomial ord n) r)
-> OrderedPolynomial r ord n
-> OrderedPolynomial r ord n
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (OrderedMonomial ord n -> OrderedMonomial ord n)
-> Map (OrderedMonomial ord n) r -> Map (OrderedMonomial ord n) r
forall k1 k2 a. (k1 -> k2) -> Map k1 a -> Map k2 a
M.mapKeysMonotonic (OrderedMonomial ord n
OrderedMonomial
  (MOrder (OrderedPolynomial r ord n))
  (Arity (OrderedPolynomial r ord n))
m OrderedMonomial ord n
-> OrderedMonomial ord n -> OrderedMonomial ord n
forall r. Multiplicative r => r -> r -> r
*) (Map (OrderedMonomial ord n) r -> Map (OrderedMonomial ord n) r)
-> (OrderedPolynomial r ord n -> Map (OrderedMonomial ord n) r)
-> OrderedPolynomial r ord n
-> Map (OrderedMonomial ord n) r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. OrderedPolynomial r ord n -> Map (OrderedMonomial ord n) r
C.coerce
  {-# INLINE (>*) #-}

  leadingTerm :: OrderedPolynomial r ord n
-> (Coefficient (OrderedPolynomial r ord n),
    OrderedMonomial
      (MOrder (OrderedPolynomial r ord n))
      (Arity (OrderedPolynomial r ord n)))
leadingTerm (Polynomial Map (OrderedMonomial ord n) r
d) =
    case Map (OrderedMonomial ord n) r
-> Maybe
     ((OrderedMonomial ord n, r), Map (OrderedMonomial ord n) r)
forall k a. Map k a -> Maybe ((k, a), Map k a)
M.maxViewWithKey Map (OrderedMonomial ord n) r
d of
      Just ((OrderedMonomial ord n
deg, r
c), Map (OrderedMonomial ord n) r
_) -> (r
Coefficient (OrderedPolynomial r ord n)
c, OrderedMonomial ord n
OrderedMonomial
  (MOrder (OrderedPolynomial r ord n))
  (Arity (OrderedPolynomial r ord n))
deg)
      Maybe ((OrderedMonomial ord n, r), Map (OrderedMonomial ord n) r)
Nothing -> (Coefficient (OrderedPolynomial r ord n)
forall m. Monoidal m => m
zero, OrderedMonomial
  (MOrder (OrderedPolynomial r ord n))
  (Arity (OrderedPolynomial r ord n))
forall r. Unital r => r
one)
  {-# INLINE leadingTerm #-}

  leadingMonomial :: OrderedPolynomial r ord n
-> OrderedMonomial
     (MOrder (OrderedPolynomial r ord n))
     (Arity (OrderedPolynomial r ord n))
leadingMonomial = (r, OrderedMonomial ord n) -> OrderedMonomial ord n
forall a b. (a, b) -> b
snd ((r, OrderedMonomial ord n) -> OrderedMonomial ord n)
-> (OrderedPolynomial r ord n -> (r, OrderedMonomial ord n))
-> OrderedPolynomial r ord n
-> OrderedMonomial ord n
forall b c a. (b -> c) -> (a -> b) -> a -> c
. OrderedPolynomial r ord n -> (r, OrderedMonomial ord n)
forall poly.
IsOrderedPolynomial poly =>
poly
-> (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
leadingTerm
  {-# INLINE leadingMonomial #-}

  leadingCoeff :: OrderedPolynomial r ord n
-> Coefficient (OrderedPolynomial r ord n)
leadingCoeff = (r, OrderedMonomial ord n) -> r
forall a b. (a, b) -> a
fst ((r, OrderedMonomial ord n) -> r)
-> (OrderedPolynomial r ord n -> (r, OrderedMonomial ord n))
-> OrderedPolynomial r ord n
-> r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. OrderedPolynomial r ord n -> (r, OrderedMonomial ord n)
forall poly.
IsOrderedPolynomial poly =>
poly
-> (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
leadingTerm
  {-# INLINE leadingCoeff #-}

  splitLeadingTerm :: OrderedPolynomial r ord n
-> ((Coefficient (OrderedPolynomial r ord n),
     OrderedMonomial
       (MOrder (OrderedPolynomial r ord n))
       (Arity (OrderedPolynomial r ord n))),
    OrderedPolynomial r ord n)
splitLeadingTerm (Polynomial Map (OrderedMonomial ord n) r
d) =
    case Map (OrderedMonomial ord n) r
-> Maybe
     ((OrderedMonomial ord n, r), Map (OrderedMonomial ord n) r)
forall k a. Map k a -> Maybe ((k, a), Map k a)
M.maxViewWithKey Map (OrderedMonomial ord n) r
d of
      Just ((OrderedMonomial ord n
deg, r
c), Map (OrderedMonomial ord n) r
p) -> ((r
Coefficient (OrderedPolynomial r ord n)
c, OrderedMonomial ord n
OrderedMonomial
  (MOrder (OrderedPolynomial r ord n))
  (Arity (OrderedPolynomial r ord n))
deg), Map (OrderedMonomial ord n) r -> OrderedPolynomial r ord n
forall k r (order :: k) (n :: Nat).
Map (OrderedMonomial order n) r -> OrderedPolynomial r order n
Polynomial Map (OrderedMonomial ord n) r
p)
      Maybe ((OrderedMonomial ord n, r), Map (OrderedMonomial ord n) r)
Nothing -> ((Coefficient (OrderedPolynomial r ord n)
forall m. Monoidal m => m
zero, OrderedMonomial
  (MOrder (OrderedPolynomial r ord n))
  (Arity (OrderedPolynomial r ord n))
forall r. Unital r => r
one), OrderedPolynomial r ord n
forall m. Monoidal m => m
zero)
  {-# INLINE splitLeadingTerm #-}

  mapMonomialMonotonic :: (OrderedMonomial
   (MOrder (OrderedPolynomial r ord n))
   (Arity (OrderedPolynomial r ord n))
 -> OrderedMonomial
      (MOrder (OrderedPolynomial r ord n))
      (Arity (OrderedPolynomial r ord n)))
-> OrderedPolynomial r ord n -> OrderedPolynomial r ord n
mapMonomialMonotonic OrderedMonomial
  (MOrder (OrderedPolynomial r ord n))
  (Arity (OrderedPolynomial r ord n))
-> OrderedMonomial
     (MOrder (OrderedPolynomial r ord n))
     (Arity (OrderedPolynomial r ord n))
f = Map (OrderedMonomial ord n) r -> OrderedPolynomial r ord n
forall k r (order :: k) (n :: Nat).
Map (OrderedMonomial order n) r -> OrderedPolynomial r order n
Polynomial (Map (OrderedMonomial ord n) r -> OrderedPolynomial r ord n)
-> (OrderedPolynomial r ord n -> Map (OrderedMonomial ord n) r)
-> OrderedPolynomial r ord n
-> OrderedPolynomial r ord n
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (OrderedMonomial ord n -> OrderedMonomial ord n)
-> Map (OrderedMonomial ord n) r -> Map (OrderedMonomial ord n) r
forall k1 k2 a. (k1 -> k2) -> Map k1 a -> Map k2 a
M.mapKeysMonotonic OrderedMonomial ord n -> OrderedMonomial ord n
OrderedMonomial
  (MOrder (OrderedPolynomial r ord n))
  (Arity (OrderedPolynomial r ord n))
-> OrderedMonomial
     (MOrder (OrderedPolynomial r ord n))
     (Arity (OrderedPolynomial r ord n))
f (Map (OrderedMonomial ord n) r -> Map (OrderedMonomial ord n) r)
-> (OrderedPolynomial r ord n -> Map (OrderedMonomial ord n) r)
-> OrderedPolynomial r ord n
-> Map (OrderedMonomial ord n) r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. OrderedPolynomial r ord n -> Map (OrderedMonomial ord n) r
C.coerce
  {-# INLINE mapMonomialMonotonic #-}

castPolynomial ::
  forall r n m o o'.
  ( CoeffRing r
  , KnownNat n
  , KnownNat m
  , IsMonomialOrder n o
  , IsMonomialOrder m o'
  ) =>
  OrderedPolynomial r o n ->
  OrderedPolynomial r o' m
castPolynomial :: OrderedPolynomial r o n -> OrderedPolynomial r o' m
castPolynomial =
  (Map (OrderedMonomial o n) r -> Map (OrderedMonomial o' m) r)
-> OrderedPolynomial r o n -> OrderedPolynomial r o' m
C.coerce @(Map (OrderedMonomial o n) r -> Map (OrderedMonomial o' m) r)
    ((OrderedMonomial o n -> OrderedMonomial o' m)
-> Map (OrderedMonomial o n) r -> Map (OrderedMonomial o' m) r
forall k2 k1 a. Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a
M.mapKeys OrderedMonomial o n -> OrderedMonomial o' m
forall k1 k2 (m :: Nat) (o :: k1) (n :: Nat) (o' :: k2).
KnownNat m =>
OrderedMonomial o n -> OrderedMonomial o' m
castMonomial)
{-# INLINE castPolynomial #-}

scastPolynomial ::
  ( IsMonomialOrder n o
  , IsMonomialOrder m o'
  , KnownNat m
  , CoeffRing r
  , KnownNat n
  ) =>
  SNat m ->
  OrderedPolynomial r o n ->
  OrderedPolynomial r o' m
scastPolynomial :: SNat m -> OrderedPolynomial r o n -> OrderedPolynomial r o' m
scastPolynomial SNat m
_ = OrderedPolynomial r o n -> OrderedPolynomial r o' m
forall r (n :: Nat) (m :: Nat) o o'.
(CoeffRing r, KnownNat n, KnownNat m, IsMonomialOrder n o,
 IsMonomialOrder m o') =>
OrderedPolynomial r o n -> OrderedPolynomial r o' m
castPolynomial
{-# INLINE scastPolynomial #-}

mapCoeff ::
  (KnownNat n, CoeffRing b, IsMonomialOrder n ord) =>
  (a -> b) ->
  OrderedPolynomial a ord n ->
  OrderedPolynomial b ord n
mapCoeff :: (a -> b) -> OrderedPolynomial a ord n -> OrderedPolynomial b ord n
mapCoeff a -> b
f (Polynomial Map (OrderedMonomial ord n) a
dic) = Map
  (OrderedMonomial
     (MOrder (OrderedPolynomial b ord n))
     (Arity (OrderedPolynomial b ord n)))
  (Coefficient (OrderedPolynomial b ord n))
-> OrderedPolynomial b ord n
forall poly.
IsOrderedPolynomial poly =>
Map (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
-> poly
polynomial (Map
   (OrderedMonomial
      (MOrder (OrderedPolynomial b ord n))
      (Arity (OrderedPolynomial b ord n)))
   (Coefficient (OrderedPolynomial b ord n))
 -> OrderedPolynomial b ord n)
-> Map
     (OrderedMonomial
        (MOrder (OrderedPolynomial b ord n))
        (Arity (OrderedPolynomial b ord n)))
     (Coefficient (OrderedPolynomial b ord n))
-> OrderedPolynomial b ord n
forall a b. (a -> b) -> a -> b
$ (a -> b)
-> Map (OrderedMonomial ord n) a -> Map (OrderedMonomial ord n) b
forall a b k. (a -> b) -> Map k a -> Map k b
M.map a -> b
f Map (OrderedMonomial ord n) a
dic
{-# INLINE mapCoeff #-}

normalize ::
  (DecidableZero r) =>
  OrderedPolynomial r order n ->
  OrderedPolynomial r order n
normalize :: OrderedPolynomial r order n -> OrderedPolynomial r order n
normalize (Polynomial Map (OrderedMonomial order n) r
dic) =
  Map (OrderedMonomial order n) r -> OrderedPolynomial r order n
forall k r (order :: k) (n :: Nat).
Map (OrderedMonomial order n) r -> OrderedPolynomial r order n
Polynomial (Map (OrderedMonomial order n) r -> OrderedPolynomial r order n)
-> Map (OrderedMonomial order n) r -> OrderedPolynomial r order n
forall a b. (a -> b) -> a -> b
$ (r -> Bool)
-> Map (OrderedMonomial order n) r
-> Map (OrderedMonomial order n) r
forall a k. (a -> Bool) -> Map k a -> Map k a
M.filter (Bool -> Bool
not (Bool -> Bool) -> (r -> Bool) -> r -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. r -> Bool
forall r. DecidableZero r => r -> Bool
isZero) Map (OrderedMonomial order n) r
dic
{-# INLINE normalize #-}

instance (Eq r) => Eq (OrderedPolynomial r order n) where
  Polynomial Map (OrderedMonomial order n) r
f == :: OrderedPolynomial r order n -> OrderedPolynomial r order n -> Bool
== Polynomial Map (OrderedMonomial order n) r
g = Map (OrderedMonomial order n) r
f Map (OrderedMonomial order n) r
-> Map (OrderedMonomial order n) r -> Bool
forall a. Eq a => a -> a -> Bool
== Map (OrderedMonomial order n) r
g
  {-# INLINE (==) #-}

-- -- | By Hilbert's finite basis theorem, a polynomial ring over a noetherian ring is also a noetherian ring.
instance (IsMonomialOrder n order, CoeffRing r, KnownNat n) => Ring (OrderedPolynomial r order n) where
  fromInteger :: Integer -> OrderedPolynomial r order n
fromInteger Integer
0 = Map (OrderedMonomial order n) r -> OrderedPolynomial r order n
forall k r (order :: k) (n :: Nat).
Map (OrderedMonomial order n) r -> OrderedPolynomial r order n
Polynomial Map (OrderedMonomial order n) r
forall k a. Map k a
M.empty
  fromInteger Integer
n = Map (OrderedMonomial order n) r -> OrderedPolynomial r order n
forall k r (order :: k) (n :: Nat).
Map (OrderedMonomial order n) r -> OrderedPolynomial r order n
Polynomial (Map (OrderedMonomial order n) r -> OrderedPolynomial r order n)
-> Map (OrderedMonomial order n) r -> OrderedPolynomial r order n
forall a b. (a -> b) -> a -> b
$ OrderedMonomial order n -> r -> Map (OrderedMonomial order n) r
forall k a. k -> a -> Map k a
M.singleton OrderedMonomial order n
forall r. Unital r => r
one (Integer -> r
forall r. Ring r => Integer -> r
NA.fromInteger Integer
n)
  {-# INLINE fromInteger #-}

decZero :: DecidableZero r => r -> Maybe r
decZero :: r -> Maybe r
decZero r
n
  | r -> Bool
forall r. DecidableZero r => r -> Bool
isZero r
n = Maybe r
forall a. Maybe a
Nothing
  | Bool
otherwise = r -> Maybe r
forall a. a -> Maybe a
Just r
n
{-# INLINE decZero #-}

instance (IsMonomialOrder n order, CoeffRing r, KnownNat n) => Rig (OrderedPolynomial r order n)

instance (IsMonomialOrder n order, CoeffRing r, KnownNat n) => Group (OrderedPolynomial r order n) where
  negate :: OrderedPolynomial r order n -> OrderedPolynomial r order n
negate (Polynomial Map (OrderedMonomial order n) r
dic) = Map (OrderedMonomial order n) r -> OrderedPolynomial r order n
forall k r (order :: k) (n :: Nat).
Map (OrderedMonomial order n) r -> OrderedPolynomial r order n
Polynomial (Map (OrderedMonomial order n) r -> OrderedPolynomial r order n)
-> Map (OrderedMonomial order n) r -> OrderedPolynomial r order n
forall a b. (a -> b) -> a -> b
$ (r -> r)
-> Map (OrderedMonomial order n) r
-> Map (OrderedMonomial order n) r
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap r -> r
forall r. Group r => r -> r
negate Map (OrderedMonomial order n) r
dic
  {-# INLINE negate #-}

  Polynomial Map (OrderedMonomial order n) r
f - :: OrderedPolynomial r order n
-> OrderedPolynomial r order n -> OrderedPolynomial r order n
- Polynomial Map (OrderedMonomial order n) r
g = Map (OrderedMonomial order n) r -> OrderedPolynomial r order n
forall k r (order :: k) (n :: Nat).
Map (OrderedMonomial order n) r -> OrderedPolynomial r order n
Polynomial (Map (OrderedMonomial order n) r -> OrderedPolynomial r order n)
-> Map (OrderedMonomial order n) r -> OrderedPolynomial r order n
forall a b. (a -> b) -> a -> b
$ (OrderedMonomial order n -> r -> r -> Maybe r)
-> (Map (OrderedMonomial order n) r
    -> Map (OrderedMonomial order n) r)
-> (Map (OrderedMonomial order n) r
    -> Map (OrderedMonomial order n) r)
-> Map (OrderedMonomial order n) r
-> Map (OrderedMonomial order n) r
-> Map (OrderedMonomial order n) r
forall k a b c.
Ord k =>
(k -> a -> b -> Maybe c)
-> (Map k a -> Map k c)
-> (Map k b -> Map k c)
-> Map k a
-> Map k b
-> Map k c
M.mergeWithKey (\OrderedMonomial order n
_ r
i r
j -> r -> Maybe r
forall r. DecidableZero r => r -> Maybe r
decZero (r
i r -> r -> r
forall r. Group r => r -> r -> r
- r
j)) Map (OrderedMonomial order n) r -> Map (OrderedMonomial order n) r
forall a. a -> a
id ((r -> r)
-> Map (OrderedMonomial order n) r
-> Map (OrderedMonomial order n) r
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap r -> r
forall r. Group r => r -> r
negate) Map (OrderedMonomial order n) r
f Map (OrderedMonomial order n) r
g
  {-# INLINE (-) #-}

instance (IsMonomialOrder n order, CoeffRing r, KnownNat n) => LeftModule Integer (OrderedPolynomial r order n) where
  Integer
n .* :: Integer
-> OrderedPolynomial r order n -> OrderedPolynomial r order n
.* Polynomial Map (OrderedMonomial order n) r
dic = Map
  (OrderedMonomial
     (MOrder (OrderedPolynomial r order n))
     (Arity (OrderedPolynomial r order n)))
  (Coefficient (OrderedPolynomial r order n))
-> OrderedPolynomial r order n
forall poly.
IsOrderedPolynomial poly =>
Map (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
-> poly
polynomial (Map
   (OrderedMonomial
      (MOrder (OrderedPolynomial r order n))
      (Arity (OrderedPolynomial r order n)))
   (Coefficient (OrderedPolynomial r order n))
 -> OrderedPolynomial r order n)
-> Map
     (OrderedMonomial
        (MOrder (OrderedPolynomial r order n))
        (Arity (OrderedPolynomial r order n)))
     (Coefficient (OrderedPolynomial r order n))
-> OrderedPolynomial r order n
forall a b. (a -> b) -> a -> b
$ (r -> r)
-> Map (OrderedMonomial order n) r
-> Map (OrderedMonomial order n) r
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Integer
n Integer -> r -> r
forall r m. LeftModule r m => r -> m -> m
.*) Map (OrderedMonomial order n) r
dic
  {-# INLINE (.*) #-}

instance (IsMonomialOrder n order, CoeffRing r, KnownNat n) => RightModule Integer (OrderedPolynomial r order n) where
  *. :: OrderedPolynomial r order n
-> Integer -> OrderedPolynomial r order n
(*.) = (Integer
 -> OrderedPolynomial r order n -> OrderedPolynomial r order n)
-> OrderedPolynomial r order n
-> Integer
-> OrderedPolynomial r order n
forall a b c. (a -> b -> c) -> b -> a -> c
flip Integer
-> OrderedPolynomial r order n -> OrderedPolynomial r order n
forall r m. LeftModule r m => r -> m -> m
(.*)
  {-# INLINE (*.) #-}

instance (IsMonomialOrder n order, CoeffRing r, KnownNat n) => Additive (OrderedPolynomial r order n) where
  (Polynomial Map (OrderedMonomial order n) r
f) + :: OrderedPolynomial r order n
-> OrderedPolynomial r order n -> OrderedPolynomial r order n
+ (Polynomial Map (OrderedMonomial order n) r
g) = Map
  (OrderedMonomial
     (MOrder (OrderedPolynomial r order n))
     (Arity (OrderedPolynomial r order n)))
  (Coefficient (OrderedPolynomial r order n))
-> OrderedPolynomial r order n
forall poly.
IsOrderedPolynomial poly =>
Map (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
-> poly
polynomial (Map
   (OrderedMonomial
      (MOrder (OrderedPolynomial r order n))
      (Arity (OrderedPolynomial r order n)))
   (Coefficient (OrderedPolynomial r order n))
 -> OrderedPolynomial r order n)
-> Map
     (OrderedMonomial
        (MOrder (OrderedPolynomial r order n))
        (Arity (OrderedPolynomial r order n)))
     (Coefficient (OrderedPolynomial r order n))
-> OrderedPolynomial r order n
forall a b. (a -> b) -> a -> b
$ (r -> r -> r)
-> Map (OrderedMonomial order n) r
-> Map (OrderedMonomial order n) r
-> Map (OrderedMonomial order n) r
forall k a. Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
M.unionWith r -> r -> r
forall r. Additive r => r -> r -> r
(+) Map (OrderedMonomial order n) r
f Map (OrderedMonomial order n) r
g
  {-# INLINE (+) #-}

instance (IsMonomialOrder n order, CoeffRing r, KnownNat n) => Monoidal (OrderedPolynomial r order n) where
  zero :: OrderedPolynomial r order n
zero = Map (OrderedMonomial order n) r -> OrderedPolynomial r order n
forall k r (order :: k) (n :: Nat).
Map (OrderedMonomial order n) r -> OrderedPolynomial r order n
Polynomial Map (OrderedMonomial order n) r
forall k a. Map k a
M.empty
  {-# INLINE zero #-}

instance (IsMonomialOrder n order, CoeffRing r, KnownNat n) => LeftModule Natural (OrderedPolynomial r order n) where
  Natural
n .* :: Natural
-> OrderedPolynomial r order n -> OrderedPolynomial r order n
.* Polynomial Map (OrderedMonomial order n) r
dic = Map
  (OrderedMonomial
     (MOrder (OrderedPolynomial r order n))
     (Arity (OrderedPolynomial r order n)))
  (Coefficient (OrderedPolynomial r order n))
-> OrderedPolynomial r order n
forall poly.
IsOrderedPolynomial poly =>
Map (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
-> poly
polynomial (Map
   (OrderedMonomial
      (MOrder (OrderedPolynomial r order n))
      (Arity (OrderedPolynomial r order n)))
   (Coefficient (OrderedPolynomial r order n))
 -> OrderedPolynomial r order n)
-> Map
     (OrderedMonomial
        (MOrder (OrderedPolynomial r order n))
        (Arity (OrderedPolynomial r order n)))
     (Coefficient (OrderedPolynomial r order n))
-> OrderedPolynomial r order n
forall a b. (a -> b) -> a -> b
$ (r -> r)
-> Map (OrderedMonomial order n) r
-> Map (OrderedMonomial order n) r
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Natural
n Natural -> r -> r
forall r m. LeftModule r m => r -> m -> m
.*) Map (OrderedMonomial order n) r
dic
  {-# INLINE (.*) #-}

instance (IsMonomialOrder n order, CoeffRing r, KnownNat n) => RightModule Natural (OrderedPolynomial r order n) where
  *. :: OrderedPolynomial r order n
-> Natural -> OrderedPolynomial r order n
(*.) = (Natural
 -> OrderedPolynomial r order n -> OrderedPolynomial r order n)
-> OrderedPolynomial r order n
-> Natural
-> OrderedPolynomial r order n
forall a b c. (a -> b -> c) -> b -> a -> c
flip Natural
-> OrderedPolynomial r order n -> OrderedPolynomial r order n
forall r m. LeftModule r m => r -> m -> m
(.*)
  {-# INLINE (*.) #-}

instance (IsMonomialOrder n order, CoeffRing r, KnownNat n) => Unital (OrderedPolynomial r order n) where
  one :: OrderedPolynomial r order n
one = Map (OrderedMonomial order n) r -> OrderedPolynomial r order n
forall k r (order :: k) (n :: Nat).
Map (OrderedMonomial order n) r -> OrderedPolynomial r order n
Polynomial (Map (OrderedMonomial order n) r -> OrderedPolynomial r order n)
-> Map (OrderedMonomial order n) r -> OrderedPolynomial r order n
forall a b. (a -> b) -> a -> b
$ OrderedMonomial order n -> r -> Map (OrderedMonomial order n) r
forall k a. k -> a -> Map k a
M.singleton OrderedMonomial order n
forall r. Unital r => r
one r
forall r. Unital r => r
one
  {-# INLINE one #-}

instance (IsMonomialOrder n order, CoeffRing r, KnownNat n) => Multiplicative (OrderedPolynomial r order n) where
  Polynomial (Map (OrderedMonomial order n) r -> [(OrderedMonomial order n, r)]
forall k a. Map k a -> [(k, a)]
M.toList -> [(OrderedMonomial order n, r)]
d1) * :: OrderedPolynomial r order n
-> OrderedPolynomial r order n -> OrderedPolynomial r order n
* Polynomial Map (OrderedMonomial order n) r
d2 =
    let ds :: [Map (OrderedMonomial order n) r]
ds = [(r -> r)
-> Map (OrderedMonomial order n) r
-> Map (OrderedMonomial order n) r
forall a b k. (a -> b) -> Map k a -> Map k b
M.map (r
c r -> r -> r
forall r. Multiplicative r => r -> r -> r
*) (Map (OrderedMonomial order n) r
 -> Map (OrderedMonomial order n) r)
-> Map (OrderedMonomial order n) r
-> Map (OrderedMonomial order n) r
forall a b. (a -> b) -> a -> b
$ (OrderedMonomial order n -> OrderedMonomial order n)
-> Map (OrderedMonomial order n) r
-> Map (OrderedMonomial order n) r
forall k1 k2 a. (k1 -> k2) -> Map k1 a -> Map k2 a
M.mapKeysMonotonic (OrderedMonomial order n
k OrderedMonomial order n
-> OrderedMonomial order n -> OrderedMonomial order n
forall r. Multiplicative r => r -> r -> r
*) Map (OrderedMonomial order n) r
d2 | (OrderedMonomial order n
k, r
c) <- [(OrderedMonomial order n, r)]
d1]
        fuse :: WhenMatched f k z z z
fuse = (k -> z -> z -> Maybe z) -> WhenMatched f k z z z
forall (f :: * -> *) k x y z.
Applicative f =>
(k -> x -> y -> Maybe z) -> WhenMatched f k x y z
MM.zipWithMaybeMatched ((k -> z -> z -> Maybe z) -> WhenMatched f k z z z)
-> (k -> z -> z -> Maybe z) -> WhenMatched f k z z z
forall a b. (a -> b) -> a -> b
$ \k
_ z
x z
y -> z -> Maybe z
forall r. DecidableZero r => r -> Maybe r
guardZero (z -> Maybe z) -> z -> Maybe z
forall a b. (a -> b) -> a -> b
$ z
x z -> z -> z
forall r. Additive r => r -> r -> r
+ z
y
     in Map (OrderedMonomial order n) r -> OrderedPolynomial r order n
forall k r (order :: k) (n :: Nat).
Map (OrderedMonomial order n) r -> OrderedPolynomial r order n
Polynomial (Map (OrderedMonomial order n) r -> OrderedPolynomial r order n)
-> Map (OrderedMonomial order n) r -> OrderedPolynomial r order n
forall a b. (a -> b) -> a -> b
$ (Map (OrderedMonomial order n) r
 -> Map (OrderedMonomial order n) r
 -> Map (OrderedMonomial order n) r)
-> Map (OrderedMonomial order n) r
-> [Map (OrderedMonomial order n) r]
-> Map (OrderedMonomial order n) r
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (SimpleWhenMissing (OrderedMonomial order n) r r
-> SimpleWhenMissing (OrderedMonomial order n) r r
-> SimpleWhenMatched (OrderedMonomial order n) r r r
-> Map (OrderedMonomial order n) r
-> Map (OrderedMonomial order n) r
-> Map (OrderedMonomial order n) r
forall k a c b.
Ord k =>
SimpleWhenMissing k a c
-> SimpleWhenMissing k b c
-> SimpleWhenMatched k a b c
-> Map k a
-> Map k b
-> Map k c
MM.merge SimpleWhenMissing (OrderedMonomial order n) r r
forall (f :: * -> *) k x. Applicative f => WhenMissing f k x x
MM.preserveMissing SimpleWhenMissing (OrderedMonomial order n) r r
forall (f :: * -> *) k x. Applicative f => WhenMissing f k x x
MM.preserveMissing SimpleWhenMatched (OrderedMonomial order n) r r r
forall (f :: * -> *) z k.
(Applicative f, DecidableZero z) =>
WhenMatched f k z z z
fuse) Map (OrderedMonomial order n) r
forall k a. Map k a
M.empty [Map (OrderedMonomial order n) r]
ds
  {-# INLINE (*) #-}

guardZero :: DecidableZero a => a -> Maybe a
guardZero :: a -> Maybe a
guardZero a
x = if a -> Bool
forall r. DecidableZero r => r -> Bool
isZero a
x then Maybe a
forall a. Maybe a
Nothing else a -> Maybe a
forall a. a -> Maybe a
Just a
x
{-# INLINE guardZero #-}

instance (IsMonomialOrder n order, CoeffRing r, KnownNat n) => Semiring (OrderedPolynomial r order n)

instance (IsMonomialOrder n order, CoeffRing r, KnownNat n) => Commutative (OrderedPolynomial r order n)

instance (IsMonomialOrder n order, CoeffRing r, KnownNat n) => Abelian (OrderedPolynomial r order n)

instance (IsMonomialOrder n order, CoeffRing r, KnownNat n) => LeftModule (Scalar r) (OrderedPolynomial r order n) where
  Scalar r
r .* :: Scalar r
-> OrderedPolynomial r order n -> OrderedPolynomial r order n
.* Polynomial Map (OrderedMonomial order n) r
dic = Map
  (OrderedMonomial
     (MOrder (OrderedPolynomial r order n))
     (Arity (OrderedPolynomial r order n)))
  (Coefficient (OrderedPolynomial r order n))
-> OrderedPolynomial r order n
forall poly.
IsOrderedPolynomial poly =>
Map (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
-> poly
polynomial (Map
   (OrderedMonomial
      (MOrder (OrderedPolynomial r order n))
      (Arity (OrderedPolynomial r order n)))
   (Coefficient (OrderedPolynomial r order n))
 -> OrderedPolynomial r order n)
-> Map
     (OrderedMonomial
        (MOrder (OrderedPolynomial r order n))
        (Arity (OrderedPolynomial r order n)))
     (Coefficient (OrderedPolynomial r order n))
-> OrderedPolynomial r order n
forall a b. (a -> b) -> a -> b
$ (r -> r)
-> Map (OrderedMonomial order n) r
-> Map (OrderedMonomial order n) r
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (r
r r -> r -> r
forall r. Multiplicative r => r -> r -> r
*) Map (OrderedMonomial order n) r
dic
  {-# INLINE (.*) #-}

instance (IsMonomialOrder n order, CoeffRing r, KnownNat n) => RightModule (Scalar r) (OrderedPolynomial r order n) where
  Polynomial Map (OrderedMonomial order n) r
dic *. :: OrderedPolynomial r order n
-> Scalar r -> OrderedPolynomial r order n
*. Scalar r
r = Map
  (OrderedMonomial
     (MOrder (OrderedPolynomial r order n))
     (Arity (OrderedPolynomial r order n)))
  (Coefficient (OrderedPolynomial r order n))
-> OrderedPolynomial r order n
forall poly.
IsOrderedPolynomial poly =>
Map (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
-> poly
polynomial (Map
   (OrderedMonomial
      (MOrder (OrderedPolynomial r order n))
      (Arity (OrderedPolynomial r order n)))
   (Coefficient (OrderedPolynomial r order n))
 -> OrderedPolynomial r order n)
-> Map
     (OrderedMonomial
        (MOrder (OrderedPolynomial r order n))
        (Arity (OrderedPolynomial r order n)))
     (Coefficient (OrderedPolynomial r order n))
-> OrderedPolynomial r order n
forall a b. (a -> b) -> a -> b
$ (r -> r)
-> Map (OrderedMonomial order n) r
-> Map (OrderedMonomial order n) r
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (r
r r -> r -> r
forall r. Multiplicative r => r -> r -> r
*) Map (OrderedMonomial order n) r
dic
  {-# INLINE (*.) #-}

instance
  (IsMonomialOrder n ord, Characteristic r, KnownNat n, CoeffRing r) =>
  Characteristic (OrderedPolynomial r ord n)
  where
  char :: proxy (OrderedPolynomial r ord n) -> Natural
char proxy (OrderedPolynomial r ord n)
_ = Proxy r -> Natural
forall r (proxy :: * -> *). Characteristic r => proxy r -> Natural
char (Proxy r
forall k (t :: k). Proxy t
Proxy :: Proxy r)
  {-# INLINE char #-}

instance
  (KnownNat n, CoeffRing r, IsMonomialOrder n order, PrettyCoeff r) =>
  Show (OrderedPolynomial r order n)
  where
  showsPrec :: Int -> OrderedPolynomial r order n -> ShowS
showsPrec = Sized (Arity (OrderedPolynomial r order n)) String
-> Int -> OrderedPolynomial r order n -> ShowS
forall poly.
(IsOrderedPolynomial poly, PrettyCoeff (Coefficient poly)) =>
Sized (Arity poly) String -> Int -> poly -> ShowS
showsPolynomialWith (Sized (Arity (OrderedPolynomial r order n)) String
 -> Int -> OrderedPolynomial r order n -> ShowS)
-> Sized (Arity (OrderedPolynomial r order n)) String
-> Int
-> OrderedPolynomial r order n
-> ShowS
forall a b. (a -> b) -> a -> b
$ SNat n -> (Ordinal n -> String) -> Sized Vector n String
forall (f :: * -> *) (n :: Nat) a.
(CFreeMonoid f, Dom f a) =>
SNat n -> (Ordinal n -> a) -> Sized f n a
generate SNat n
forall (n :: Nat). KnownNat n => SNat n
sNat (\Ordinal n
i -> String
"X_" String -> ShowS
forall w. Monoid w => w -> w -> w
++ Int -> String
forall a. Show a => a -> String
show (Ordinal n -> Int
forall a. Enum a => a -> Int
fromEnum Ordinal n
i))

{- | We provide Num instance to use trivial injection R into R[X].
   Do not use signum or abs.
-}
instance
  (IsMonomialOrder n order, CoeffRing r, KnownNat n) =>
  P.Num (OrderedPolynomial r order n)
  where
  + :: OrderedPolynomial r order n
-> OrderedPolynomial r order n -> OrderedPolynomial r order n
(+) = OrderedPolynomial r order n
-> OrderedPolynomial r order n -> OrderedPolynomial r order n
forall r. Additive r => r -> r -> r
(NA.+)
  {-# INLINE (+) #-}

  * :: OrderedPolynomial r order n
-> OrderedPolynomial r order n -> OrderedPolynomial r order n
(*) = OrderedPolynomial r order n
-> OrderedPolynomial r order n -> OrderedPolynomial r order n
forall r. Multiplicative r => r -> r -> r
(NA.*)
  {-# INLINE (*) #-}

  fromInteger :: Integer -> OrderedPolynomial r order n
fromInteger = Integer -> OrderedPolynomial r order n
forall r. Ring r => Integer -> r
NA.fromInteger
  {-# INLINE fromInteger #-}

  signum :: OrderedPolynomial r order n -> OrderedPolynomial r order n
signum OrderedPolynomial r order n
f = if OrderedPolynomial r order n -> Bool
forall r. DecidableZero r => r -> Bool
isZero OrderedPolynomial r order n
f then OrderedPolynomial r order n
forall m. Monoidal m => m
zero else Coefficient (OrderedPolynomial r order n)
-> OrderedPolynomial r order n
forall poly. IsPolynomial poly => Coefficient poly -> poly
injectCoeff Coefficient (OrderedPolynomial r order n)
forall r. Unital r => r
one
  {-# INLINE signum #-}

  abs :: OrderedPolynomial r order n -> OrderedPolynomial r order n
abs = OrderedPolynomial r order n -> OrderedPolynomial r order n
forall a. a -> a
id
  {-# INLINE abs #-}

  negate :: OrderedPolynomial r order n -> OrderedPolynomial r order n
negate = ((Integer -> Integer
forall a. Num a => a -> a
P.negate Integer
1 :: Integer) Integer
-> OrderedPolynomial r order n -> OrderedPolynomial r order n
forall r m. LeftModule r m => r -> m -> m
.*)
  {-# INLINE negate #-}

instance (CoeffRing r, KnownNat n, IsMonomialOrder n ord) => DecidableZero (OrderedPolynomial r ord n) where
  isZero :: OrderedPolynomial r ord n -> Bool
isZero (Polynomial Map (OrderedMonomial ord n) r
d) = Map (OrderedMonomial ord n) r -> Bool
forall k a. Map k a -> Bool
M.null Map (OrderedMonomial ord n) r
d
  {-# INLINE isZero #-}

instance
  (Eq r, KnownNat n, Euclidean r, IsMonomialOrder n ord) =>
  DecidableAssociates (OrderedPolynomial r ord n)
  where
  isAssociate :: OrderedPolynomial r ord n -> OrderedPolynomial r ord n -> Bool
isAssociate = OrderedPolynomial r ord n -> OrderedPolynomial r ord n -> Bool
forall r poly.
(UnitNormalForm r, Coefficient poly ~ r,
 IsOrderedPolynomial poly) =>
poly -> poly -> Bool
isAssociateDefault
  {-# INLINE isAssociate #-}

instance
  ( Eq r
  , Euclidean r
  , KnownNat n
  , IsMonomialOrder n ord
  ) =>
  UnitNormalForm (OrderedPolynomial r ord n)
  where
  splitUnit :: OrderedPolynomial r ord n
-> (OrderedPolynomial r ord n, OrderedPolynomial r ord n)
splitUnit = OrderedPolynomial r ord n
-> (OrderedPolynomial r ord n, OrderedPolynomial r ord n)
forall r poly.
(UnitNormalForm r, Coefficient poly ~ r,
 IsOrderedPolynomial poly) =>
poly -> (poly, poly)
splitUnitDefault
  {-# INLINE splitUnit #-}

instance
  {-# OVERLAPPING #-}
  ( Eq r
  , DecidableUnits r
  , DecidableZero r
  , Field r
  , IsMonomialOrder 1 ord
  , ZeroProductSemiring r
  ) =>
  GCDDomain (OrderedPolynomial r ord 1)

instance
  {-# OVERLAPPING #-}
  ( Eq r
  , DecidableUnits r
  , DecidableZero r
  , Field r
  , IsMonomialOrder 1 ord
  , ZeroProductSemiring r
  ) =>
  UFD (OrderedPolynomial r ord 1)

instance
  ( Eq r
  , DecidableUnits r
  , DecidableZero r
  , Field r
  , IsMonomialOrder 1 ord
  , ZeroProductSemiring r
  ) =>
  PID (OrderedPolynomial r ord 1)

instance (Eq r, DecidableUnits r, DecidableZero r, Field r, IsMonomialOrder 1 ord, ZeroProductSemiring r) => Euclidean (OrderedPolynomial r ord 1) where
  OrderedPolynomial r ord 1
f0 divide :: OrderedPolynomial r ord 1
-> OrderedPolynomial r ord 1
-> (OrderedPolynomial r ord 1, OrderedPolynomial r ord 1)
`divide` OrderedPolynomial r ord 1
g = OrderedPolynomial r ord 1
-> OrderedPolynomial r ord 1
-> (OrderedPolynomial r ord 1, OrderedPolynomial r ord 1)
step OrderedPolynomial r ord 1
f0 OrderedPolynomial r ord 1
forall m. Monoidal m => m
zero
    where
      lm :: OrderedMonomial
  (MOrder (OrderedPolynomial r ord 1))
  (Arity (OrderedPolynomial r ord 1))
lm = OrderedPolynomial r ord 1
-> OrderedMonomial
     (MOrder (OrderedPolynomial r ord 1))
     (Arity (OrderedPolynomial r ord 1))
forall poly.
IsOrderedPolynomial poly =>
poly -> OrderedMonomial (MOrder poly) (Arity poly)
leadingMonomial OrderedPolynomial r ord 1
g
      step :: OrderedPolynomial r ord 1
-> OrderedPolynomial r ord 1
-> (OrderedPolynomial r ord 1, OrderedPolynomial r ord 1)
step OrderedPolynomial r ord 1
p OrderedPolynomial r ord 1
quo
        | OrderedPolynomial r ord 1 -> Bool
forall r. DecidableZero r => r -> Bool
isZero OrderedPolynomial r ord 1
p = (OrderedPolynomial r ord 1
quo, OrderedPolynomial r ord 1
p)
        | OrderedMonomial ord 1
OrderedMonomial
  (MOrder (OrderedPolynomial r ord 1))
  (Arity (OrderedPolynomial r ord 1))
lm OrderedMonomial ord 1 -> OrderedMonomial ord 1 -> Bool
forall k (n :: Nat) (ord :: k).
KnownNat n =>
OrderedMonomial ord n -> OrderedMonomial ord n -> Bool
`divs` OrderedPolynomial r ord 1
-> OrderedMonomial
     (MOrder (OrderedPolynomial r ord 1))
     (Arity (OrderedPolynomial r ord 1))
forall poly.
IsOrderedPolynomial poly =>
poly -> OrderedMonomial (MOrder poly) (Arity poly)
leadingMonomial OrderedPolynomial r ord 1
p =
          let q :: OrderedPolynomial r ord 1
q = (Coefficient (OrderedPolynomial r ord 1),
 OrderedMonomial
   (MOrder (OrderedPolynomial r ord 1))
   (Arity (OrderedPolynomial r ord 1)))
-> OrderedPolynomial r ord 1
forall poly.
IsOrderedPolynomial poly =>
(Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
-> poly
toPolynomial ((Coefficient (OrderedPolynomial r ord 1),
  OrderedMonomial
    (MOrder (OrderedPolynomial r ord 1))
    (Arity (OrderedPolynomial r ord 1)))
 -> OrderedPolynomial r ord 1)
-> (Coefficient (OrderedPolynomial r ord 1),
    OrderedMonomial
      (MOrder (OrderedPolynomial r ord 1))
      (Arity (OrderedPolynomial r ord 1)))
-> OrderedPolynomial r ord 1
forall a b. (a -> b) -> a -> b
$ OrderedPolynomial r ord 1
-> (Coefficient (OrderedPolynomial r ord 1),
    OrderedMonomial
      (MOrder (OrderedPolynomial r ord 1))
      (Arity (OrderedPolynomial r ord 1)))
forall poly.
IsOrderedPolynomial poly =>
poly
-> (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
leadingTerm OrderedPolynomial r ord 1
p (r, OrderedMonomial ord 1)
-> (r, OrderedMonomial ord 1) -> (r, OrderedMonomial ord 1)
forall k (n :: Nat) r (ord :: k).
(KnownNat n, Field r) =>
(r, OrderedMonomial ord n)
-> (r, OrderedMonomial ord n) -> (r, OrderedMonomial ord n)
`tryDiv` OrderedPolynomial r ord 1
-> (Coefficient (OrderedPolynomial r ord 1),
    OrderedMonomial
      (MOrder (OrderedPolynomial r ord 1))
      (Arity (OrderedPolynomial r ord 1)))
forall poly.
IsOrderedPolynomial poly =>
poly
-> (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
leadingTerm OrderedPolynomial r ord 1
g
           in OrderedPolynomial r ord 1
-> OrderedPolynomial r ord 1
-> (OrderedPolynomial r ord 1, OrderedPolynomial r ord 1)
step (OrderedPolynomial r ord 1
p OrderedPolynomial r ord 1
-> OrderedPolynomial r ord 1 -> OrderedPolynomial r ord 1
forall r. Group r => r -> r -> r
- (OrderedPolynomial r ord 1
q OrderedPolynomial r ord 1
-> OrderedPolynomial r ord 1 -> OrderedPolynomial r ord 1
forall r. Multiplicative r => r -> r -> r
* OrderedPolynomial r ord 1
g)) (OrderedPolynomial r ord 1
quo OrderedPolynomial r ord 1
-> OrderedPolynomial r ord 1 -> OrderedPolynomial r ord 1
forall r. Additive r => r -> r -> r
+ OrderedPolynomial r ord 1
q)
        | Bool
otherwise = (OrderedPolynomial r ord 1
quo, OrderedPolynomial r ord 1
p)
  degree :: OrderedPolynomial r ord 1 -> Maybe Natural
degree OrderedPolynomial r ord 1
f
    | OrderedPolynomial r ord 1 -> Bool
forall r. DecidableZero r => r -> Bool
isZero OrderedPolynomial r ord 1
f = Maybe Natural
forall a. Maybe a
Nothing
    | Bool
otherwise = Natural -> Maybe Natural
forall a. a -> Maybe a
Just (Natural -> Maybe Natural) -> Natural -> Maybe Natural
forall a b. (a -> b) -> a -> b
$ Int -> Natural
forall a b. (Integral a, Num b) => a -> b
P.fromIntegral (Int -> Natural) -> Int -> Natural
forall a b. (a -> b) -> a -> b
$ OrderedPolynomial r ord 1 -> Int
forall poly. IsPolynomial poly => poly -> Int
totalDegree' OrderedPolynomial r ord 1
f

instance
  ( Eq r
  , DecidableUnits r
  , DecidableZero r
  , KnownNat n
  , Field r
  , IsMonomialOrder n ord
  , ZeroProductSemiring r
  ) =>
  ZeroProductSemiring (OrderedPolynomial r ord n)

instance
  {-# OVERLAPPING #-}
  ( Eq r
  , DecidableUnits r
  , DecidableZero r
  , Field r
  , IsMonomialOrder 1 ord
  , ZeroProductSemiring r
  ) =>
  IntegralDomain (OrderedPolynomial r ord 1)

instance
  ( Eq r
  , DecidableUnits r
  , DecidableZero r
  , KnownNat n
  , Field r
  , IsMonomialOrder n ord
  , ZeroProductSemiring r
  ) =>
  IntegralDomain (OrderedPolynomial r ord n)
  where
  OrderedPolynomial r ord n
p divides :: OrderedPolynomial r ord n -> OrderedPolynomial r ord n -> Bool
`divides` OrderedPolynomial r ord n
q = OrderedPolynomial r ord n -> Bool
forall r. DecidableZero r => r -> Bool
isZero (OrderedPolynomial r ord n -> Bool)
-> OrderedPolynomial r ord n -> Bool
forall a b. (a -> b) -> a -> b
$ OrderedPolynomial r ord n
p OrderedPolynomial r ord n
-> [OrderedPolynomial r ord n] -> OrderedPolynomial r ord n
forall poly (t :: * -> *).
(IsOrderedPolynomial poly, Field (Coefficient poly), Functor t,
 Foldable t) =>
poly -> t poly -> poly
`modPolynomial` [OrderedPolynomial r ord n
q]
  OrderedPolynomial r ord n
p maybeQuot :: OrderedPolynomial r ord n
-> OrderedPolynomial r ord n -> Maybe (OrderedPolynomial r ord n)
`maybeQuot` OrderedPolynomial r ord n
q =
    if OrderedPolynomial r ord n -> Bool
forall r. DecidableZero r => r -> Bool
isZero OrderedPolynomial r ord n
q
      then Maybe (OrderedPolynomial r ord n)
forall a. Maybe a
Nothing
      else
        let ([(OrderedPolynomial r ord n, OrderedPolynomial r ord n)]
r, OrderedPolynomial r ord n
s) = OrderedPolynomial r ord n
p OrderedPolynomial r ord n
-> [OrderedPolynomial r ord n]
-> ([(OrderedPolynomial r ord n, OrderedPolynomial r ord n)],
    OrderedPolynomial r ord n)
forall poly.
(IsOrderedPolynomial poly, Field (Coefficient poly)) =>
poly -> [poly] -> ([(poly, poly)], poly)
`divModPolynomial` [OrderedPolynomial r ord n
q]
         in if OrderedPolynomial r ord n -> Bool
forall r. DecidableZero r => r -> Bool
isZero OrderedPolynomial r ord n
s
              then OrderedPolynomial r ord n -> Maybe (OrderedPolynomial r ord n)
forall a. a -> Maybe a
Just (OrderedPolynomial r ord n -> Maybe (OrderedPolynomial r ord n))
-> OrderedPolynomial r ord n -> Maybe (OrderedPolynomial r ord n)
forall a b. (a -> b) -> a -> b
$ (OrderedPolynomial r ord n, OrderedPolynomial r ord n)
-> OrderedPolynomial r ord n
forall a b. (a, b) -> b
snd ((OrderedPolynomial r ord n, OrderedPolynomial r ord n)
 -> OrderedPolynomial r ord n)
-> (OrderedPolynomial r ord n, OrderedPolynomial r ord n)
-> OrderedPolynomial r ord n
forall a b. (a -> b) -> a -> b
$ [(OrderedPolynomial r ord n, OrderedPolynomial r ord n)]
-> (OrderedPolynomial r ord n, OrderedPolynomial r ord n)
forall a. [a] -> a
head [(OrderedPolynomial r ord n, OrderedPolynomial r ord n)]
r
              else Maybe (OrderedPolynomial r ord n)
forall a. Maybe a
Nothing

instance
  (CoeffRing r, IsMonomialOrder n ord, DecidableUnits r, KnownNat n) =>
  DecidableUnits (OrderedPolynomial r ord n)
  where
  isUnit :: OrderedPolynomial r ord n -> Bool
isUnit = OrderedPolynomial r ord n -> Bool
forall r poly.
(DecidableUnits r, Coefficient poly ~ r, IsPolynomial poly) =>
poly -> Bool
isUnitDefault
  recipUnit :: OrderedPolynomial r ord n -> Maybe (OrderedPolynomial r ord n)
recipUnit = OrderedPolynomial r ord n -> Maybe (OrderedPolynomial r ord n)
forall r poly.
(DecidableUnits r, Coefficient poly ~ r, IsPolynomial poly) =>
poly -> Maybe poly
recipUnitDefault

varX ::
  forall r n order.
  (CoeffRing r, KnownNat n, IsMonomialOrder n order, (0 < n)) =>
  OrderedPolynomial r order n
varX :: OrderedPolynomial r order n
varX = Ordinal (Arity (OrderedPolynomial r order n))
-> OrderedPolynomial r order n
forall poly. IsPolynomial poly => Ordinal (Arity poly) -> poly
var Ordinal (Arity (OrderedPolynomial r order n))
forall (n :: Nat). (0 < n) => Ordinal n
OZ

-- | Substitute univariate polynomial using Horner's rule
substUnivariate ::
  (Module (Scalar r) b, Unital b, CoeffRing r, IsMonomialOrder 1 order) =>
  b ->
  OrderedPolynomial r order 1 ->
  b
substUnivariate :: b -> OrderedPolynomial r order 1 -> b
substUnivariate b
u OrderedPolynomial r order 1
f =
  let n :: Int
n = OrderedPolynomial r order 1 -> Int
forall poly. IsPolynomial poly => poly -> Int
totalDegree' OrderedPolynomial r order 1
f
   in (r -> b -> b) -> b -> [r] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr
        (\r
a b
b -> r -> Scalar r
forall r. r -> Scalar r
Scalar r
a Scalar r -> b -> b
forall r m. LeftModule r m => r -> m -> m
.* b
forall r. Unital r => r
one b -> b -> b
forall r. Additive r => r -> r -> r
+ b
b b -> b -> b
forall r. Multiplicative r => r -> r -> r
* b
u)
        (r -> Scalar r
forall r. r -> Scalar r
Scalar (OrderedMonomial
  (MOrder (OrderedPolynomial r order 1))
  (Arity (OrderedPolynomial r order 1))
-> OrderedPolynomial r order 1
-> Coefficient (OrderedPolynomial r order 1)
forall poly.
IsOrderedPolynomial poly =>
OrderedMonomial (MOrder poly) (Arity poly)
-> poly -> Coefficient poly
coeff (Monomial 1 -> OrderedMonomial order 1
forall k (ordering :: k) (n :: Nat).
Monomial n -> OrderedMonomial ordering n
OrderedMonomial (Monomial 1 -> OrderedMonomial order 1)
-> Monomial 1 -> OrderedMonomial order 1
forall a b. (a -> b) -> a -> b
$ Int -> Monomial 1
forall (f :: * -> *) a. (CPointed f, Dom f a) => a -> Sized f 1 a
singleton (Int -> Monomial 1) -> Int -> Monomial 1
forall a b. (a -> b) -> a -> b
$ Int -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
n) OrderedPolynomial r order 1
f) Scalar r -> b -> b
forall r m. LeftModule r m => r -> m -> m
.* b
forall r. Unital r => r
one)
        [OrderedMonomial
  (MOrder (OrderedPolynomial r order 1))
  (Arity (OrderedPolynomial r order 1))
-> OrderedPolynomial r order 1
-> Coefficient (OrderedPolynomial r order 1)
forall poly.
IsOrderedPolynomial poly =>
OrderedMonomial (MOrder poly) (Arity poly)
-> poly -> Coefficient poly
coeff (Monomial 1 -> OrderedMonomial order 1
forall k (ordering :: k) (n :: Nat).
Monomial n -> OrderedMonomial ordering n
OrderedMonomial (Monomial 1 -> OrderedMonomial order 1)
-> Monomial 1 -> OrderedMonomial order 1
forall a b. (a -> b) -> a -> b
$ Int -> Monomial 1
forall (f :: * -> *) a. (CPointed f, Dom f a) => a -> Sized f 1 a
singleton (Int -> Monomial 1) -> Int -> Monomial 1
forall a b. (a -> b) -> a -> b
$ Int -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
i) OrderedPolynomial r order 1
f | Int
i <- [Int
0 .. Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
P.- Int
1]]

evalUnivariate :: (CoeffRing b, IsMonomialOrder 1 order) => b -> OrderedPolynomial b order 1 -> b
evalUnivariate :: b -> OrderedPolynomial b order 1 -> b
evalUnivariate b
u OrderedPolynomial b order 1
f =
  let n :: Int
n = OrderedPolynomial b order 1 -> Int
forall poly. IsPolynomial poly => poly -> Int
totalDegree' OrderedPolynomial b order 1
f
   in if Int
n Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0
        then OrderedMonomial
  (MOrder (OrderedPolynomial b order 1))
  (Arity (OrderedPolynomial b order 1))
-> OrderedPolynomial b order 1
-> Coefficient (OrderedPolynomial b order 1)
forall poly.
IsOrderedPolynomial poly =>
OrderedMonomial (MOrder poly) (Arity poly)
-> poly -> Coefficient poly
coeff OrderedMonomial
  (MOrder (OrderedPolynomial b order 1))
  (Arity (OrderedPolynomial b order 1))
forall r. Unital r => r
one OrderedPolynomial b order 1
f
        else (b -> b -> b) -> [b] -> b
forall (t :: * -> *) a. Foldable t => (a -> a -> a) -> t a -> a
foldr1 (\b
a b
b -> b
a b -> b -> b
forall r. Additive r => r -> r -> r
+ b
b b -> b -> b
forall r. Multiplicative r => r -> r -> r
* b
u) [OrderedMonomial
  (MOrder (OrderedPolynomial b order 1))
  (Arity (OrderedPolynomial b order 1))
-> OrderedPolynomial b order 1
-> Coefficient (OrderedPolynomial b order 1)
forall poly.
IsOrderedPolynomial poly =>
OrderedMonomial (MOrder poly) (Arity poly)
-> poly -> Coefficient poly
coeff (Monomial 1 -> OrderedMonomial order 1
forall k (ordering :: k) (n :: Nat).
Monomial n -> OrderedMonomial ordering n
OrderedMonomial (Monomial 1 -> OrderedMonomial order 1)
-> Monomial 1 -> OrderedMonomial order 1
forall a b. (a -> b) -> a -> b
$ Int -> Monomial 1
forall (f :: * -> *) a. (CPointed f, Dom f a) => a -> Sized f 1 a
singleton (Int -> Monomial 1) -> Int -> Monomial 1
forall a b. (a -> b) -> a -> b
$ Int -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
i) OrderedPolynomial b order 1
f | Int
i <- [Int
0 .. Int
n]]

-- | Evaluate polynomial at some point.
eval ::
  (CoeffRing r, IsMonomialOrder n order, KnownNat n) =>
  Sized n r ->
  OrderedPolynomial r order n ->
  r
eval :: Sized n r -> OrderedPolynomial r order n -> r
eval = (Coefficient (OrderedPolynomial r order n) -> r -> r)
-> Sized (Arity (OrderedPolynomial r order n)) r
-> OrderedPolynomial r order n
-> r
forall poly m.
(IsPolynomial poly, Ring m) =>
(Coefficient poly -> m -> m) -> Sized (Arity poly) m -> poly -> m
substWith Coefficient (OrderedPolynomial r order n) -> r -> r
forall r. Multiplicative r => r -> r -> r
(*)

-- evalOn :: forall k a order . (SingI k, CoeffRing a, IsMonomialOrder order)
--       => OrderedPolynomial a order k -> RepArgs k a a
-- evalOn p = fromNAry $ (fromVecFun (flip eval p) :: NAry k a a)

{- | @substVar n f@ substitutes @n@-th variable with polynomial @f@,
   without changing arity.
-}
substVar ::
  (CoeffRing r, KnownNat n, IsMonomialOrder n ord, (1 <= n)) =>
  Ordinal n ->
  OrderedPolynomial r ord n ->
  OrderedPolynomial r ord n ->
  OrderedPolynomial r ord n
substVar :: Ordinal n
-> OrderedPolynomial r ord n
-> OrderedPolynomial r ord n
-> OrderedPolynomial r ord n
substVar Ordinal n
p OrderedPolynomial r ord n
val =
  (Ordinal (Arity (OrderedPolynomial r ord n))
 -> OrderedPolynomial r ord n)
-> OrderedPolynomial r ord n -> OrderedPolynomial r ord n
forall poly alg.
(IsPolynomial poly, Module (Scalar (Coefficient poly)) alg,
 Ring alg, Commutative alg) =>
(Ordinal (Arity poly) -> alg) -> poly -> alg
liftMap (\Ordinal (Arity (OrderedPolynomial r ord n))
o -> if Ordinal n
Ordinal (Arity (OrderedPolynomial r ord n))
o Ordinal n -> Ordinal n -> Bool
forall a. Eq a => a -> a -> Bool
== Ordinal n
p then OrderedPolynomial r ord n
val else Ordinal (Arity (OrderedPolynomial r ord n))
-> OrderedPolynomial r ord n
forall poly. IsPolynomial poly => Ordinal (Arity poly) -> poly
var Ordinal (Arity (OrderedPolynomial r ord n))
o)

allVars ::
  forall k ord n.
  (IsMonomialOrder n ord, CoeffRing k, KnownNat n) =>
  Sized n (OrderedPolynomial k ord n)
allVars :: Sized n (OrderedPolynomial k ord n)
allVars = [OrderedPolynomial k ord n] -> Sized n (OrderedPolynomial k ord n)
forall (f :: * -> *) (n :: Nat) a.
(KnownNat n, CFreeMonoid f, Dom f a) =>
[a] -> Sized f n a
unsafeFromList' [OrderedPolynomial k ord n]
forall poly. IsPolynomial poly => [poly]
vars

changeOrder ::
  forall k n o o'.
  (CoeffRing k, Eq (Monomial n), IsMonomialOrder n o, IsMonomialOrder n o', KnownNat n) =>
  o' ->
  OrderedPolynomial k o n ->
  OrderedPolynomial k o' n
changeOrder :: o' -> OrderedPolynomial k o n -> OrderedPolynomial k o' n
changeOrder o'
_ =
  forall b.
Coercible
  (Map (OrderedMonomial o n) k -> Map (OrderedMonomial o' n) k) b =>
(Map (OrderedMonomial o n) k -> Map (OrderedMonomial o' n) k) -> b
C.coerce @(Map (OrderedMonomial o n) k -> Map (OrderedMonomial o' n) k) ((Map (OrderedMonomial o n) k -> Map (OrderedMonomial o' n) k)
 -> OrderedPolynomial k o n -> OrderedPolynomial k o' n)
-> (Map (OrderedMonomial o n) k -> Map (OrderedMonomial o' n) k)
-> OrderedPolynomial k o n
-> OrderedPolynomial k o' n
forall a b. (a -> b) -> a -> b
$
    (OrderedMonomial o n -> OrderedMonomial o' n)
-> Map (OrderedMonomial o n) k -> Map (OrderedMonomial o' n) k
forall k2 k1 a. Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a
M.mapKeys (Monomial n -> OrderedMonomial o' n
forall k (ordering :: k) (n :: Nat).
Monomial n -> OrderedMonomial ordering n
OrderedMonomial (Monomial n -> OrderedMonomial o' n)
-> (OrderedMonomial o n -> Monomial n)
-> OrderedMonomial o n
-> OrderedMonomial o' n
forall b c a. (b -> c) -> (a -> b) -> a -> c
. OrderedMonomial o n -> Monomial n
forall k (ordering :: k) (n :: Nat).
OrderedMonomial ordering n -> Monomial n
getMonomial)

changeOrderProxy ::
  forall k n o o'.
  ( CoeffRing k
  , Eq (Monomial n)
  , IsMonomialOrder n o
  , IsMonomialOrder n o'
  , KnownNat n
  ) =>
  Proxy o' ->
  OrderedPolynomial k o n ->
  OrderedPolynomial k o' n
changeOrderProxy :: Proxy o' -> OrderedPolynomial k o n -> OrderedPolynomial k o' n
changeOrderProxy Proxy o'
_ =
  forall b.
Coercible
  (Map (OrderedMonomial o n) k -> Map (OrderedMonomial o' n) k) b =>
(Map (OrderedMonomial o n) k -> Map (OrderedMonomial o' n) k) -> b
C.coerce @(Map (OrderedMonomial o n) k -> Map (OrderedMonomial o' n) k) ((Map (OrderedMonomial o n) k -> Map (OrderedMonomial o' n) k)
 -> OrderedPolynomial k o n -> OrderedPolynomial k o' n)
-> (Map (OrderedMonomial o n) k -> Map (OrderedMonomial o' n) k)
-> OrderedPolynomial k o n
-> OrderedPolynomial k o' n
forall a b. (a -> b) -> a -> b
$
    (OrderedMonomial o n -> OrderedMonomial o' n)
-> Map (OrderedMonomial o n) k -> Map (OrderedMonomial o' n) k
forall k2 k1 a. Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a
M.mapKeys (Monomial n -> OrderedMonomial o' n
forall k (ordering :: k) (n :: Nat).
Monomial n -> OrderedMonomial ordering n
OrderedMonomial (Monomial n -> OrderedMonomial o' n)
-> (OrderedMonomial o n -> Monomial n)
-> OrderedMonomial o n
-> OrderedMonomial o' n
forall b c a. (b -> c) -> (a -> b) -> a -> c
. OrderedMonomial o n -> Monomial n
forall k (ordering :: k) (n :: Nat).
OrderedMonomial ordering n -> Monomial n
getMonomial)

getTerms :: OrderedPolynomial k order n -> [(k, OrderedMonomial order n)]
getTerms :: OrderedPolynomial k order n -> [(k, OrderedMonomial order n)]
getTerms = ((OrderedMonomial order n, k) -> (k, OrderedMonomial order n))
-> [(OrderedMonomial order n, k)] -> [(k, OrderedMonomial order n)]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
map ((OrderedMonomial order n, k) -> k
forall a b. (a, b) -> b
snd ((OrderedMonomial order n, k) -> k)
-> ((OrderedMonomial order n, k) -> OrderedMonomial order n)
-> (OrderedMonomial order n, k)
-> (k, OrderedMonomial order n)
forall (a :: * -> * -> *) b c c'.
Arrow a =>
a b c -> a b c' -> a b (c, c')
&&& (OrderedMonomial order n, k) -> OrderedMonomial order n
forall a b. (a, b) -> a
fst) ([(OrderedMonomial order n, k)] -> [(k, OrderedMonomial order n)])
-> (OrderedPolynomial k order n -> [(OrderedMonomial order n, k)])
-> OrderedPolynomial k order n
-> [(k, OrderedMonomial order n)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map (OrderedMonomial order n) k -> [(OrderedMonomial order n, k)]
forall k a. Map k a -> [(k, a)]
M.toDescList (Map (OrderedMonomial order n) k -> [(OrderedMonomial order n, k)])
-> (OrderedPolynomial k order n -> Map (OrderedMonomial order n) k)
-> OrderedPolynomial k order n
-> [(OrderedMonomial order n, k)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. OrderedPolynomial k order n -> Map (OrderedMonomial order n) k
forall r k (order :: k) (n :: Nat).
OrderedPolynomial r order n -> Map (OrderedMonomial order n) r
_terms

transformMonomial ::
  (IsMonomialOrder m o', CoeffRing k, KnownNat m) =>
  (USized n Int -> USized m Int) ->
  OrderedPolynomial k o n ->
  OrderedPolynomial k o' m
transformMonomial :: (USized n Int -> USized m Int)
-> OrderedPolynomial k o n -> OrderedPolynomial k o' m
transformMonomial USized n Int -> USized m Int
tr (Polynomial Map (OrderedMonomial o n) k
d) =
  Map
  (OrderedMonomial
     (MOrder (OrderedPolynomial k o' m))
     (Arity (OrderedPolynomial k o' m)))
  (Coefficient (OrderedPolynomial k o' m))
-> OrderedPolynomial k o' m
forall poly.
IsOrderedPolynomial poly =>
Map (OrderedMonomial (MOrder poly) (Arity poly)) (Coefficient poly)
-> poly
polynomial (Map
   (OrderedMonomial
      (MOrder (OrderedPolynomial k o' m))
      (Arity (OrderedPolynomial k o' m)))
   (Coefficient (OrderedPolynomial k o' m))
 -> OrderedPolynomial k o' m)
-> Map
     (OrderedMonomial
        (MOrder (OrderedPolynomial k o' m))
        (Arity (OrderedPolynomial k o' m)))
     (Coefficient (OrderedPolynomial k o' m))
-> OrderedPolynomial k o' m
forall a b. (a -> b) -> a -> b
$ (OrderedMonomial o n -> OrderedMonomial o' m)
-> Map (OrderedMonomial o n) k -> Map (OrderedMonomial o' m) k
forall k2 k1 a. Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a
M.mapKeys (USized m Int -> OrderedMonomial o' m
forall k (ordering :: k) (n :: Nat).
Monomial n -> OrderedMonomial ordering n
OrderedMonomial (USized m Int -> OrderedMonomial o' m)
-> (OrderedMonomial o n -> USized m Int)
-> OrderedMonomial o n
-> OrderedMonomial o' m
forall b c a. (b -> c) -> (a -> b) -> a -> c
. USized n Int -> USized m Int
tr (USized n Int -> USized m Int)
-> (OrderedMonomial o n -> USized n Int)
-> OrderedMonomial o n
-> USized m Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. OrderedMonomial o n -> USized n Int
forall k (ordering :: k) (n :: Nat).
OrderedMonomial ordering n -> Monomial n
getMonomial) Map (OrderedMonomial o n) k
d

orderedBy :: OrderedPolynomial k o n -> o -> OrderedPolynomial k o n
OrderedPolynomial k o n
p orderedBy :: OrderedPolynomial k o n -> o -> OrderedPolynomial k o n
`orderedBy` o
_ = OrderedPolynomial k o n
p

shiftR ::
  forall k r n ord.
  ( CoeffRing r
  , KnownNat n
  , IsMonomialOrder n ord
  , IsMonomialOrder (k + n) ord
  ) =>
  SNat k ->
  OrderedPolynomial r ord n ->
  OrderedPolynomial r ord (k + n)
shiftR :: SNat k
-> OrderedPolynomial r ord n -> OrderedPolynomial r ord (k + n)
shiftR SNat k
k =
  SNat (k + n)
-> (KnownNat (k + n) =>
    OrderedPolynomial r ord n -> OrderedPolynomial r ord (k + n))
-> OrderedPolynomial r ord n
-> OrderedPolynomial r ord (k + n)
forall (n :: Nat) r. SNat n -> (KnownNat n => r) -> r
withKnownNat (SNat k
k SNat k -> SNat n -> SNat (k + n)
forall (n :: Nat) (m :: Nat). SNat n -> SNat m -> SNat (n + m)
%+ (SNat n
forall (n :: Nat). KnownNat n => SNat n
sNat :: SNat n)) ((KnownNat (k + n) =>
  OrderedPolynomial r ord n -> OrderedPolynomial r ord (k + n))
 -> OrderedPolynomial r ord n -> OrderedPolynomial r ord (k + n))
-> (KnownNat (k + n) =>
    OrderedPolynomial r ord n -> OrderedPolynomial r ord (k + n))
-> OrderedPolynomial r ord n
-> OrderedPolynomial r ord (k + n)
forall a b. (a -> b) -> a -> b
$
    SNat k
-> (KnownNat k =>
    OrderedPolynomial r ord n -> OrderedPolynomial r ord (k + n))
-> OrderedPolynomial r ord n
-> OrderedPolynomial r ord (k + n)
forall (n :: Nat) r. SNat n -> (KnownNat n => r) -> r
withKnownNat SNat k
k ((KnownNat k =>
  OrderedPolynomial r ord n -> OrderedPolynomial r ord (k + n))
 -> OrderedPolynomial r ord n -> OrderedPolynomial r ord (k + n))
-> (KnownNat k =>
    OrderedPolynomial r ord n -> OrderedPolynomial r ord (k + n))
-> OrderedPolynomial r ord n
-> OrderedPolynomial r ord (k + n)
forall a b. (a -> b) -> a -> b
$ (USized n Int -> USized (k + n) Int)
-> OrderedPolynomial r ord n -> OrderedPolynomial r ord (k + n)
forall k (m :: Nat) o' k (n :: Nat) (o :: k).
(IsMonomialOrder m o', CoeffRing k, KnownNat m) =>
(USized n Int -> USized m Int)
-> OrderedPolynomial k o n -> OrderedPolynomial k o' m
transformMonomial (Sized Vector k Int -> USized n Int -> USized (k + n) Int
forall (f :: * -> *) (n :: Nat) (m :: Nat) a.
(CFreeMonoid f, Dom f a) =>
Sized f n a -> Sized f m a -> Sized f (n + m) a
S.append (Int -> Sized Vector k Int
forall (f :: * -> *) (n :: Nat) a.
(KnownNat n, CFreeMonoid f, Dom f a) =>
a -> Sized f n a
S.replicate' Int
0))

-- | Calculate the homogenized polynomial of given one, with additional variable is the last variable.
homogenize ::
  forall k ord n.
  (CoeffRing k, KnownNat n, IsMonomialOrder (n + 1) ord, IsMonomialOrder n ord) =>
  OrderedPolynomial k ord n ->
  OrderedPolynomial k ord (n + 1)
homogenize :: OrderedPolynomial k ord n -> OrderedPolynomial k ord (n + 1)
homogenize OrderedPolynomial k ord n
f =
  let g :: OrderedPolynomial k ord (n + 1)
g = (Coefficient (OrderedPolynomial k ord n)
 -> OrderedPolynomial k ord (n + 1)
 -> OrderedPolynomial k ord (n + 1))
-> Sized
     (Arity (OrderedPolynomial k ord n))
     (OrderedPolynomial k ord (n + 1))
-> OrderedPolynomial k ord n
-> OrderedPolynomial k ord (n + 1)
forall poly m.
(IsPolynomial poly, Ring m) =>
(Coefficient poly -> m -> m) -> Sized (Arity poly) m -> poly -> m
substWith Coefficient (OrderedPolynomial k ord n)
-> OrderedPolynomial k ord (n + 1)
-> OrderedPolynomial k ord (n + 1)
forall r m. Module (Scalar r) m => r -> m -> m
(.*.) (Sized Vector (n + 1) (OrderedPolynomial k ord (n + 1))
-> Sized Vector n (OrderedPolynomial k ord (n + 1))
forall (f :: * -> *) (n :: Nat) a.
(CFreeMonoid f, Dom f a) =>
Sized f (n + 1) a -> Sized f n a
S.init Sized Vector (n + 1) (OrderedPolynomial k ord (n + 1))
forall k ord (n :: Nat).
(IsMonomialOrder n ord, CoeffRing k, KnownNat n) =>
Sized n (OrderedPolynomial k ord n)
allVars) OrderedPolynomial k ord n
f
      d :: Int
d = Int -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (OrderedPolynomial k ord (n + 1) -> Int
forall poly. IsPolynomial poly => poly -> Int
totalDegree' OrderedPolynomial k ord (n + 1)
g)
   in (OrderedMonomial
   (MOrder (OrderedPolynomial k ord (n + 1)))
   (Arity (OrderedPolynomial k ord (n + 1)))
 -> OrderedMonomial
      (MOrder (OrderedPolynomial k ord (n + 1)))
      (Arity (OrderedPolynomial k ord (n + 1))))
-> OrderedPolynomial k ord (n + 1)
-> OrderedPolynomial k ord (n + 1)
forall poly.
IsOrderedPolynomial poly =>
(OrderedMonomial (MOrder poly) (Arity poly)
 -> OrderedMonomial (MOrder poly) (Arity poly))
-> poly -> poly
mapMonomialMonotonic (\OrderedMonomial
  (MOrder (OrderedPolynomial k ord (n + 1)))
  (Arity (OrderedPolynomial k ord (n + 1)))
m -> OrderedMonomial ord (n + 1)
OrderedMonomial
  (MOrder (OrderedPolynomial k ord (n + 1)))
  (Arity (OrderedPolynomial k ord (n + 1)))
m OrderedMonomial ord (n + 1)
-> (OrderedMonomial ord (n + 1) -> OrderedMonomial ord (n + 1))
-> OrderedMonomial ord (n + 1)
forall a b. a -> (a -> b) -> b
& (Monomial (n + 1) -> Identity (Monomial (n + 1)))
-> OrderedMonomial ord (n + 1)
-> Identity (OrderedMonomial ord (n + 1))
forall s t. Rewrapping s t => Iso s t (Unwrapped s) (Unwrapped t)
_Wrapped ((Monomial (n + 1) -> Identity (Monomial (n + 1)))
 -> OrderedMonomial ord (n + 1)
 -> Identity (OrderedMonomial ord (n + 1)))
-> ((Int -> Identity Int)
    -> Monomial (n + 1) -> Identity (Monomial (n + 1)))
-> (Int -> Identity Int)
-> OrderedMonomial ord (n + 1)
-> Identity (OrderedMonomial ord (n + 1))
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Index (Monomial (n + 1))
-> Traversal' (Monomial (n + 1)) (IxValue (Monomial (n + 1)))
forall m. Ixed m => Index m -> Traversal' m (IxValue m)
ix Index (Monomial (n + 1))
forall a. Bounded a => a
maxBound ((Int -> Identity Int)
 -> OrderedMonomial ord (n + 1)
 -> Identity (OrderedMonomial ord (n + 1)))
-> Int
-> OrderedMonomial ord (n + 1)
-> OrderedMonomial ord (n + 1)
forall s t a b. ASetter s t a b -> b -> s -> t
.~ Int
d Int -> Int -> Int
forall r. Group r => r -> r -> r
- Monomial (n + 1) -> Element (Monomial (n + 1))
forall mono.
(MonoFoldable mono, Num (Element mono)) =>
mono -> Element mono
osum (OrderedMonomial ord (n + 1)
OrderedMonomial
  (MOrder (OrderedPolynomial k ord (n + 1)))
  (Arity (OrderedPolynomial k ord (n + 1)))
m OrderedMonomial ord (n + 1)
-> Getting
     (Monomial (n + 1)) (OrderedMonomial ord (n + 1)) (Monomial (n + 1))
-> Monomial (n + 1)
forall s a. s -> Getting a s a -> a
^. Getting
  (Monomial (n + 1)) (OrderedMonomial ord (n + 1)) (Monomial (n + 1))
forall s t. Rewrapping s t => Iso s t (Unwrapped s) (Unwrapped t)
_Wrapped)) OrderedPolynomial k ord (n + 1)
g

unhomogenize ::
  forall k ord n.
  ( CoeffRing k
  , KnownNat n
  , IsMonomialOrder n ord
  , IsMonomialOrder (n + 1) ord
  ) =>
  OrderedPolynomial k ord (n + 1) ->
  OrderedPolynomial k ord n
unhomogenize :: OrderedPolynomial k ord (n + 1) -> OrderedPolynomial k ord n
unhomogenize =
  (Coefficient (OrderedPolynomial k ord (n + 1))
 -> OrderedPolynomial k ord n -> OrderedPolynomial k ord n)
-> Sized
     (Arity (OrderedPolynomial k ord (n + 1)))
     (OrderedPolynomial k ord n)
-> OrderedPolynomial k ord (n + 1)
-> OrderedPolynomial k ord n
forall poly m.
(IsPolynomial poly, Ring m) =>
(Coefficient poly -> m -> m) -> Sized (Arity poly) m -> poly -> m
substWith
    Coefficient (OrderedPolynomial k ord (n + 1))
-> OrderedPolynomial k ord n -> OrderedPolynomial k ord n
forall r m. Module (Scalar r) m => r -> m -> m
(.*.)
    ( Sized n (OrderedPolynomial k ord n)
forall k ord (n :: Nat).
(IsMonomialOrder n ord, CoeffRing k, KnownNat n) =>
Sized n (OrderedPolynomial k ord n)
allVars Sized n (OrderedPolynomial k ord n)
-> Sized Vector 1 (OrderedPolynomial k ord n)
-> Sized Vector (n + 1) (OrderedPolynomial k ord n)
forall (f :: * -> *) (n :: Nat) (m :: Nat) a.
(CFreeMonoid f, Dom f a) =>
Sized f n a -> Sized f m a -> Sized f (n + m) a
`S.append` OrderedPolynomial k ord n
-> Sized Vector 1 (OrderedPolynomial k ord n)
forall (f :: * -> *) a. (CPointed f, Dom f a) => a -> Sized f 1 a
S.singleton OrderedPolynomial k ord n
forall r. Unital r => r
one
    )

reversal ::
  (CoeffRing k, IsMonomialOrder 1 o) =>
  Int ->
  OrderedPolynomial k o 1 ->
  OrderedPolynomial k o 1
reversal :: Int -> OrderedPolynomial k o 1 -> OrderedPolynomial k o 1
reversal Int
k = (Monomial 1 -> Monomial 1)
-> OrderedPolynomial k o 1 -> OrderedPolynomial k o 1
forall k (m :: Nat) o' k (n :: Nat) (o :: k).
(IsMonomialOrder m o', CoeffRing k, KnownNat m) =>
(USized n Int -> USized m Int)
-> OrderedPolynomial k o n -> OrderedPolynomial k o' m
transformMonomial ((Int -> Int) -> Monomial 1 -> Monomial 1
forall (f :: * -> *) (n :: Nat) a b.
(CFreeMonoid f, Dom f a, Dom f b) =>
(a -> b) -> Sized f n a -> Sized f n b
S.map (Int
k Int -> Int -> Int
forall r. Group r => r -> r -> r
-))

padeApprox ::
  ( Field r
  , DecidableUnits r
  , CoeffRing r
  , ZeroProductSemiring r
  , IsMonomialOrder 1 order
  ) =>
  Natural ->
  Natural ->
  OrderedPolynomial r order 1 ->
  (OrderedPolynomial r order 1, OrderedPolynomial r order 1)
padeApprox :: Natural
-> Natural
-> OrderedPolynomial r order 1
-> (OrderedPolynomial r order 1, OrderedPolynomial r order 1)
padeApprox Natural
k Natural
nmk OrderedPolynomial r order 1
g =
  let (OrderedPolynomial r order 1
r, OrderedPolynomial r order 1
_, OrderedPolynomial r order 1
t) = [(OrderedPolynomial r order 1, OrderedPolynomial r order 1,
  OrderedPolynomial r order 1)]
-> (OrderedPolynomial r order 1, OrderedPolynomial r order 1,
    OrderedPolynomial r order 1)
forall a. [a] -> a
last ([(OrderedPolynomial r order 1, OrderedPolynomial r order 1,
   OrderedPolynomial r order 1)]
 -> (OrderedPolynomial r order 1, OrderedPolynomial r order 1,
     OrderedPolynomial r order 1))
-> [(OrderedPolynomial r order 1, OrderedPolynomial r order 1,
     OrderedPolynomial r order 1)]
-> (OrderedPolynomial r order 1, OrderedPolynomial r order 1,
    OrderedPolynomial r order 1)
forall a b. (a -> b) -> a -> b
$ ((OrderedPolynomial r order 1, OrderedPolynomial r order 1,
  OrderedPolynomial r order 1)
 -> Bool)
-> [(OrderedPolynomial r order 1, OrderedPolynomial r order 1,
     OrderedPolynomial r order 1)]
-> [(OrderedPolynomial r order 1, OrderedPolynomial r order 1,
     OrderedPolynomial r order 1)]
forall a. (a -> Bool) -> [a] -> [a]
filter ((Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Natural -> Int
forall a b. (Integral a, Num b) => a -> b
P.fromIntegral Natural
k) (Int -> Bool)
-> ((OrderedPolynomial r order 1, OrderedPolynomial r order 1,
     OrderedPolynomial r order 1)
    -> Int)
-> (OrderedPolynomial r order 1, OrderedPolynomial r order 1,
    OrderedPolynomial r order 1)
-> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. OrderedPolynomial r order 1 -> Int
forall poly. IsPolynomial poly => poly -> Int
totalDegree' (OrderedPolynomial r order 1 -> Int)
-> ((OrderedPolynomial r order 1, OrderedPolynomial r order 1,
     OrderedPolynomial r order 1)
    -> OrderedPolynomial r order 1)
-> (OrderedPolynomial r order 1, OrderedPolynomial r order 1,
    OrderedPolynomial r order 1)
-> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Getting
  (OrderedPolynomial r order 1)
  (OrderedPolynomial r order 1, OrderedPolynomial r order 1,
   OrderedPolynomial r order 1)
  (OrderedPolynomial r order 1)
-> (OrderedPolynomial r order 1, OrderedPolynomial r order 1,
    OrderedPolynomial r order 1)
-> OrderedPolynomial r order 1
forall s (m :: * -> *) a. MonadReader s m => Getting a s a -> m a
view Getting
  (OrderedPolynomial r order 1)
  (OrderedPolynomial r order 1, OrderedPolynomial r order 1,
   OrderedPolynomial r order 1)
  (OrderedPolynomial r order 1)
forall s t a b. Field1 s t a b => Lens s t a b
_1) ([(OrderedPolynomial r order 1, OrderedPolynomial r order 1,
   OrderedPolynomial r order 1)]
 -> [(OrderedPolynomial r order 1, OrderedPolynomial r order 1,
      OrderedPolynomial r order 1)])
-> [(OrderedPolynomial r order 1, OrderedPolynomial r order 1,
     OrderedPolynomial r order 1)]
-> [(OrderedPolynomial r order 1, OrderedPolynomial r order 1,
     OrderedPolynomial r order 1)]
forall a b. (a -> b) -> a -> b
$ OrderedPolynomial r order 1
-> OrderedPolynomial r order 1
-> [(OrderedPolynomial r order 1, OrderedPolynomial r order 1,
     OrderedPolynomial r order 1)]
forall d. Euclidean d => d -> d -> [(d, d, d)]
euclid (OrderedPolynomial r order 1
-> Natural -> OrderedPolynomial r order 1
forall r. Unital r => r -> Natural -> r
pow OrderedPolynomial r order 1
forall r (n :: Nat) order.
(CoeffRing r, KnownNat n, IsMonomialOrder n order, 0 < n) =>
OrderedPolynomial r order n
varX (Natural
k Natural -> Natural -> Natural
forall r. Additive r => r -> r -> r
+ Natural
nmk)) OrderedPolynomial r order 1
g
   in (OrderedPolynomial r order 1
r, OrderedPolynomial r order 1
t)

minpolRecurrent ::
  forall k.
  (Eq k, ZeroProductSemiring k, DecidableUnits k, DecidableZero k, Field k) =>
  Natural ->
  [k] ->
  Polynomial k 1
minpolRecurrent :: Natural -> [k] -> Polynomial k 1
minpolRecurrent Natural
n [k]
xs =
  let h :: Polynomial k 1
h =
        [Polynomial k 1] -> Polynomial k 1
forall (f :: * -> *) m. (Foldable f, Monoidal m) => f m -> m
sum ([Polynomial k 1] -> Polynomial k 1)
-> [Polynomial k 1] -> Polynomial k 1
forall a b. (a -> b) -> a -> b
$ (k -> Polynomial k 1 -> Polynomial k 1)
-> [k] -> [Polynomial k 1] -> [Polynomial k 1]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith (\k
a Polynomial k 1
b -> Coefficient (Polynomial k 1) -> Polynomial k 1
forall poly. IsPolynomial poly => Coefficient poly -> poly
injectCoeff k
Coefficient (Polynomial k 1)
a Polynomial k 1 -> Polynomial k 1 -> Polynomial k 1
forall r. Multiplicative r => r -> r -> r
* Polynomial k 1
b) [k]
xs [Polynomial k 1 -> Natural -> Polynomial k 1
forall r. Unital r => r -> Natural -> r
pow Polynomial k 1
forall r (n :: Nat) order.
(CoeffRing r, KnownNat n, IsMonomialOrder n order, 0 < n) =>
OrderedPolynomial r order n
varX Natural
i | Natural
i <- [Natural
0 .. Natural -> Natural
forall a. Enum a => a -> a
pred (Natural
2 Natural -> Natural -> Natural
forall r. Multiplicative r => r -> r -> r
* Natural
n)]] ::
          Polynomial k 1
      (Polynomial k 1
s, Polynomial k 1
t) = Natural
-> Natural -> Polynomial k 1 -> (Polynomial k 1, Polynomial k 1)
forall r order.
(Field r, DecidableUnits r, CoeffRing r, ZeroProductSemiring r,
 IsMonomialOrder 1 order) =>
Natural
-> Natural
-> OrderedPolynomial r order 1
-> (OrderedPolynomial r order 1, OrderedPolynomial r order 1)
padeApprox Natural
n Natural
n Polynomial k 1
h
      d :: Int
d = Int -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int -> Int) -> Int -> Int
forall a b. (a -> b) -> a -> b
$ Int -> Int -> Int
forall a. Ord a => a -> a -> a
max (Int
1 Int -> Int -> Int
forall r. Additive r => r -> r -> r
+ Polynomial k 1 -> Int
forall poly. IsPolynomial poly => poly -> Int
totalDegree' Polynomial k 1
s) (Polynomial k 1 -> Int
forall poly. IsPolynomial poly => poly -> Int
totalDegree' Polynomial k 1
t)
   in Int -> Polynomial k 1 -> Polynomial k 1
forall k o.
(CoeffRing k, IsMonomialOrder 1 o) =>
Int -> OrderedPolynomial k o 1 -> OrderedPolynomial k o 1
reversal Int
d (k -> k
forall r. Division r => r -> r
recip (OrderedMonomial (MOrder (Polynomial k 1)) (Arity (Polynomial k 1))
-> Polynomial k 1 -> Coefficient (Polynomial k 1)
forall poly.
IsOrderedPolynomial poly =>
OrderedMonomial (MOrder poly) (Arity poly)
-> poly -> Coefficient poly
coeff OrderedMonomial (MOrder (Polynomial k 1)) (Arity (Polynomial k 1))
forall r. Unital r => r
one Polynomial k 1
t) k -> Polynomial k 1 -> Polynomial k 1
forall r m. Module (Scalar r) m => r -> m -> m
.*. Polynomial k 1
t)

newtype PadPolyL n ord poly = PadPolyL {PadPolyL n ord poly -> OrderedPolynomial poly (Graded ord) n
runPadPolyL :: OrderedPolynomial poly (Graded ord) n}

deriving instance
  (KnownNat n, IsMonomialOrder n ord, IsPolynomial poly) =>
  Additive (PadPolyL n ord poly)

deriving instance
  (KnownNat n, IsMonomialOrder n ord, IsPolynomial poly) =>
  LeftModule Natural (PadPolyL n ord poly)

deriving instance
  (KnownNat n, IsMonomialOrder n ord, IsPolynomial poly) =>
  RightModule Natural (PadPolyL n ord poly)

deriving instance
  (KnownNat n, IsMonomialOrder n ord, IsPolynomial poly) =>
  Monoidal (PadPolyL n ord poly)

deriving instance
  (KnownNat n, IsMonomialOrder n ord, IsPolynomial poly) =>
  LeftModule Integer (PadPolyL n ord poly)

deriving instance
  (KnownNat n, IsMonomialOrder n ord, IsPolynomial poly) =>
  RightModule Integer (PadPolyL n ord poly)

deriving instance
  (KnownNat n, IsMonomialOrder n ord, IsPolynomial poly) =>
  Group (PadPolyL n ord poly)

deriving instance
  (KnownNat n, IsMonomialOrder n ord, IsPolynomial poly) =>
  Abelian (PadPolyL n ord poly)

deriving instance
  (KnownNat n, IsMonomialOrder n ord, IsPolynomial poly) =>
  Multiplicative (PadPolyL n ord poly)

deriving instance
  (KnownNat n, IsMonomialOrder n ord, IsPolynomial poly) =>
  Unital (PadPolyL n ord poly)

deriving instance
  (KnownNat n, IsMonomialOrder n ord, IsPolynomial poly) =>
  Commutative (PadPolyL n ord poly)

deriving instance
  (KnownNat n, IsMonomialOrder n ord, IsPolynomial poly) =>
  Eq (PadPolyL n ord poly)

deriving instance
  (KnownNat n, IsMonomialOrder n ord, IsPolynomial poly) =>
  Semiring (PadPolyL n ord poly)

deriving instance
  (KnownNat n, IsMonomialOrder n ord, IsPolynomial poly) =>
  Rig (PadPolyL n ord poly)

deriving instance
  (KnownNat n, IsMonomialOrder n ord, IsPolynomial poly) =>
  Ring (PadPolyL n ord poly)

deriving instance
  (KnownNat n, IsMonomialOrder n ord, IsPolynomial poly) =>
  DecidableZero (PadPolyL n ord poly)

instance
  ( KnownNat n
  , IsMonomialOrder n ord
  , IsPolynomial poly
  , LeftModule (Scalar r) poly
  ) =>
  LeftModule (Scalar r) (PadPolyL n ord poly)
  where
  Scalar r
r .* :: Scalar r -> PadPolyL n ord poly -> PadPolyL n ord poly
.* PadPolyL OrderedPolynomial poly (Graded ord) n
f = OrderedPolynomial poly (Graded ord) n -> PadPolyL n ord poly
forall (n :: Nat) ord poly.
OrderedPolynomial poly (Graded ord) n -> PadPolyL n ord poly
PadPolyL (OrderedPolynomial poly (Graded ord) n -> PadPolyL n ord poly)
-> OrderedPolynomial poly (Graded ord) n -> PadPolyL n ord poly
forall a b. (a -> b) -> a -> b
$ (Coefficient (OrderedPolynomial poly (Graded ord) n)
 -> Coefficient (OrderedPolynomial poly (Graded ord) n))
-> OrderedPolynomial poly (Graded ord) n
-> OrderedPolynomial poly (Graded ord) n
forall poly.
IsPolynomial poly =>
(Coefficient poly -> Coefficient poly) -> poly -> poly
mapCoeff' (Scalar r
r Scalar r -> poly -> poly
forall r m. LeftModule r m => r -> m -> m
.*) OrderedPolynomial poly (Graded ord) n
f
  {-# INLINE (.*) #-}

instance
  ( KnownNat n
  , IsMonomialOrder n ord
  , IsPolynomial poly
  , RightModule (Scalar r) poly
  ) =>
  RightModule (Scalar r) (PadPolyL n ord poly)
  where
  PadPolyL OrderedPolynomial poly (Graded ord) n
f *. :: PadPolyL n ord poly -> Scalar r -> PadPolyL n ord poly
*. Scalar r
r = OrderedPolynomial poly (Graded ord) n -> PadPolyL n ord poly
forall (n :: Nat) ord poly.
OrderedPolynomial poly (Graded ord) n -> PadPolyL n ord poly
PadPolyL (OrderedPolynomial poly (Graded ord) n -> PadPolyL n ord poly)
-> OrderedPolynomial poly (Graded ord) n -> PadPolyL n ord poly
forall a b. (a -> b) -> a -> b
$ (Coefficient (OrderedPolynomial poly (Graded ord) n)
 -> Coefficient (OrderedPolynomial poly (Graded ord) n))
-> OrderedPolynomial poly (Graded ord) n
-> OrderedPolynomial poly (Graded ord) n
forall poly.
IsPolynomial poly =>
(Coefficient poly -> Coefficient poly) -> poly -> poly
mapCoeff' (poly -> Scalar r -> poly
forall r m. RightModule r m => m -> r -> m
*. Scalar r
r) OrderedPolynomial poly (Graded ord) n
f
  {-# INLINE (*.) #-}

deriving instance
  (KnownNat n, IsMonomialOrder n ord, IsPolynomial poly) =>
  Num (PadPolyL n ord poly)

instance
  (KnownNat n, IsMonomialOrder n ord, IsPolynomial poly) =>
  IsPolynomial (PadPolyL n ord poly)
  where
  type Coefficient (PadPolyL n ord poly) = Coefficient poly
  type Arity (PadPolyL n ord poly) = n + Arity poly
  sArity :: proxy (PadPolyL n ord poly) -> SNat (Arity (PadPolyL n ord poly))
sArity proxy (PadPolyL n ord poly)
_ = SNat (Arity (PadPolyL n ord poly))
forall (n :: Nat). KnownNat n => SNat n
sNat
  liftMap :: (Ordinal (Arity (PadPolyL n ord poly)) -> alg)
-> PadPolyL n ord poly -> alg
liftMap Ordinal (Arity (PadPolyL n ord poly)) -> alg
f = Sized (Arity (PadPolyL n ord poly)) alg
-> PadPolyL n ord poly -> alg
forall poly alg.
(IsPolynomial poly, Ring alg, Commutative alg,
 Module (Scalar (Coefficient poly)) alg) =>
Sized (Arity poly) alg -> poly -> alg
subst (Sized (Arity (PadPolyL n ord poly)) alg
 -> PadPolyL n ord poly -> alg)
-> Sized (Arity (PadPolyL n ord poly)) alg
-> PadPolyL n ord poly
-> alg
forall a b. (a -> b) -> a -> b
$ SNat (n + Arity poly)
-> (Ordinal (n + Arity poly) -> alg)
-> Sized Vector (n + Arity poly) alg
forall (f :: * -> *) (n :: Nat) a.
(CFreeMonoid f, Dom f a) =>
SNat n -> (Ordinal n -> a) -> Sized f n a
S.generate SNat (n + Arity poly)
forall (n :: Nat). KnownNat n => SNat n
sNat Ordinal (n + Arity poly) -> alg
Ordinal (Arity (PadPolyL n ord poly)) -> alg
f
  subst :: Sized (Arity (PadPolyL n ord poly)) alg
-> PadPolyL n ord poly -> alg
subst Sized (Arity (PadPolyL n ord poly)) alg
vec (PadPolyL OrderedPolynomial poly (Graded ord) n
f) =
    let sn :: SNat n
sn = SNat n
forall (n :: Nat). KnownNat n => SNat n
sNat :: SNat n
     in IsTrue (n <=? (n + Arity poly))
-> (((n <=? (n + Arity poly)) ~ 'True) => alg) -> alg
forall (b :: Bool) r. IsTrue b -> ((b ~ 'True) => r) -> r
withWitness (SNat n -> SNat (Arity poly) -> IsTrue (n <=? (n + Arity poly))
forall (n :: Nat) (m :: Nat).
SNat n -> SNat m -> IsTrue (n <=? (n + m))
plusLeqL SNat n
sn (KnownNat (Arity poly) => SNat (Arity poly)
forall (n :: Nat). KnownNat n => SNat n
sNat @(Arity poly))) ((((n <=? (n + Arity poly)) ~ 'True) => alg) -> alg)
-> (((n <=? (n + Arity poly)) ~ 'True) => alg) -> alg
forall a b. (a -> b) -> a -> b
$
          case SNat n
-> Sized Vector (n + Arity poly) alg
-> (Sized Vector n alg, Sized Vector ((n + Arity poly) -. n) alg)
forall (n :: Nat) (f :: * -> *) (m :: Nat) a.
(CFreeMonoid f, Dom f a, n <= m) =>
SNat n -> Sized f m a -> (Sized f n a, Sized f (m -. n) a)
S.splitAt SNat n
sn Sized Vector (n + Arity poly) alg
Sized (Arity (PadPolyL n ord poly)) alg
vec of
            (Sized Vector n alg
ls, Sized Vector ((n + Arity poly) -. n) alg
rs) -> (Coefficient (OrderedPolynomial poly (Graded ord) n) -> alg -> alg)
-> Sized (Arity (OrderedPolynomial poly (Graded ord) n)) alg
-> OrderedPolynomial poly (Graded ord) n
-> alg
forall poly m.
(IsPolynomial poly, Ring m) =>
(Coefficient poly -> m -> m) -> Sized (Arity poly) m -> poly -> m
substWith (\Coefficient (OrderedPolynomial poly (Graded ord) n)
g alg
a -> alg
a alg -> alg -> alg
forall r. Multiplicative r => r -> r -> r
* Sized (Arity poly) alg -> poly -> alg
forall poly alg.
(IsPolynomial poly, Ring alg, Commutative alg,
 Module (Scalar (Coefficient poly)) alg) =>
Sized (Arity poly) alg -> poly -> alg
subst Sized (Arity poly) alg
Sized Vector ((n + Arity poly) -. n) alg
rs poly
Coefficient (OrderedPolynomial poly (Graded ord) n)
g) Sized Vector n alg
Sized (Arity (OrderedPolynomial poly (Graded ord) n)) alg
ls OrderedPolynomial poly (Graded ord) n
f
  injectCoeff :: Coefficient (PadPolyL n ord poly) -> PadPolyL n ord poly
injectCoeff = OrderedPolynomial poly (Graded ord) n -> PadPolyL n ord poly
forall (n :: Nat) ord poly.
OrderedPolynomial poly (Graded ord) n -> PadPolyL n ord poly
PadPolyL (OrderedPolynomial poly (Graded ord) n -> PadPolyL n ord poly)
-> (Coefficient poly -> OrderedPolynomial poly (Graded ord) n)
-> Coefficient poly
-> PadPolyL n ord poly
forall b c a. (b -> c) -> (a -> b) -> a -> c
. poly -> OrderedPolynomial poly (Graded ord) n
forall poly. IsPolynomial poly => Coefficient poly -> poly
injectCoeff (poly -> OrderedPolynomial poly (Graded ord) n)
-> (Coefficient poly -> poly)
-> Coefficient poly
-> OrderedPolynomial poly (Graded ord) n
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Coefficient poly -> poly
forall poly. IsPolynomial poly => Coefficient poly -> poly
injectCoeff
  fromMonomial :: Monomial (Arity (PadPolyL n ord poly)) -> PadPolyL n ord poly
fromMonomial Monomial (Arity (PadPolyL n ord poly))
m =
    let sn :: SNat n
sn = SNat n
forall (n :: Nat). KnownNat n => SNat n
sNat :: SNat n
     in IsTrue (n <=? (n + Arity poly))
-> (((n <=? (n + Arity poly)) ~ 'True) => PadPolyL n ord poly)
-> PadPolyL n ord poly
forall (b :: Bool) r. IsTrue b -> ((b ~ 'True) => r) -> r
withWitness (SNat n -> SNat (Arity poly) -> IsTrue (n <=? (n + Arity poly))
forall (n :: Nat) (m :: Nat).
SNat n -> SNat m -> IsTrue (n <=? (n + m))
plusLeqL SNat n
sn (KnownNat (Arity poly) => SNat (Arity poly)
forall (n :: Nat). KnownNat n => SNat n
sNat @(Arity poly))) ((((n <=? (n + Arity poly)) ~ 'True) => PadPolyL n ord poly)
 -> PadPolyL n ord poly)
-> (((n <=? (n + Arity poly)) ~ 'True) => PadPolyL n ord poly)
-> PadPolyL n ord poly
forall a b. (a -> b) -> a -> b
$
          case SNat n
-> Sized Vector (n + Arity poly) Int
-> (Sized Vector n Int, Sized Vector ((n + Arity poly) -. n) Int)
forall (n :: Nat) (f :: * -> *) (m :: Nat) a.
(CFreeMonoid f, Dom f a, n <= m) =>
SNat n -> Sized f m a -> (Sized f n a, Sized f (m -. n) a)
S.splitAt SNat n
sn Sized Vector (n + Arity poly) Int
Monomial (Arity (PadPolyL n ord poly))
m of
            (Sized Vector n Int
ls, Sized Vector ((n + Arity poly) -. n) Int
rs) -> OrderedPolynomial poly (Graded ord) n -> PadPolyL n ord poly
forall (n :: Nat) ord poly.
OrderedPolynomial poly (Graded ord) n -> PadPolyL n ord poly
PadPolyL (OrderedPolynomial poly (Graded ord) n -> PadPolyL n ord poly)
-> OrderedPolynomial poly (Graded ord) n -> PadPolyL n ord poly
forall a b. (a -> b) -> a -> b
$ Monomial (Arity (OrderedPolynomial poly (Graded ord) n))
-> OrderedPolynomial poly (Graded ord) n
forall poly. IsPolynomial poly => Monomial (Arity poly) -> poly
fromMonomial Sized Vector n Int
Monomial (Arity (OrderedPolynomial poly (Graded ord) n))
ls OrderedPolynomial poly (Graded ord) n
-> OrderedPolynomial poly (Graded ord) n
-> OrderedPolynomial poly (Graded ord) n
forall r. Multiplicative r => r -> r -> r
* Coefficient (OrderedPolynomial poly (Graded ord) n)
-> OrderedPolynomial poly (Graded ord) n
forall poly. IsPolynomial poly => Coefficient poly -> poly
injectCoeff (Monomial (Arity poly) -> poly
forall poly. IsPolynomial poly => Monomial (Arity poly) -> poly
fromMonomial Monomial (Arity poly)
Sized Vector ((n + Arity poly) -. n) Int
rs)
  terms' :: PadPolyL n ord poly
-> Map
     (Monomial (Arity (PadPolyL n ord poly)))
     (Coefficient (PadPolyL n ord poly))
terms' (PadPolyL OrderedPolynomial poly (Graded ord) n
m) =
    [(Sized Vector (n + Arity poly) Int, Coefficient poly)]
-> Map (Sized Vector (n + Arity poly) Int) (Coefficient poly)
forall k a. Ord k => [(k, a)] -> Map k a
M.fromList
      [ (Sized Vector n Int
ls Sized Vector n Int
-> Monomial (Arity poly) -> Sized Vector (n + Arity poly) Int
forall (f :: * -> *) (n :: Nat) (m :: Nat) a.
(CFreeMonoid f, Dom f a) =>
Sized f n a -> Sized f m a -> Sized f (n + m) a
S.++ Monomial (Arity poly)
rs, Coefficient poly
k)
      | (Sized Vector n Int
ls, poly
pol) <- Map (Sized Vector n Int) poly -> [(Sized Vector n Int, poly)]
forall k a. Map k a -> [(k, a)]
M.toList (Map (Sized Vector n Int) poly -> [(Sized Vector n Int, poly)])
-> Map (Sized Vector n Int) poly -> [(Sized Vector n Int, poly)]
forall a b. (a -> b) -> a -> b
$ OrderedPolynomial poly (Graded ord) n
-> Map
     (Monomial (Arity (OrderedPolynomial poly (Graded ord) n)))
     (Coefficient (OrderedPolynomial poly (Graded ord) n))
forall poly.
IsPolynomial poly =>
poly -> Map (Monomial (Arity poly)) (Coefficient poly)
terms' OrderedPolynomial poly (Graded ord) n
m
      , (Monomial (Arity poly)
rs, Coefficient poly
k) <- 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)
 -> [(Monomial (Arity poly), Coefficient poly)])
-> Map (Monomial (Arity poly)) (Coefficient poly)
-> [(Monomial (Arity poly), Coefficient poly)]
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
pol
      ]

instance
  (SingI (Replicate n 1), KnownNat n, IsMonomialOrder n ord, IsOrderedPolynomial poly) =>
  IsOrderedPolynomial (PadPolyL n ord poly)
  where
  type
    MOrder (PadPolyL n ord poly) =
      ProductOrder n (Arity poly) (Graded ord) (MOrder poly)
  leadingTerm :: PadPolyL n ord poly
-> (Coefficient (PadPolyL n ord poly),
    OrderedMonomial
      (MOrder (PadPolyL n ord poly)) (Arity (PadPolyL n ord poly)))
leadingTerm (PadPolyL OrderedPolynomial poly (Graded ord) n
f) =
    let (poly
p, OrderedMonomial Monomial n
ls) = OrderedPolynomial poly (Graded ord) n
-> (Coefficient (OrderedPolynomial poly (Graded ord) n),
    OrderedMonomial
      (MOrder (OrderedPolynomial poly (Graded ord) n))
      (Arity (OrderedPolynomial poly (Graded ord) n)))
forall poly.
IsOrderedPolynomial poly =>
poly
-> (Coefficient poly, OrderedMonomial (MOrder poly) (Arity poly))
leadingTerm OrderedPolynomial poly (Graded ord) n
f
        (Coefficient poly
k, OrderedMonomial Monomial (Arity poly)
rs) = 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
Coefficient (PadPolyL n ord poly)
k, Monomial (n + Arity poly)
-> OrderedMonomial
     (ProductOrder n (Arity poly) (Graded ord) (MOrder poly))
     (n + Arity poly)
forall k (ordering :: k) (n :: Nat).
Monomial n -> OrderedMonomial ordering n
OrderedMonomial (Monomial (n + Arity poly)
 -> OrderedMonomial
      (ProductOrder n (Arity poly) (Graded ord) (MOrder poly))
      (n + Arity poly))
-> Monomial (n + Arity poly)
-> OrderedMonomial
     (ProductOrder n (Arity poly) (Graded ord) (MOrder poly))
     (n + Arity poly)
forall a b. (a -> b) -> a -> b
$ Monomial n
ls Monomial n -> Monomial (Arity poly) -> Monomial (n + Arity poly)
forall (f :: * -> *) (n :: Nat) (m :: Nat) a.
(CFreeMonoid f, Dom f a) =>
Sized f n a -> Sized f m a -> Sized f (n + m) a
S.++ Monomial (Arity poly)
rs)

padLeftPoly ::
  (IsMonomialOrder n ord, IsPolynomial poly) =>
  SNat n ->
  ord ->
  poly ->
  PadPolyL n ord poly
padLeftPoly :: SNat n -> ord -> poly -> PadPolyL n ord poly
padLeftPoly SNat n
n ord
_ = SNat n
-> (KnownNat n => poly -> PadPolyL n ord poly)
-> poly
-> PadPolyL n ord poly
forall (n :: Nat) r. SNat n -> (KnownNat n => r) -> r
withKnownNat SNat n
n ((KnownNat n => poly -> PadPolyL n ord poly)
 -> poly -> PadPolyL n ord poly)
-> (KnownNat n => poly -> PadPolyL n ord poly)
-> poly
-> PadPolyL n ord poly
forall a b. (a -> b) -> a -> b
$ OrderedPolynomial poly (Graded ord) n -> PadPolyL n ord poly
forall (n :: Nat) ord poly.
OrderedPolynomial poly (Graded ord) n -> PadPolyL n ord poly
PadPolyL (OrderedPolynomial poly (Graded ord) n -> PadPolyL n ord poly)
-> (poly -> OrderedPolynomial poly (Graded ord) n)
-> poly
-> PadPolyL n ord poly
forall b c a. (b -> c) -> (a -> b) -> a -> c
. poly -> OrderedPolynomial poly (Graded ord) n
forall poly. IsPolynomial poly => Coefficient poly -> poly
injectCoeff

instance
  ( r ~ Coefficient poly
  , IsOrderedPolynomial poly
  , SingI (Replicate n 1)
  , KnownNat n
  , CoeffRing r
  , IsMonomialOrder n order
  , PrettyCoeff r
  ) =>
  Show (PadPolyL n order poly)
  where
  showsPrec :: Int -> PadPolyL n order poly -> ShowS
showsPrec = Sized (Arity (PadPolyL n order poly)) String
-> Int -> PadPolyL n order poly -> ShowS
forall poly.
(IsOrderedPolynomial poly, PrettyCoeff (Coefficient poly)) =>
Sized (Arity poly) String -> Int -> poly -> ShowS
showsPolynomialWith (Sized (Arity (PadPolyL n order poly)) String
 -> Int -> PadPolyL n order poly -> ShowS)
-> Sized (Arity (PadPolyL n order poly)) String
-> Int
-> PadPolyL n order poly
-> ShowS
forall a b. (a -> b) -> a -> b
$ SNat (n + Arity poly)
-> (Ordinal (n + Arity poly) -> String)
-> Sized Vector (n + Arity poly) String
forall (f :: * -> *) (n :: Nat) a.
(CFreeMonoid f, Dom f a) =>
SNat n -> (Ordinal n -> a) -> Sized f n a
generate SNat (n + Arity poly)
forall (n :: Nat). KnownNat n => SNat n
sNat (\Ordinal (n + Arity poly)
i -> String
"X_" String -> ShowS
forall w. Monoid w => w -> w -> w
++ Int -> String
forall a. Show a => a -> String
show (Ordinal (n + Arity poly) -> Int
forall a. Enum a => a -> Int
fromEnum Ordinal (n + Arity poly)
i))

mapOrderedPolynomial ::
  forall r r' n n' ord' ord.
  (KnownNat n, KnownNat n', CoeffRing r', IsMonomialOrder n' ord') =>
  (r -> r') ->
  (Ordinal n -> Ordinal n') ->
  OrderedPolynomial r ord n ->
  OrderedPolynomial r' ord' n'
mapOrderedPolynomial :: (r -> r')
-> (Ordinal n -> Ordinal n')
-> OrderedPolynomial r ord n
-> OrderedPolynomial r' ord' n'
mapOrderedPolynomial r -> r'
mapCoe Ordinal n -> Ordinal n'
mapVar (Polynomial Map (OrderedMonomial ord n) r
dic) =
  let toGenerator :: OrderedMonomial ord n -> OrderedMonomial ord' n'
toGenerator =
        Monomial n' -> OrderedMonomial ord' n'
forall k (ordering :: k) (n :: Nat).
Monomial n -> OrderedMonomial ordering n
OrderedMonomial
          (Monomial n' -> OrderedMonomial ord' n')
-> (OrderedMonomial ord n -> Monomial n')
-> OrderedMonomial ord n
-> OrderedMonomial ord' n'
forall b c a. (b -> c) -> (a -> b) -> a -> c
. SNat n' -> (Ordinal n' -> Int) -> Monomial n'
forall (f :: * -> *) (n :: Nat) a.
(CFreeMonoid f, Dom f a) =>
SNat n -> (Ordinal n -> a) -> Sized f n a
generate SNat n'
forall (n :: Nat). KnownNat n => SNat n
sNat
          ((Ordinal n' -> Int) -> Monomial n')
-> (OrderedMonomial ord n -> Ordinal n' -> Int)
-> OrderedMonomial ord n
-> Monomial n'
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Add Int -> Int
forall a. Add a -> a
runAdd (Add Int -> Int) -> (Ordinal n' -> Add Int) -> Ordinal n' -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
.)
          ((Ordinal n' -> Add Int) -> Ordinal n' -> Int)
-> (OrderedMonomial ord n -> Ordinal n' -> Add Int)
-> OrderedMonomial ord n
-> Ordinal n'
-> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Ordinal n -> Int -> Ordinal n' -> Add Int)
-> Monomial n -> Ordinal n' -> Add Int
forall (n :: Nat) m.
(KnownNat n, Monoid m) =>
(Ordinal n -> Int -> m) -> Monomial n -> m
ifoldMapMonom (\Ordinal n
o Int
l Ordinal n'
j -> Int -> Add Int
forall a. a -> Add a
Add (Int -> Add Int) -> Int -> Add Int
forall a b. (a -> b) -> a -> b
$ if Ordinal n'
j Ordinal n' -> Ordinal n' -> Bool
forall a. Eq a => a -> a -> Bool
== Ordinal n -> Ordinal n'
mapVar Ordinal n
o then Int
l else Int
0)
          (Monomial n -> Ordinal n' -> Add Int)
-> (OrderedMonomial ord n -> Monomial n)
-> OrderedMonomial ord n
-> Ordinal n'
-> Add Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. OrderedMonomial ord n -> Monomial n
forall k (ordering :: k) (n :: Nat).
OrderedMonomial ordering n -> Monomial n
getMonomial
   in Map (OrderedMonomial ord' n') r' -> OrderedPolynomial r' ord' n'
forall k r (order :: k) (n :: Nat).
Map (OrderedMonomial order n) r -> OrderedPolynomial r order n
Polynomial (Map (OrderedMonomial ord' n') r' -> OrderedPolynomial r' ord' n')
-> Map (OrderedMonomial ord' n') r' -> OrderedPolynomial r' ord' n'
forall a b. (a -> b) -> a -> b
$
        (OrderedMonomial ord n -> OrderedMonomial ord' n')
-> Map (OrderedMonomial ord n) r'
-> Map (OrderedMonomial ord' n') r'
forall k2 k1 a. Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a
M.mapKeys OrderedMonomial ord n -> OrderedMonomial ord' n'
toGenerator (Map (OrderedMonomial ord n) r'
 -> Map (OrderedMonomial ord' n') r')
-> Map (OrderedMonomial ord n) r'
-> Map (OrderedMonomial ord' n') r'
forall a b. (a -> b) -> a -> b
$
          (r -> Maybe r')
-> Map (OrderedMonomial ord n) r -> Map (OrderedMonomial ord n) r'
forall a b k. (a -> Maybe b) -> Map k a -> Map k b
M.mapMaybe (\r
i -> let c :: r'
c = r -> r'
mapCoe r
i in if r' -> Bool
forall r. DecidableZero r => r -> Bool
isZero r'
c then Maybe r'
forall a. Maybe a
Nothing else r' -> Maybe r'
forall a. a -> Maybe a
Just r'
c) Map (OrderedMonomial ord n) r
dic

-- Orphan Rules
{-# RULES
"convertPolynomial/OrderedPolynomial" [~2]
  convertPolynomial =
    id
"convertPolynomial'/OrderedPolynomial" [~2]
  convertPolynomial' =
    castPolynomial
"mapPolynomial/OrderedPolynomial" [~2] forall
  (mapC :: CoeffRing r' => r -> r')
  (mapV :: KnownNat n' => Ordinal n -> Ordinal n').
  mapPolynomial mapC mapV =
    mapOrderedPolynomial mapC mapV
  #-}