{-# LANGUAGE DeriveAnyClass               #-}
{-# LANGUAGE NoGeneralisedNewtypeDeriving #-}

module ZkFold.Base.Algebra.Polynomials.Multivariate.Polynomial 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, keysSet)
import qualified Data.Map.Strict                                       as M
import           Data.Set                                              (Set)
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.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 Poly c i j = P [(c, Mono i j)]
    deriving ((forall x. Poly c i j -> Rep (Poly c i j) x)
-> (forall x. Rep (Poly c i j) x -> Poly c i j)
-> Generic (Poly c i j)
forall x. Rep (Poly c i j) x -> Poly c i j
forall x. Poly c i j -> Rep (Poly c i j) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall c i j x. Rep (Poly c i j) x -> Poly c i j
forall c i j x. Poly c i j -> Rep (Poly c i j) x
$cfrom :: forall c i j x. Poly c i j -> Rep (Poly c i j) x
from :: forall x. Poly c i j -> Rep (Poly c i j) x
$cto :: forall c i j x. Rep (Poly c i j) x -> Poly c i j
to :: forall x. Rep (Poly c i j) x -> Poly c i j
Generic, Poly c i j -> ()
(Poly c i j -> ()) -> NFData (Poly c i j)
forall a. (a -> ()) -> NFData a
forall c i j. (NFData c, NFData i, NFData j) => Poly c i j -> ()
$crnf :: forall c i j. (NFData c, NFData i, NFData j) => Poly c i j -> ()
rnf :: Poly c i j -> ()
NFData, Value -> Parser [Poly c i j]
Value -> Parser (Poly c i j)
(Value -> Parser (Poly c i j))
-> (Value -> Parser [Poly c i j]) -> FromJSON (Poly c i j)
forall a.
(Value -> Parser a) -> (Value -> Parser [a]) -> FromJSON a
forall c i j.
(FromJSONKey i, Ord i, FromJSON c, FromJSON j) =>
Value -> Parser [Poly c i j]
forall c i j.
(FromJSONKey i, Ord i, FromJSON c, FromJSON j) =>
Value -> Parser (Poly c i j)
$cparseJSON :: forall c i j.
(FromJSONKey i, Ord i, FromJSON c, FromJSON j) =>
Value -> Parser (Poly c i j)
parseJSON :: Value -> Parser (Poly c i j)
$cparseJSONList :: forall c i j.
(FromJSONKey i, Ord i, FromJSON c, FromJSON j) =>
Value -> Parser [Poly c i j]
parseJSONList :: Value -> Parser [Poly c i j]
FromJSON, [Poly c i j] -> Value
[Poly c i j] -> Encoding
Poly c i j -> Value
Poly c i j -> Encoding
(Poly c i j -> Value)
-> (Poly c i j -> Encoding)
-> ([Poly c i j] -> Value)
-> ([Poly c i j] -> Encoding)
-> ToJSON (Poly c i j)
forall a.
(a -> Value)
-> (a -> Encoding)
-> ([a] -> Value)
-> ([a] -> Encoding)
-> ToJSON a
forall c i j.
(ToJSON c, ToJSON j, ToJSONKey i) =>
[Poly c i j] -> Value
forall c i j.
(ToJSON c, ToJSON j, ToJSONKey i) =>
[Poly c i j] -> Encoding
forall c i j.
(ToJSON c, ToJSON j, ToJSONKey i) =>
Poly c i j -> Value
forall c i j.
(ToJSON c, ToJSON j, ToJSONKey i) =>
Poly c i j -> Encoding
$ctoJSON :: forall c i j.
(ToJSON c, ToJSON j, ToJSONKey i) =>
Poly c i j -> Value
toJSON :: Poly c i j -> Value
$ctoEncoding :: forall c i j.
(ToJSON c, ToJSON j, ToJSONKey i) =>
Poly c i j -> Encoding
toEncoding :: Poly c i j -> Encoding
$ctoJSONList :: forall c i j.
(ToJSON c, ToJSON j, ToJSONKey i) =>
[Poly c i j] -> Value
toJSONList :: [Poly c i j] -> Value
$ctoEncodingList :: forall c i j.
(ToJSON c, ToJSON j, ToJSONKey i) =>
[Poly c i j] -> Encoding
toEncodingList :: [Poly c i j] -> Encoding
ToJSON)

---------------------------------- List-based polynomials with map-based monomials ----------------------------------

-- | Polynomial constructor
polynomial :: Polynomial c i j => [(c, Mono i j)] -> Poly c i j
polynomial :: forall c i j. Polynomial c i j => [(c, Mono i j)] -> Poly c i j
polynomial = ((c, Mono i j) -> Poly c i j -> Poly c i j)
-> Poly c i j -> [(c, Mono i j)] -> Poly c 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, Mono i j
m) Poly c i j
x -> if c
c c -> c -> Bool
forall a. Eq a => a -> a -> Bool
== c
forall a. AdditiveMonoid a => a
zero then Poly c i j
x else [(c, Mono i j)] -> Poly c i j
forall c i j. [(c, Mono i j)] -> Poly c i j
P [(c
c, Mono i j
m)] Poly c i j -> Poly c i j -> Poly c i j
forall a. AdditiveSemigroup a => a -> a -> a
+ Poly c i j
x) Poly c i j
forall a. AdditiveMonoid a => a
zero

evalPolynomial
    :: forall c i j b
     . AdditiveMonoid b
    => Scale c b
    => ((i -> b) -> Mono i j -> b)
    -> (i -> b)
    -> Poly c i j
    -> b
evalPolynomial :: forall c i j b.
(AdditiveMonoid b, Scale c b) =>
((i -> b) -> Mono i j -> b) -> (i -> b) -> Poly c i j -> b
evalPolynomial (i -> b) -> Mono i j -> b
e i -> b
f (P [(c, Mono i j)]
p) = ((c, Mono i j) -> b -> b) -> b -> [(c, Mono i j)] -> 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, Mono i j
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) -> Mono i j -> b
e i -> b
f Mono i j
m)) b
forall a. AdditiveMonoid a => a
zero [(c, Mono i j)]
p

variables :: forall c v . Ord v => Poly c v Natural -> Set v
variables :: forall c v. Ord v => Poly c v Natural -> Set v
variables (P [(c, Mono v Natural)]
p) = ((c, Mono v Natural) -> Set v) -> [(c, Mono v Natural)] -> Set v
forall m a. Monoid m => (a -> m) -> [a] -> m
forall (t :: Type -> Type) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap ((\(M Map v Natural
m) -> Map v Natural -> Set v
forall k a. Map k a -> Set k
keysSet Map v Natural
m) (Mono v Natural -> Set v)
-> ((c, Mono v Natural) -> Mono v Natural)
-> (c, Mono v Natural)
-> Set v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (c, Mono v Natural) -> Mono v Natural
forall a b. (a, b) -> b
snd) [(c, Mono v Natural)]
p

mapVars :: Variable i2 => (i1 -> i2) -> Poly c i1 j -> Poly c i2 j
mapVars :: forall i2 i1 c j.
Variable i2 =>
(i1 -> i2) -> Poly c i1 j -> Poly c i2 j
mapVars i1 -> i2
f (P [(c, Mono i1 j)]
ms) = [(c, Mono i2 j)] -> Poly c i2 j
forall c i j. [(c, Mono i j)] -> Poly c i j
P ([(c, Mono i2 j)] -> Poly c i2 j)
-> [(c, Mono i2 j)] -> Poly c i2 j
forall a b. (a -> b) -> a -> b
$ (\(c
c, M Map i1 j
m) -> (c
c, Map i2 j -> Mono i2 j
forall i j. Map i j -> Mono i j
M (Map i2 j -> Mono i2 j) -> Map i2 j -> Mono i2 j
forall a b. (a -> b) -> a -> b
$ (i1 -> i2) -> Map i1 j -> Map i2 j
forall k2 k1 a. Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a
M.mapKeys i1 -> i2
f Map i1 j
m)) ((c, Mono i1 j) -> (c, Mono i2 j))
-> [(c, Mono i1 j)] -> [(c, Mono i2 j)]
forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> [(c, Mono i1 j)]
ms

mapVarPolynomial :: Variable i => Map i i-> Poly c i j -> Poly c i j
mapVarPolynomial :: forall i c j. Variable i => Map i i -> Poly c i j -> Poly c i j
mapVarPolynomial Map i i
m (P [(c, Mono i j)]
ms) = [(c, Mono i j)] -> Poly c i j
forall c i j. [(c, Mono i j)] -> Poly c i j
P ([(c, Mono i j)] -> Poly c i j) -> [(c, Mono i j)] -> Poly c i j
forall a b. (a -> b) -> a -> b
$ (Mono i j -> Mono i j) -> (c, Mono i j) -> (c, Mono 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 i -> Mono i j -> Mono i j
forall i j. Variable i => Map i i -> Mono i j -> Mono i j
mapVarMonomial Map i i
m) ((c, Mono i j) -> (c, Mono i j))
-> [(c, Mono i j)] -> [(c, Mono i j)]
forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> [(c, Mono i j)]
ms

mapCoeffs :: forall c c' i j .
    (c -> c')
    -> Poly c i j
    -> Poly c' i j
mapCoeffs :: forall c c' i j. (c -> c') -> Poly c i j -> Poly c' i j
mapCoeffs c -> c'
f (P [(c, Mono i j)]
p) = [(c', Mono i j)] -> Poly c' i j
forall c i j. [(c, Mono i j)] -> Poly c i j
P ([(c', Mono i j)] -> Poly c' i j)
-> [(c', Mono i j)] -> Poly c' i j
forall a b. (a -> b) -> a -> b
$ [(c, Mono i j)]
p [(c, Mono i j)]
-> ((c, Mono i j) -> (c', Mono i j)) -> [(c', Mono i j)]
forall (f :: Type -> Type) a b. Functor f => f a -> (a -> b) -> f b
<&> (c -> c') -> (c, Mono i j) -> (c', Mono 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

instance Polynomial c i j => IsList (Poly c i j) where
    type Item (Poly c i j) = (c, Map i j)
    toList :: Poly c i j -> [Item (Poly c i j)]
toList (P [(c, Mono i j)]
p) = (Mono i j -> Map i j) -> (c, Mono 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, Mono i j) -> (c, Map i j))
-> [(c, Mono i j)] -> [(c, Map i j)]
forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> [(c, Mono i j)]
p
    fromList :: [Item (Poly c i j)] -> Poly c i j
fromList [Item (Poly c i j)]
p = [(c, Mono i j)] -> Poly c i j
forall c i j. Polynomial c i j => [(c, Mono i j)] -> Poly c i j
polynomial ([(c, Mono i j)] -> Poly c i j) -> [(c, Mono i j)] -> Poly c i j
forall a b. (a -> b) -> a -> b
$ (Map i j -> Mono i j) -> (c, Map i j) -> (c, Mono 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 -> Mono i j
forall i j. Monomial i j => Map i j -> Mono i j
monomial ((c, Map i j) -> (c, Mono i j))
-> [(c, Map i j)] -> [(c, Mono i j)]
forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> [(c, Map i j)]
[Item (Poly c i j)]
p

instance (Show c, Show i, Show j, Monomial i j) => Show (Poly c i j) where
    show :: Poly c i j -> String
show (P [(c, Mono 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, Mono i j)]
p [(c, Mono i j)] -> ((c, Mono i j) -> String) -> [String]
forall (f :: Type -> Type) a b. Functor f => f a -> (a -> b) -> f b
<&> \(c
c, Mono 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
<> Mono i j -> String
forall a. Show a => a -> String
show (Mono i j
m :: Mono i j)

instance Polynomial c i j => Eq (Poly c i j) where
    P [(c, Mono i j)]
l == :: Poly c i j -> Poly c i j -> Bool
== P [(c, Mono i j)]
r = [(c, Mono i j)]
l [(c, Mono i j)] -> [(c, Mono i j)] -> Bool
forall a. Eq a => a -> a -> Bool
== [(c, Mono i j)]
r

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

instance (Arbitrary c, Arbitrary (Mono i j)) => Arbitrary (Poly c i j) where
    arbitrary :: Gen (Poly c i j)
arbitrary = [(c, Mono i j)] -> Poly c i j
forall c i j. [(c, Mono i j)] -> Poly c i j
P ([(c, Mono i j)] -> Poly c i j)
-> Gen [(c, Mono i j)] -> Gen (Poly c i j)
forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> Gen [(c, Mono i j)]
forall a. Arbitrary a => Gen a
arbitrary

instance {-# OVERLAPPING #-} FromConstant (Poly c i j) (Poly c i j)

instance Polynomial c i j => AdditiveSemigroup (Poly c i j) where
    P [(c, Mono i j)]
l + :: Poly c i j -> Poly c i j -> Poly c i j
+ P [(c, Mono i j)]
r = [(c, Mono i j)] -> Poly c i j
forall c i j. [(c, Mono i j)] -> Poly c i j
P ([(c, Mono i j)] -> Poly c i j) -> [(c, Mono i j)] -> Poly c i j
forall a b. (a -> b) -> a -> b
$ [(c, Mono i j)] -> [(c, Mono i j)] -> [(c, Mono i j)]
forall {a} {a}.
(AdditiveMonoid a, Eq a, Ord a) =>
[(a, a)] -> [(a, a)] -> [(a, a)]
go [(c, Mono i j)]
l [(c, Mono 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
cl a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
forall a. AdditiveMonoid a => a
zero = [(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)
                | a
cr a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
forall a. AdditiveMonoid a => a
zero = [(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
                | 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' (Poly c i j) where
    scale :: c' -> Poly c i j -> Poly c i j
scale c'
c' (P [(c, Mono i j)]
p) = [(c, Mono i j)] -> Poly c i j
forall c i j. [(c, Mono i j)] -> Poly c i j
P ([(c, Mono i j)] -> Poly c i j) -> [(c, Mono i j)] -> Poly c i j
forall a b. (a -> b) -> a -> b
$ ((c, Mono i j) -> (c, Mono i j))
-> [(c, Mono i j)] -> [(c, Mono i j)]
forall a b. (a -> b) -> [a] -> [b]
map ((c -> c) -> (c, Mono i j) -> (c, Mono 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, Mono i j)]
p

instance Polynomial c i j => AdditiveMonoid (Poly c i j) where
    zero :: Poly c i j
zero = [(c, Mono i j)] -> Poly c i j
forall c i j. [(c, Mono i j)] -> Poly c i j
P []

instance Polynomial c i j => AdditiveGroup (Poly c i j) where
    negate :: Poly c i j -> Poly c i j
negate (P [(c, Mono i j)]
p) = [(c, Mono i j)] -> Poly c i j
forall c i j. [(c, Mono i j)] -> Poly c i j
P ([(c, Mono i j)] -> Poly c i j) -> [(c, Mono i j)] -> Poly c i j
forall a b. (a -> b) -> a -> b
$ ((c, Mono i j) -> (c, Mono i j))
-> [(c, Mono i j)] -> [(c, Mono i j)]
forall a b. (a -> b) -> [a] -> [b]
map ((c -> c) -> (c, Mono i j) -> (c, Mono 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, Mono i j)]
p

instance {-# OVERLAPPING #-} Polynomial c i j => Scale (Poly c i j) (Poly c i j)

instance Polynomial c i j => MultiplicativeSemigroup (Poly c i j) where
    P [(c, Mono i j)]
l * :: Poly c i j -> Poly c i j -> Poly c i j
* Poly c i j
r = (Poly c i j -> Poly c i j -> Poly c i j)
-> Poly c i j -> [Poly c i j] -> Poly c 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' Poly c i j -> Poly c i j -> Poly c i j
forall a. AdditiveSemigroup a => a -> a -> a
(+) ([(c, Mono i j)] -> Poly c i j
forall c i j. [(c, Mono i j)] -> Poly c i j
P []) ([Poly c i j] -> Poly c i j) -> [Poly c i j] -> Poly c i j
forall a b. (a -> b) -> a -> b
$ ((c, Mono i j) -> Poly c i j) -> [(c, Mono i j)] -> [Poly c i j]
forall a b. (a -> b) -> [a] -> [b]
map ((c, Mono i j) -> Poly c i j -> Poly c i j
forall c i j.
Polynomial c i j =>
(c, Mono i j) -> Poly c i j -> Poly c i j
`scaleM` Poly c i j
r) [(c, Mono i j)]
l

instance Polynomial c i j => Exponent (Poly c i j) Natural where
    ^ :: Poly c i j -> Natural -> Poly c i j
(^) = Poly c i j -> Natural -> Poly c i j
forall a. MultiplicativeMonoid a => a -> Natural -> a
natPow

instance Polynomial c i j => MultiplicativeMonoid (Poly c i j) where
    one :: Poly c i j
one = [(c, Mono i j)] -> Poly c i j
forall c i j. [(c, Mono i j)] -> Poly c i j
P [(c
forall a. MultiplicativeMonoid a => a
one, Map i j -> Mono i j
forall i j. Map i j -> Mono i j
M Map i j
forall k a. Map k a
empty)]

instance FromConstant c' c => FromConstant c' (Poly c i j) where
    fromConstant :: c' -> Poly c i j
fromConstant c'
x = [(c, Mono i j)] -> Poly c i j
forall c i j. [(c, Mono i j)] -> Poly c i j
P [(c' -> c
forall a b. FromConstant a b => a -> b
fromConstant c'
x, Map i j -> Mono i j
forall i j. Map i j -> Mono i j
M Map i j
forall k a. Map k a
empty)]

instance Polynomial c i j => Semiring (Poly c i j)

instance Polynomial c i j => Ring (Poly c i j)

-- | @'var' i@ is a polynomial \(p(x) = x_i\)
var :: Polynomial c i j => i -> Poly c i j
var :: forall c i j. Polynomial c i j => i -> Poly c i j
var i
x = [(c, Mono i j)] -> Poly c i j
forall c i j. Polynomial c i j => [(c, Mono i j)] -> Poly c i j
polynomial [(c
forall a. MultiplicativeMonoid a => a
one, Map i j -> Mono i j
forall i j. Monomial i j => Map i j -> Mono i j
monomial (Map i j -> Mono i j) -> Map i j -> Mono 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)])]

-- | @'constant' i@ is a polynomial \(p(x) = const\)
constant :: Polynomial c i j => c -> Poly c i j
constant :: forall c i j. Polynomial c i j => c -> Poly c i j
constant c
c = [(c, Mono i j)] -> Poly c i j
forall c i j. Polynomial c i j => [(c, Mono i j)] -> Poly c i j
polynomial [(c
c, Map i j -> Mono i j
forall i j. Map i j -> Mono i j
M Map i j
forall k a. Map k a
M.empty)]

lt :: Polynomial c i j => Poly c i j -> (c, Mono i j)
lt :: forall c i j. Polynomial c i j => Poly c i j -> (c, Mono i j)
lt (P [])    = (c
forall a. AdditiveMonoid a => a
zero, Map i j -> Mono i j
forall i j. Map i j -> Mono i j
M Map i j
forall k a. Map k a
empty)
lt (P ((c, Mono i j)
m:[(c, Mono i j)]
_)) = (c, Mono i j)
m

zeroP :: Poly c i j -> Bool
zeroP :: forall c i j. Poly c i j -> Bool
zeroP (P []) = Bool
True
zeroP Poly c i j
_      = Bool
False

scaleM :: Polynomial c i j => (c, Mono i j) -> Poly c i j -> Poly c i j
scaleM :: forall c i j.
Polynomial c i j =>
(c, Mono i j) -> Poly c i j -> Poly c i j
scaleM (c
c, Mono i j
m) (P [(c, Mono i j)]
p) = [(c, Mono i j)] -> Poly c i j
forall c i j. [(c, Mono i j)] -> Poly c i j
P ([(c, Mono i j)] -> Poly c i j) -> [(c, Mono i j)] -> Poly c i j
forall a b. (a -> b) -> a -> b
$ ((c, Mono i j) -> (c, Mono i j))
-> [(c, Mono i j)] -> [(c, Mono i j)]
forall a b. (a -> b) -> [a] -> [b]
map ((c -> c)
-> (Mono i j -> Mono i j) -> (c, Mono i j) -> (c, Mono i j)
forall a b c d. (a -> b) -> (c -> d) -> (a, c) -> (b, d)
forall (p :: Type -> Type -> Type) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap (c -> c -> c
forall a. MultiplicativeSemigroup a => a -> a -> a
* c
c) (Mono i j -> Mono i j -> Mono i j
forall a. MultiplicativeSemigroup a => a -> a -> a
* Mono i j
m)) [(c, Mono i j)]
p