{-# LANGUAGE DeriveAnyClass               #-}
{-# LANGUAGE NoGeneralisedNewtypeDeriving #-}
{-# LANGUAGE TypeApplications             #-}
{-# LANGUAGE TypeOperators                #-}

module ZkFold.Base.Algebra.Polynomials.Multivariate.Polynomial
    ( Polynomial
    , Polynomial'
    , polynomial
    , PolynomialAny
    , PolynomialRepAny
    , PolynomialBoundedDegree
    , PolynomialRepBoundedDegree
    , mapCoeffs
    , var
    , evalPolynomial
    , mapVarPolynomial
    , variables
    ) where

import           Control.DeepSeq                                       (NFData)
import           Data.Aeson                                            (FromJSON, ToJSON)
import           Data.Bifunctor                                        (Bifunctor (..))
import           Data.Functor                                          ((<&>))
import           Data.List                                             (foldl', intercalate)
import           Data.Map.Strict                                       (Map, empty)
import           Data.Set                                              (Set, singleton)
import           GHC.Generics                                          (Generic)
import           GHC.IsList                                            (IsList (..))
import           Numeric.Natural                                       (Natural)
import           Prelude                                               hiding (Num (..), drop, lcm, length, sum, take,
                                                                        (!!), (/))
import           Test.QuickCheck                                       (Arbitrary (..))

import           ZkFold.Base.Algebra.Basic.Class
import           ZkFold.Base.Algebra.Basic.Sources
import           ZkFold.Base.Algebra.Polynomials.Multivariate.Monomial

-- | A class for polynomials.
-- `c` is the coefficient type,
-- `i` is the variable type,
-- `j` is the power type.
type Polynomial c i j = (Eq c, Field c, Monomial i j)

-- | Polynomial type
newtype P c i j m p = P p
    deriving ((forall x. P c i j m p -> Rep (P c i j m p) x)
-> (forall x. Rep (P c i j m p) x -> P c i j m p)
-> Generic (P c i j m p)
forall x. Rep (P c i j m p) x -> P c i j m p
forall x. P c i j m p -> Rep (P c i j m p) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall k (c :: k) k (i :: k) k (j :: k) k (m :: k) p x.
Rep (P c i j m p) x -> P c i j m p
forall k (c :: k) k (i :: k) k (j :: k) k (m :: k) p x.
P c i j m p -> Rep (P c i j m p) x
$cfrom :: forall k (c :: k) k (i :: k) k (j :: k) k (m :: k) p x.
P c i j m p -> Rep (P c i j m p) x
from :: forall x. P c i j m p -> Rep (P c i j m p) x
$cto :: forall k (c :: k) k (i :: k) k (j :: k) k (m :: k) p x.
Rep (P c i j m p) x -> P c i j m p
to :: forall x. Rep (P c i j m p) x -> P c i j m p
Generic, P c i j m p -> ()
(P c i j m p -> ()) -> NFData (P c i j m p)
forall a. (a -> ()) -> NFData a
forall k (c :: k) k (i :: k) k (j :: k) k (m :: k) p.
NFData p =>
P c i j m p -> ()
$crnf :: forall k (c :: k) k (i :: k) k (j :: k) k (m :: k) p.
NFData p =>
P c i j m p -> ()
rnf :: P c i j m p -> ()
NFData, Maybe (P c i j m p)
Value -> Parser [P c i j m p]
Value -> Parser (P c i j m p)
(Value -> Parser (P c i j m p))
-> (Value -> Parser [P c i j m p])
-> Maybe (P c i j m p)
-> FromJSON (P c i j m p)
forall a.
(Value -> Parser a)
-> (Value -> Parser [a]) -> Maybe a -> FromJSON a
forall k (c :: k) k (i :: k) k (j :: k) k (m :: k) p.
FromJSON p =>
Maybe (P c i j m p)
forall k (c :: k) k (i :: k) k (j :: k) k (m :: k) p.
FromJSON p =>
Value -> Parser [P c i j m p]
forall k (c :: k) k (i :: k) k (j :: k) k (m :: k) p.
FromJSON p =>
Value -> Parser (P c i j m p)
$cparseJSON :: forall k (c :: k) k (i :: k) k (j :: k) k (m :: k) p.
FromJSON p =>
Value -> Parser (P c i j m p)
parseJSON :: Value -> Parser (P c i j m p)
$cparseJSONList :: forall k (c :: k) k (i :: k) k (j :: k) k (m :: k) p.
FromJSON p =>
Value -> Parser [P c i j m p]
parseJSONList :: Value -> Parser [P c i j m p]
$comittedField :: forall k (c :: k) k (i :: k) k (j :: k) k (m :: k) p.
FromJSON p =>
Maybe (P c i j m p)
omittedField :: Maybe (P c i j m p)
FromJSON, [P c i j m p] -> Value
[P c i j m p] -> Encoding
P c i j m p -> Bool
P c i j m p -> Value
P c i j m p -> Encoding
(P c i j m p -> Value)
-> (P c i j m p -> Encoding)
-> ([P c i j m p] -> Value)
-> ([P c i j m p] -> Encoding)
-> (P c i j m p -> Bool)
-> ToJSON (P c i j m p)
forall a.
(a -> Value)
-> (a -> Encoding)
-> ([a] -> Value)
-> ([a] -> Encoding)
-> (a -> Bool)
-> ToJSON a
forall k (c :: k) k (i :: k) k (j :: k) k (m :: k) p.
ToJSON p =>
[P c i j m p] -> Value
forall k (c :: k) k (i :: k) k (j :: k) k (m :: k) p.
ToJSON p =>
[P c i j m p] -> Encoding
forall k (c :: k) k (i :: k) k (j :: k) k (m :: k) p.
ToJSON p =>
P c i j m p -> Bool
forall k (c :: k) k (i :: k) k (j :: k) k (m :: k) p.
ToJSON p =>
P c i j m p -> Value
forall k (c :: k) k (i :: k) k (j :: k) k (m :: k) p.
ToJSON p =>
P c i j m p -> Encoding
$ctoJSON :: forall k (c :: k) k (i :: k) k (j :: k) k (m :: k) p.
ToJSON p =>
P c i j m p -> Value
toJSON :: P c i j m p -> Value
$ctoEncoding :: forall k (c :: k) k (i :: k) k (j :: k) k (m :: k) p.
ToJSON p =>
P c i j m p -> Encoding
toEncoding :: P c i j m p -> Encoding
$ctoJSONList :: forall k (c :: k) k (i :: k) k (j :: k) k (m :: k) p.
ToJSON p =>
[P c i j m p] -> Value
toJSONList :: [P c i j m p] -> Value
$ctoEncodingList :: forall k (c :: k) k (i :: k) k (j :: k) k (m :: k) p.
ToJSON p =>
[P c i j m p] -> Encoding
toEncodingList :: [P c i j m p] -> Encoding
$comitField :: forall k (c :: k) k (i :: k) k (j :: k) k (m :: k) p.
ToJSON p =>
P c i j m p -> Bool
omitField :: P c i j m p -> Bool
ToJSON)

-- | Most general type for a multivariate polynomial
type Polynomial' c = P c Natural Natural (Map Natural Natural) [(c, Monomial')]

type PolynomialRepAny c = [(c, MonomialAny)]

type PolynomialRepBoundedDegree c i d = [(c, MonomialBoundedDegree i d)]

-- | Most general type for a multivariate polynomial, parameterized by the field of coefficients
type PolynomialAny c = P c Integer Integer MonomialRepAny (PolynomialRepAny c)

-- | Most general type for a multivariate polynomial with bounded degree,
-- parameterized by the field of coefficients, the type of variables, and the degree
type PolynomialBoundedDegree c i d = P c i Bool (MonomialRepBoundedDegree i d) (PolynomialRepBoundedDegree c i d)

-- | Polynomial constructor
polynomial ::
    Polynomial c i j =>
    [(c, M i j (Map i j))] ->
    P c i j (Map i j) [(c, M i j (Map i j))]
polynomial :: forall c i j.
Polynomial c i j =>
[(c, M i j (Map i j))] -> P c i j (Map i j) [(c, M i j (Map i j))]
polynomial = ((c, M i j (Map i j))
 -> P c i j (Map i j) [(c, M i j (Map i j))]
 -> P c i j (Map i j) [(c, M i j (Map i j))])
-> P c i j (Map i j) [(c, M i j (Map i j))]
-> [(c, M i j (Map i j))]
-> P c i j (Map i j) [(c, M i j (Map i j))]
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: Type -> Type) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (\(c
c, M i j (Map i j)
m) P c i j (Map i j) [(c, M i j (Map i j))]
x -> if c
c c -> c -> Bool
forall a. Eq a => a -> a -> Bool
== c
forall a. AdditiveMonoid a => a
zero then P c i j (Map i j) [(c, M i j (Map i j))]
x else [(c, M i j (Map i j))] -> P c i j (Map i j) [(c, M i j (Map i j))]
forall {k} {k} {k} {k} (c :: k) (i :: k) (j :: k) (m :: k) p.
p -> P c i j m p
P [(c
c, M i j (Map i j)
m)] P c i j (Map i j) [(c, M i j (Map i j))]
-> P c i j (Map i j) [(c, M i j (Map i j))]
-> P c i j (Map i j) [(c, M i j (Map i j))]
forall a. AdditiveSemigroup a => a -> a -> a
+ P c i j (Map i j) [(c, M i j (Map i j))]
x) P c i j (Map i j) [(c, M i j (Map i j))]
forall a. AdditiveMonoid a => a
zero

instance (Ord i, Eq c, Field c, Ord j, Semiring j) => IsList (P c i j (Map i j) [(c, M i j (Map i j))]) where
    type Item (P c i j (Map i j) [(c, M i j (Map i j))]) = (c, Map i j)
    toList :: P c i j (Map i j) [(c, M i j (Map i j))]
-> [Item (P c i j (Map i j) [(c, M i j (Map i j))])]
toList (P [(c, M i j (Map i j))]
p) = (M i j (Map i j) -> Map i j)
-> (c, M i j (Map i j)) -> (c, Map i j)
forall b c a. (b -> c) -> (a, b) -> (a, c)
forall (p :: Type -> Type -> Type) b c a.
Bifunctor p =>
(b -> c) -> p a b -> p a c
second (\(M Map i j
m) -> Map i j
m) ((c, M i j (Map i j)) -> (c, Map i j))
-> [(c, M i j (Map i j))] -> [(c, Map i j)]
forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> [(c, M i j (Map i j))]
p
    fromList :: [Item (P c i j (Map i j) [(c, M i j (Map i j))])]
-> P c i j (Map i j) [(c, M i j (Map i j))]
fromList [Item (P c i j (Map i j) [(c, M i j (Map i j))])]
p = [(c, M i j (Map i j))] -> P c i j (Map i j) [(c, M i j (Map i j))]
forall c i j.
Polynomial c i j =>
[(c, M i j (Map i j))] -> P c i j (Map i j) [(c, M i j (Map i j))]
polynomial ([(c, M i j (Map i j))]
 -> P c i j (Map i j) [(c, M i j (Map i j))])
-> [(c, M i j (Map i j))]
-> P c i j (Map i j) [(c, M i j (Map i j))]
forall a b. (a -> b) -> a -> b
$ (Map i j -> M i j (Map i j))
-> (c, Map i j) -> (c, M i j (Map i j))
forall b c a. (b -> c) -> (a, b) -> (a, c)
forall (p :: Type -> Type -> Type) b c a.
Bifunctor p =>
(b -> c) -> p a b -> p a c
second Map i j -> M i j (Map i j)
forall i j. Monomial i j => Map i j -> M i j (Map i j)
monomial ((c, Map i j) -> (c, M i j (Map i j)))
-> [(c, Map i j)] -> [(c, M i j (Map i j))]
forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> [(c, Map i j)]
[Item (P c i j (Map i j) [(c, M i j (Map i j))])]
p

instance (Show c, Show i, Show j, Monomial i j) => Show (P c i j (Map i j) [(c, M i j (Map i j))]) where
    show :: P c i j (Map i j) [(c, M i j (Map i j))] -> String
show (P [(c, M i j (Map i j))]
p) = String -> [String] -> String
forall a. [a] -> [[a]] -> [a]
intercalate String
" + "
        ([String] -> String) -> [String] -> String
forall a b. (a -> b) -> a -> b
$ [(c, M i j (Map i j))]
p [(c, M i j (Map i j))]
-> ((c, M i j (Map i j)) -> String) -> [String]
forall (f :: Type -> Type) a b. Functor f => f a -> (a -> b) -> f b
<&> \(c
c, M i j (Map i j)
m) -> c -> String
forall a. Show a => a -> String
show c
c String -> ShowS
forall a. Semigroup a => a -> a -> a
<> String
"∙" String -> ShowS
forall a. Semigroup a => a -> a -> a
<> M i j (Map i j) -> String
forall a. Show a => a -> String
show (M i j (Map i j)
m :: M i j (Map i j))

instance (Eq i, Eq j, Eq c, Eq (Map i j)) => Eq (P c i j m [(c, M i j (Map i j))]) where
    P [(c, M i j (Map i j))]
l == :: P c i j m [(c, M i j (Map i j))]
-> P c i j m [(c, M i j (Map i j))] -> Bool
== P [(c, M i j (Map i j))]
r = [(c, M i j (Map i j))]
l [(c, M i j (Map i j))] -> [(c, M i j (Map i j))] -> Bool
forall a. Eq a => a -> a -> Bool
== [(c, M i j (Map i j))]
r

-- TODO: this assumes sorted monomials! Needs fixing.
instance (Eq i, Eq j, Eq c, Ord (M i j (Map i j))) => Ord (P c i j m [(c, M i j (Map i j))]) where
    compare :: P c i j m [(c, M i j (Map i j))]
-> P c i j m [(c, M i j (Map i j))] -> Ordering
compare (P [(c, M i j (Map i j))]
l) (P [(c, M i j (Map i j))]
r) = [M i j (Map i j)] -> [M i j (Map i j)] -> Ordering
forall a. Ord a => a -> a -> Ordering
compare
        ((c, M i j (Map i j)) -> M i j (Map i j)
forall a b. (a, b) -> b
snd ((c, M i j (Map i j)) -> M i j (Map i j))
-> [(c, M i j (Map i j))] -> [M i j (Map i j)]
forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> [(c, M i j (Map i j))]
l)
        ((c, M i j (Map i j)) -> M i j (Map i j)
forall a b. (a, b) -> b
snd ((c, M i j (Map i j)) -> M i j (Map i j))
-> [(c, M i j (Map i j))] -> [M i j (Map i j)]
forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> [(c, M i j (Map i j))]
r)

instance (Arbitrary c, Arbitrary m) => Arbitrary (P c i j m [(c, M i j m)]) where
    arbitrary :: Gen (P c i j m [(c, M i j m)])
arbitrary = [(c, M i j m)] -> P c i j m [(c, M i j m)]
forall {k} {k} {k} {k} (c :: k) (i :: k) (j :: k) (m :: k) p.
p -> P c i j m p
P ([(c, M i j m)] -> P c i j m [(c, M i j m)])
-> Gen [(c, M i j m)] -> Gen (P c i j m [(c, M i j m)])
forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> Gen [(c, M i j m)]
forall a. Arbitrary a => Gen a
arbitrary

{-
    In general, `P c i j m p` may define a set of polynomials that is not necessarily a ring.
    Arithmetic operations are defined for a more concrete type below.
-}

instance Polynomial c i j => AdditiveSemigroup (P c i j (Map i j) [(c, M i j (Map i j))]) where
    P [(c, M i j (Map i j))]
l + :: P c i j (Map i j) [(c, M i j (Map i j))]
-> P c i j (Map i j) [(c, M i j (Map i j))]
-> P c i j (Map i j) [(c, M i j (Map i j))]
+ P [(c, M i j (Map i j))]
r = [(c, M i j (Map i j))] -> P c i j (Map i j) [(c, M i j (Map i j))]
forall {k} {k} {k} {k} (c :: k) (i :: k) (j :: k) (m :: k) p.
p -> P c i j m p
P ([(c, M i j (Map i j))]
 -> P c i j (Map i j) [(c, M i j (Map i j))])
-> [(c, M i j (Map i j))]
-> P c i j (Map i j) [(c, M i j (Map i j))]
forall a b. (a -> b) -> a -> b
$ [(c, M i j (Map i j))]
-> [(c, M i j (Map i j))] -> [(c, M i j (Map i j))]
forall {a} {a}.
(Eq a, AdditiveMonoid a, Ord a) =>
[(a, a)] -> [(a, a)] -> [(a, a)]
go [(c, M i j (Map i j))]
l [(c, M i j (Map i j))]
r
        where
            go :: [(a, a)] -> [(a, a)] -> [(a, a)]
go [] [] = []
            go [(a, a)]
ls [] = [(a, a)]
ls
            go [] [(a, a)]
rs = [(a, a)]
rs
            go ((a
cl, a
ml):[(a, a)]
ls) ((a
cr, a
mr):[(a, a)]
rs)
                | a
ml a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
mr =
                    if a
cl a -> a -> a
forall a. AdditiveSemigroup a => a -> a -> a
+ a
cr a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
forall a. AdditiveMonoid a => a
zero
                        then [(a, a)] -> [(a, a)] -> [(a, a)]
go [(a, a)]
ls [(a, a)]
rs
                        else (a
cl a -> a -> a
forall a. AdditiveSemigroup a => a -> a -> a
+ a
cr, a
ml) (a, a) -> [(a, a)] -> [(a, a)]
forall a. a -> [a] -> [a]
: [(a, a)] -> [(a, a)] -> [(a, a)]
go [(a, a)]
ls [(a, a)]
rs
                | a
ml a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
mr   = (a
cl, a
ml) (a, a) -> [(a, a)] -> [(a, a)]
forall a. a -> [a] -> [a]
: [(a, a)] -> [(a, a)] -> [(a, a)]
go [(a, a)]
ls ((a
cr, a
mr)(a, a) -> [(a, a)] -> [(a, a)]
forall a. a -> [a] -> [a]
:[(a, a)]
rs)
                | Bool
otherwise = (a
cr, a
mr) (a, a) -> [(a, a)] -> [(a, a)]
forall a. a -> [a] -> [a]
: [(a, a)] -> [(a, a)] -> [(a, a)]
go ((a
cl, a
ml)(a, a) -> [(a, a)] -> [(a, a)]
forall a. a -> [a] -> [a]
:[(a, a)]
ls) [(a, a)]
rs

instance Scale c' c => Scale c' (P c i j (Map i j) [(c, M i j (Map i j))]) where
    scale :: c'
-> P c i j (Map i j) [(c, M i j (Map i j))]
-> P c i j (Map i j) [(c, M i j (Map i j))]
scale c'
c' (P [(c, M i j (Map i j))]
p) = [(c, M i j (Map i j))] -> P c i j (Map i j) [(c, M i j (Map i j))]
forall {k} {k} {k} {k} (c :: k) (i :: k) (j :: k) (m :: k) p.
p -> P c i j m p
P ([(c, M i j (Map i j))]
 -> P c i j (Map i j) [(c, M i j (Map i j))])
-> [(c, M i j (Map i j))]
-> P c i j (Map i j) [(c, M i j (Map i j))]
forall a b. (a -> b) -> a -> b
$ ((c, M i j (Map i j)) -> (c, M i j (Map i j)))
-> [(c, M i j (Map i j))] -> [(c, M i j (Map i j))]
forall a b. (a -> b) -> [a] -> [b]
map ((c -> c) -> (c, M i j (Map i j)) -> (c, M i j (Map i j))
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: Type -> Type -> Type) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first (c' -> c -> c
forall b a. Scale b a => b -> a -> a
scale c'
c')) [(c, M i j (Map i j))]
p

instance Polynomial c i j => AdditiveMonoid (P c i j (Map i j) [(c, M i j (Map i j))]) where
    zero :: P c i j (Map i j) [(c, M i j (Map i j))]
zero = [(c, M i j (Map i j))] -> P c i j (Map i j) [(c, M i j (Map i j))]
forall {k} {k} {k} {k} (c :: k) (i :: k) (j :: k) (m :: k) p.
p -> P c i j m p
P []

instance Polynomial c i j => AdditiveGroup (P c i j (Map i j) [(c, M i j (Map i j))]) where
    negate :: P c i j (Map i j) [(c, M i j (Map i j))]
-> P c i j (Map i j) [(c, M i j (Map i j))]
negate (P [(c, M i j (Map i j))]
p) = [(c, M i j (Map i j))] -> P c i j (Map i j) [(c, M i j (Map i j))]
forall {k} {k} {k} {k} (c :: k) (i :: k) (j :: k) (m :: k) p.
p -> P c i j m p
P ([(c, M i j (Map i j))]
 -> P c i j (Map i j) [(c, M i j (Map i j))])
-> [(c, M i j (Map i j))]
-> P c i j (Map i j) [(c, M i j (Map i j))]
forall a b. (a -> b) -> a -> b
$ ((c, M i j (Map i j)) -> (c, M i j (Map i j)))
-> [(c, M i j (Map i j))] -> [(c, M i j (Map i j))]
forall a b. (a -> b) -> [a] -> [b]
map ((c -> c) -> (c, M i j (Map i j)) -> (c, M i j (Map i j))
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: Type -> Type -> Type) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first c -> c
forall a. AdditiveGroup a => a -> a
negate) [(c, M i j (Map i j))]
p

instance Polynomial c i j => MultiplicativeSemigroup (P c i j (Map i j) [(c, M i j (Map i j))]) where
    P [(c, M i j (Map i j))]
l * :: P c i j (Map i j) [(c, M i j (Map i j))]
-> P c i j (Map i j) [(c, M i j (Map i j))]
-> P c i j (Map i j) [(c, M i j (Map i j))]
* P c i j (Map i j) [(c, M i j (Map i j))]
r = (P c i j (Map i j) [(c, M i j (Map i j))]
 -> P c i j (Map i j) [(c, M i j (Map i j))]
 -> P c i j (Map i j) [(c, M i j (Map i j))])
-> P c i j (Map i j) [(c, M i j (Map i j))]
-> [P c i j (Map i j) [(c, M i j (Map i j))]]
-> P c i j (Map i j) [(c, M i j (Map i j))]
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: Type -> Type) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' P c i j (Map i j) [(c, M i j (Map i j))]
-> P c i j (Map i j) [(c, M i j (Map i j))]
-> P c i j (Map i j) [(c, M i j (Map i j))]
forall a. AdditiveSemigroup a => a -> a -> a
(+) ([(c, M i j (Map i j))] -> P c i j (Map i j) [(c, M i j (Map i j))]
forall {k} {k} {k} {k} (c :: k) (i :: k) (j :: k) (m :: k) p.
p -> P c i j m p
P []) ([P c i j (Map i j) [(c, M i j (Map i j))]]
 -> P c i j (Map i j) [(c, M i j (Map i j))])
-> [P c i j (Map i j) [(c, M i j (Map i j))]]
-> P c i j (Map i j) [(c, M i j (Map i j))]
forall a b. (a -> b) -> a -> b
$ ((c, M i j (Map i j)) -> P c i j (Map i j) [(c, M i j (Map i j))])
-> [(c, M i j (Map i j))]
-> [P c i j (Map i j) [(c, M i j (Map i j))]]
forall a b. (a -> b) -> [a] -> [b]
map (P c i j (Map i j) [(c, M i j (Map i j))]
-> (c, M i j (Map i j)) -> P c i j (Map i j) [(c, M i j (Map i j))]
forall {k} {k} {k} {k} {k} {k} {k} {k} {p :: Type -> Type -> Type}
       {b} {d} {c :: k} {i :: k} {j :: k} {m :: k} {c :: k} {i :: k}
       {j :: k} {m :: k}.
(Bifunctor p, MultiplicativeSemigroup b,
 MultiplicativeSemigroup d) =>
P c i j m [p b d] -> (b, d) -> P c i j m [p b d]
f P c i j (Map i j) [(c, M i j (Map i j))]
r) [(c, M i j (Map i j))]
l
        where f :: P c i j m [p b d] -> (b, d) -> P c i j m [p b d]
f (P [p b d]
p) (b
c, d
m) = [p b d] -> P c i j m [p b d]
forall {k} {k} {k} {k} (c :: k) (i :: k) (j :: k) (m :: k) p.
p -> P c i j m p
P ([p b d] -> P c i j m [p b d]) -> [p b d] -> P c i j m [p b d]
forall a b. (a -> b) -> a -> b
$ (p b d -> p b d) -> [p b d] -> [p b d]
forall a b. (a -> b) -> [a] -> [b]
map ((b -> b) -> (d -> d) -> p b d -> p b d
forall a b c d. (a -> b) -> (c -> d) -> p a c -> p b d
forall (p :: Type -> Type -> Type) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap (b -> b -> b
forall a. MultiplicativeSemigroup a => a -> a -> a
* b
c) (d -> d -> d
forall a. MultiplicativeSemigroup a => a -> a -> a
* d
m)) [p b d]
p

instance Polynomial c i j => Exponent (P c i j (Map i j) [(c, M i j (Map i j))]) Natural where
    ^ :: P c i j (Map i j) [(c, M i j (Map i j))]
-> Natural -> P c i j (Map i j) [(c, M i j (Map i j))]
(^) = P c i j (Map i j) [(c, M i j (Map i j))]
-> Natural -> P c i j (Map i j) [(c, M i j (Map i j))]
forall a. MultiplicativeMonoid a => a -> Natural -> a
natPow

instance Polynomial c i j => MultiplicativeMonoid (P c i j (Map i j) [(c, M i j (Map i j))]) where
    one :: P c i j (Map i j) [(c, M i j (Map i j))]
one = [(c, M i j (Map i j))] -> P c i j (Map i j) [(c, M i j (Map i j))]
forall {k} {k} {k} {k} (c :: k) (i :: k) (j :: k) (m :: k) p.
p -> P c i j m p
P [(c
forall a. MultiplicativeMonoid a => a
one, Map i j -> M i j (Map i j)
forall {k} {k1} (i :: k) (j :: k1) m. m -> M i j m
M Map i j
forall k a. Map k a
empty)]

instance FromConstant c' c => FromConstant c' (P c i j (Map i j) [(c, M i j (Map i j))]) where
    fromConstant :: c' -> P c i j (Map i j) [(c, M i j (Map i j))]
fromConstant c'
x = [(c, M i j (Map i j))] -> P c i j (Map i j) [(c, M i j (Map i j))]
forall {k} {k} {k} {k} (c :: k) (i :: k) (j :: k) (m :: k) p.
p -> P c i j m p
P [(c' -> c
forall a b. FromConstant a b => a -> b
fromConstant c'
x, Map i j -> M i j (Map i j)
forall {k} {k1} (i :: k) (j :: k1) m. m -> M i j m
M Map i j
forall k a. Map k a
empty)]

instance Polynomial c i j => Semiring (P c i j (Map i j) [(c, M i j (Map i j))])

instance Polynomial c i j => Ring (P c i j (Map i j) [(c, M i j (Map i j))])

-- | @'var' i@ is a polynomial \(p(x) = x_i\)
var :: Polynomial c i j => i -> P c i j (Map i j) [(c, M i j (Map i j))]
var :: forall c i j.
Polynomial c i j =>
i -> P c i j (Map i j) [(c, M i j (Map i j))]
var i
x = [(c, M i j (Map i j))] -> P c i j (Map i j) [(c, M i j (Map i j))]
forall c i j.
Polynomial c i j =>
[(c, M i j (Map i j))] -> P c i j (Map i j) [(c, M i j (Map i j))]
polynomial [(c
forall a. MultiplicativeMonoid a => a
one, Map i j -> M i j (Map i j)
forall i j. Monomial i j => Map i j -> M i j (Map i j)
monomial (Map i j -> M i j (Map i j)) -> Map i j -> M i j (Map i j)
forall a b. (a -> b) -> a -> b
$ [Item (Map i j)] -> Map i j
forall l. IsList l => [Item l] -> l
fromList [(i
x, j
forall a. MultiplicativeMonoid a => a
one)])]

evalPolynomial :: forall c i j b m .
    Algebra c b =>
    ((i -> b) -> M i j m -> b) -> (i -> b) -> P c i j m [(c, M i j m)] -> b
evalPolynomial :: forall {k1} c i (j :: k1) b m.
Algebra c b =>
((i -> b) -> M i j m -> b)
-> (i -> b) -> P c i j m [(c, M i j m)] -> b
evalPolynomial (i -> b) -> M i j m -> b
e i -> b
f (P [(c, M i j m)]
p) = ((c, M i j m) -> b -> b) -> b -> [(c, M i j m)] -> b
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: Type -> Type) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (\(c
c, M i j m
m) b
x -> b
x b -> b -> b
forall a. AdditiveSemigroup a => a -> a -> a
+ c -> b -> b
forall b a. Scale b a => b -> a -> a
scale c
c ((i -> b) -> M i j m -> b
e i -> b
f M i j m
m)) b
forall a. AdditiveMonoid a => a
zero [(c, M i j m)]
p

variables :: forall c .
    MultiplicativeMonoid c =>
    Polynomial' c -> Set Natural
variables :: forall c. MultiplicativeMonoid c => Polynomial' c -> Set Natural
variables = Sources c Natural -> Set Natural
forall {k} (a :: k) i. Sources a i -> Set i
runSources (Sources c Natural -> Set Natural)
-> (Polynomial' c -> Sources c Natural)
-> Polynomial' c
-> Set Natural
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Natural -> Sources c Natural)
 -> M Natural Natural (Map Natural Natural) -> Sources c Natural)
-> (Natural -> Sources c Natural)
-> Polynomial' c
-> Sources c Natural
forall {k1} c i (j :: k1) b m.
Algebra c b =>
((i -> b) -> M i j m -> b)
-> (i -> b) -> P c i j m [(c, M i j m)] -> b
evalPolynomial (Natural -> Sources c Natural)
-> M Natural Natural (Map Natural Natural) -> Sources c Natural
forall i j b.
(MultiplicativeMonoid b, Exponent b j) =>
(i -> b) -> M i j (Map i j) -> b
evalMapM (forall {k} (a :: k) i. Set i -> Sources a i
forall a i. Set i -> Sources a i
Sources @c (Set Natural -> Sources c Natural)
-> (Natural -> Set Natural) -> Natural -> Sources c Natural
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Natural -> Set Natural
forall a. a -> Set a
singleton)

mapCoeffs :: forall c c' i j .
    (c -> c')
    -> P c i j (Map i j) [(c, M i j (Map i j))]
    -> P c' i j (Map i j) [(c', M i j (Map i j))]
mapCoeffs :: forall c c' i j.
(c -> c')
-> P c i j (Map i j) [(c, M i j (Map i j))]
-> P c' i j (Map i j) [(c', M i j (Map i j))]
mapCoeffs c -> c'
f (P [(c, M i j (Map i j))]
p) = [(c', M i j (Map i j))]
-> P c' i j (Map i j) [(c', M i j (Map i j))]
forall {k} {k} {k} {k} (c :: k) (i :: k) (j :: k) (m :: k) p.
p -> P c i j m p
P ([(c', M i j (Map i j))]
 -> P c' i j (Map i j) [(c', M i j (Map i j))])
-> [(c', M i j (Map i j))]
-> P c' i j (Map i j) [(c', M i j (Map i j))]
forall a b. (a -> b) -> a -> b
$ [(c, M i j (Map i j))]
p [(c, M i j (Map i j))]
-> ((c, M i j (Map i j)) -> (c', M i j (Map i j)))
-> [(c', M i j (Map i j))]
forall (f :: Type -> Type) a b. Functor f => f a -> (a -> b) -> f b
<&> (c -> c') -> (c, M i j (Map i j)) -> (c', M i j (Map i j))
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: Type -> Type -> Type) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first c -> c'
f

mapVarPolynomial :: [Natural] -> Polynomial' c -> Polynomial' c
mapVarPolynomial :: forall c. [Natural] -> Polynomial' c -> Polynomial' c
mapVarPolynomial [Natural]
vars (P [(c, M Natural Natural (Map Natural Natural))]
ms) = [(c, M Natural Natural (Map Natural Natural))]
-> P c
     Natural
     Natural
     (Map Natural Natural)
     [(c, M Natural Natural (Map Natural Natural))]
forall {k} {k} {k} {k} (c :: k) (i :: k) (j :: k) (m :: k) p.
p -> P c i j m p
P ([(c, M Natural Natural (Map Natural Natural))]
 -> P c
      Natural
      Natural
      (Map Natural Natural)
      [(c, M Natural Natural (Map Natural Natural))])
-> [(c, M Natural Natural (Map Natural Natural))]
-> P c
     Natural
     Natural
     (Map Natural Natural)
     [(c, M Natural Natural (Map Natural Natural))]
forall a b. (a -> b) -> a -> b
$ (M Natural Natural (Map Natural Natural)
 -> M Natural Natural (Map Natural Natural))
-> (c, M Natural Natural (Map Natural Natural))
-> (c, M Natural Natural (Map Natural Natural))
forall b c a. (b -> c) -> (a, b) -> (a, c)
forall (p :: Type -> Type -> Type) b c a.
Bifunctor p =>
(b -> c) -> p a b -> p a c
second ([Natural]
-> M Natural Natural (Map Natural Natural)
-> M Natural Natural (Map Natural Natural)
mapVarMonomial [Natural]
vars) ((c, M Natural Natural (Map Natural Natural))
 -> (c, M Natural Natural (Map Natural Natural)))
-> [(c, M Natural Natural (Map Natural Natural))]
-> [(c, M Natural Natural (Map Natural Natural))]
forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> [(c, M Natural Natural (Map Natural Natural))]
ms