{-# 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
type Polynomial c i j = (Eq c, Field c, Monomial i j)
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)
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)]
type PolynomialAny c = P c Integer Integer MonomialRepAny (PolynomialRepAny c)
type PolynomialBoundedDegree c i d = P c i Bool (MonomialRepBoundedDegree i d) (PolynomialRepBoundedDegree c i d)
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
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
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 :: 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