Data.Poly.Multi.Semiring

Sparse multivariate polynomials with a Semiring instance.

Since: 0.5.0.0

Documentation

data MultiPoly (v :: Type -> Type) (n :: Nat) (a :: Type)

Sparse polynomials of n variables with coefficients from a, backed by a Vector v (boxed, unboxed, storable, etc.).

Use the patterns X, Y and Z for construction:

>>> :set -XDataKinds
>>> (X + 1) + (Y - 1) + Z :: VMultiPoly 3 Integer
1 * X + 1 * Y + 1 * Z
>>> (X + 1) * (Y - 1) :: UMultiPoly 2 Int
1 * X * Y + (-1) * X + 1 * Y + (-1)

Polynomials are stored normalized, without zero coefficients, so 0 * X + 1 equals to 1.

The Ord instance does not make much sense mathematically, it is defined only for the sake of Set, Map, etc.

Due to being polymorphic by multiple axis, the performance of MultiPoly crucially depends on specialisation of instances. Clients are strongly recommended to compile with ghc-options: -fspecialise-aggressively and suggested to enable -O2.

Since: 0.5.0.0

Instances

(Eq a, Field a, Vector v (Vector 1 Word, a)) => Euclidean (Poly v a)

Note that degree 0 = 0.

Defined in Data.Poly.Internal.Multi.Field

Methods

quotRem :: Poly v a -> Poly v a -> (Poly v a, Poly v a)

quot :: Poly v a -> Poly v a -> Poly v a

rem :: Poly v a -> Poly v a -> Poly v a

degree :: Poly v a -> Natural

(Eq a, Ring a, GcdDomain a, Vector v (Vector 1 Word, a)) => GcdDomain (Poly v a)

Defined in Data.Poly.Internal.Multi.GcdDomain

Methods

divide :: Poly v a -> Poly v a -> Maybe (Poly v a)

gcd :: Poly v a -> Poly v a -> Poly v a

lcm :: Poly v a -> Poly v a -> Poly v a

coprime :: Poly v a -> Poly v a -> Bool

(Eq a, Semiring a, Vector v (Vector n Word, a)) => IsList (MultiPoly v n a)

Defined in Data.Poly.Internal.Multi

Associated Types

type Item (MultiPoly v n a)

Methods

fromList :: [Item (MultiPoly v n a)] -> MultiPoly v n a

fromListN :: Int -> [Item (MultiPoly v n a)] -> MultiPoly v n a

toList :: MultiPoly v n a -> [Item (MultiPoly v n a)]

(Eq a, Num a, KnownNat n, Vector v (Vector n Word, a)) => Num (MultiPoly v n a)

Note that abs = id and signum = const 1.

Defined in Data.Poly.Internal.Multi

Methods

(+) :: MultiPoly v n a -> MultiPoly v n a -> MultiPoly v n a

(-) :: MultiPoly v n a -> MultiPoly v n a -> MultiPoly v n a

(*) :: MultiPoly v n a -> MultiPoly v n a -> MultiPoly v n a

negate :: MultiPoly v n a -> MultiPoly v n a

abs :: MultiPoly v n a -> MultiPoly v n a

signum :: MultiPoly v n a -> MultiPoly v n a

fromInteger :: Integer -> MultiPoly v n a

(Show a, KnownNat n, Vector v (Vector n Word, a)) => Show (MultiPoly v n a)

Defined in Data.Poly.Internal.Multi

Methods

showsPrec :: Int -> MultiPoly v n a -> ShowS

show :: MultiPoly v n a -> String

showList :: [MultiPoly v n a] -> ShowS

NFData (v (Vector n Word, a)) => NFData (MultiPoly v n a)

Defined in Data.Poly.Internal.Multi

Methods

rnf :: MultiPoly v n a -> ()

Eq (v (Vector n Word, a)) => Eq (MultiPoly v n a)

Defined in Data.Poly.Internal.Multi

Methods

(==) :: MultiPoly v n a -> MultiPoly v n a -> Bool

(/=) :: MultiPoly v n a -> MultiPoly v n a -> Bool

Ord (v (Vector n Word, a)) => Ord (MultiPoly v n a)

Defined in Data.Poly.Internal.Multi

Methods

compare :: MultiPoly v n a -> MultiPoly v n a -> Ordering

(<) :: MultiPoly v n a -> MultiPoly v n a -> Bool

(<=) :: MultiPoly v n a -> MultiPoly v n a -> Bool

(>) :: MultiPoly v n a -> MultiPoly v n a -> Bool

(>=) :: MultiPoly v n a -> MultiPoly v n a -> Bool

max :: MultiPoly v n a -> MultiPoly v n a -> MultiPoly v n a

min :: MultiPoly v n a -> MultiPoly v n a -> MultiPoly v n a

(Eq a, Ring a, GcdDomain a, KnownNat n, forall (m :: Nat). KnownNat m => Vector v (Vector m Word, a), forall (m :: Nat). KnownNat m => Eq (v (Vector m Word, a))) => GcdDomain (MultiPoly v n a)

Defined in Data.Poly.Internal.Multi.GcdDomain

Methods

divide :: MultiPoly v n a -> MultiPoly v n a -> Maybe (MultiPoly v n a)

gcd :: MultiPoly v n a -> MultiPoly v n a -> MultiPoly v n a

lcm :: MultiPoly v n a -> MultiPoly v n a -> MultiPoly v n a

coprime :: MultiPoly v n a -> MultiPoly v n a -> Bool

(Eq a, Ring a, KnownNat n, Vector v (Vector n Word, a)) => Ring (MultiPoly v n a)

Defined in Data.Poly.Internal.Multi

Methods

negate :: MultiPoly v n a -> MultiPoly v n a

(Eq a, Semiring a, KnownNat n, Vector v (Vector n Word, a)) => Semiring (MultiPoly v n a)

Defined in Data.Poly.Internal.Multi

Methods

plus :: MultiPoly v n a -> MultiPoly v n a -> MultiPoly v n a

zero :: MultiPoly v n a

times :: MultiPoly v n a -> MultiPoly v n a -> MultiPoly v n a

one :: MultiPoly v n a

fromNatural :: Natural -> MultiPoly v n a

type Item (MultiPoly v n a)

Defined in Data.Poly.Internal.Multi

type Item (MultiPoly v n a) = (Vector n Word, a)

type VMultiPoly (n :: Nat) (a :: Type) = MultiPoly Vector n a

Multivariate polynomials backed by boxed vectors.

Since: 0.5.0.0

type UMultiPoly (n :: Nat) (a :: Type) = MultiPoly Vector n a

Multivariate polynomials backed by unboxed vectors.

Since: 0.5.0.0

unMultiPoly :: MultiPoly v n a -> v (Vector n Word, a)

Convert a MultiPoly to a vector of (powers, coefficient) pairs.

Since: 0.5.0.0

toMultiPoly :: (Eq a, Semiring a, Vector v (Vector n Word, a)) => v (Vector n Word, a) -> MultiPoly v n a

Make a MultiPoly from a list of (powers, coefficient) pairs.

>>> :set -XOverloadedLists -XDataKinds
>>> import Data.Vector.Generic.Sized (fromTuple)
>>> toMultiPoly [(fromTuple (0,0),1),(fromTuple (0,1),2),(fromTuple (1,0),3)] :: VMultiPoly 2 Integer
3 * X + 2 * Y + 1
>>> toMultiPoly [(fromTuple (0,0),0),(fromTuple (0,1),0),(fromTuple (1,0),0)] :: UMultiPoly 2 Int
0

Since: 0.5.0.0

monomial :: (Eq a, Semiring a, Vector v (Vector n Word, a)) => Vector n Word -> a -> MultiPoly v n a

Create a monomial from powers and a coefficient.

Since: 0.5.0.0

scale :: (Eq a, Semiring a, KnownNat n, Vector v (Vector n Word, a)) => Vector n Word -> a -> MultiPoly v n a -> MultiPoly v n a

Multiply a polynomial by a monomial, expressed as powers and a coefficient.

>>> :set -XDataKinds
>>> import Data.Vector.Generic.Sized (fromTuple)
>>> scale (fromTuple (1, 1)) 3 (X^2 + Y) :: UMultiPoly 2 Int
3 * X^3 * Y + 3 * X * Y^2

Since: 0.5.0.0

pattern X :: (Eq a, Semiring a, KnownNat n, 1 <= n, Vector v (Vector n Word, a)) => MultiPoly v n a

Create a polynomial equal to the first variable.

Since: 0.5.0.0

pattern Y :: (Eq a, Semiring a, KnownNat n, 2 <= n, Vector v (Vector n Word, a)) => MultiPoly v n a

Create a polynomial equal to the second variable.

Since: 0.5.0.0

pattern Z :: (Eq a, Semiring a, KnownNat n, 3 <= n, Vector v (Vector n Word, a)) => MultiPoly v n a

Create a polynomial equal to the third variable.

Since: 0.5.0.0

eval :: (Semiring a, Vector v (Vector n Word, a), Vector u a) => MultiPoly v n a -> Vector u n a -> a

Evaluate the polynomial at a given point.

>>> :set -XDataKinds
>>> import Data.Vector.Generic.Sized (fromTuple)
>>> eval (X^2 + Y^2 :: UMultiPoly 2 Int) (fromTuple (3, 4) :: Data.Vector.Sized.Vector 2 Int)
25

Since: 0.5.0.0

subst :: (Eq a, Semiring a, KnownNat m, Vector v (Vector n Word, a), Vector w (Vector m Word, a)) => MultiPoly v n a -> Vector n (MultiPoly w m a) -> MultiPoly w m a

Substitute other polynomials instead of the variables.

>>> :set -XDataKinds
>>> import Data.Vector.Generic.Sized (fromTuple)
>>> subst (X^2 + Y^2 + Z^2 :: UMultiPoly 3 Int) (fromTuple (X + 1, Y + 1, X + Y :: UMultiPoly 2 Int))
2 * X^2 + 2 * X * Y + 2 * X + 2 * Y^2 + 2 * Y + 2

Since: 0.5.0.0

deriv :: (Eq a, Semiring a, Vector v (Vector n Word, a)) => Finite n -> MultiPoly v n a -> MultiPoly v n a

Take the derivative of the polynomial with respect to the i-th variable.

>>> :set -XDataKinds
>>> deriv 0 (X^3 + 3 * Y) :: UMultiPoly 2 Int
3 * X^2
>>> deriv 1 (X^3 + 3 * Y) :: UMultiPoly 2 Int
3

Since: 0.5.0.0

integral :: (Field a, Vector v (Vector n Word, a)) => Finite n -> MultiPoly v n a -> MultiPoly v n a

Compute an indefinite integral of the polynomial with respect to the i-th variable, setting the constant term to zero.

>>> :set -XDataKinds
>>> integral 0 (3 * X^2 + 2 * Y) :: UMultiPoly 2 Double
1.0 * X^3 + 2.0 * X * Y
>>> integral 1 (3 * X^2 + 2 * Y) :: UMultiPoly 2 Double
3.0 * X^2 * Y + 1.0 * Y^2

Since: 0.5.0.0

segregate :: (Vector v (Vector (1 + m) Word, a), Vector v (Vector m Word, a)) => MultiPoly v (1 + m) a -> VPoly (MultiPoly v m a)

Interpret a multivariate polynomial over 1+m variables as a univariate polynomial, whose coefficients are multivariate polynomials over the last m variables.

Since: 0.5.0.0

unsegregate :: (Vector v (Vector (1 + m) Word, a), Vector v (Vector m Word, a)) => VPoly (MultiPoly v m a) -> MultiPoly v (1 + m) a

Interpret a univariate polynomials, whose coefficients are multivariate polynomials over the first m variables, as a multivariate polynomial over 1+m variables.

Since: 0.5.0.0