Data.Poly.Sparse.Semiring

Sparse polynomials with Semiring instance.

Documentation

type Poly (v :: Type -> Type) (a :: Type) = MultiPoly v 1 a

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

Use pattern X for construction:

>>> (X + 1) + (X - 1) :: VPoly Integer
2 * X
>>> (X + 1) * (X - 1) :: UPoly Int
1 * X^2 + (-1)

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

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

type VPoly (a :: Type) = Poly Vector a

Polynomials backed by boxed vectors.

type UPoly (a :: Type) = Poly Vector a

Polynomials backed by unboxed vectors.

unPoly :: (Vector v (Word, a), Vector v (Vector 1 Word, a)) => Poly v a -> v (Word, a)

Convert Poly to a vector of coefficients.

toPoly :: (Eq a, Semiring a, Vector v (Word, a), Vector v (Vector 1 Word, a)) => v (Word, a) -> Poly v a

Make Poly from a list of (power, coefficient) pairs.

>>> :set -XOverloadedLists
>>> toPoly [(0,1),(1,2),(2,3)] :: VPoly Integer
3 * X^2 + 2 * X + 1
>>> toPoly [(0,0),(1,0),(2,0)] :: UPoly Int
0

leading :: Vector v (Vector 1 Word, a) => Poly v a -> Maybe (Word, a)

Return a leading power and coefficient of a non-zero polynomial.

>>> import Data.Poly.Sparse (UPoly)
>>> leading ((2 * X + 1) * (2 * X^2 - 1) :: UPoly Int)
Just (3,4)
>>> leading (0 :: UPoly Int)
Nothing

monomial :: (Eq a, Semiring a, Vector v (Vector 1 Word, a)) => Word -> a -> Poly v a

Create a monomial from a power and a coefficient.

scale :: (Eq a, Semiring a, Vector v (Vector 1 Word, a)) => Word -> a -> Poly v a -> Poly v a

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

>>> scale 2 3 (X^2 + 1) :: UPoly Int
3 * X^4 + 3 * X^2

pattern X :: (Eq a, Semiring a, Vector v (Vector 1 Word, a)) => Poly v a

Create an identity polynomial.

eval :: (Semiring a, Vector v (Vector 1 Word, a)) => Poly v a -> a -> a

Evaluate at a given point.

>>> eval (X^2 + 1 :: UPoly Int) 3
10

subst :: (Eq a, Semiring a, Vector v (Vector 1 Word, a), Vector w (Vector 1 Word, a)) => Poly v a -> Poly w a -> Poly w a

Substitute another polynomial instead of X.

>>> subst (X^2 + 1 :: UPoly Int) (X + 1 :: UPoly Int)
1 * X^2 + 2 * X + 2

deriv :: (Eq a, Semiring a, Vector v (Vector 1 Word, a)) => Poly v a -> Poly v a

Take a derivative.

>>> deriv (X^3 + 3 * X) :: UPoly Int
3 * X^2 + 3

integral :: (Field a, Vector v (Vector 1 Word, a)) => Poly v a -> Poly v a

Compute an indefinite integral of a polynomial, setting constant term to zero.

>>> integral (3 * X^2 + 3) :: UPoly Double
1.0 * X^3 + 3.0 * X

denseToSparse :: (Eq a, Semiring a, Vector v a, Vector v (Vector 1 Word, a)) => Poly v a -> Poly v a

Convert from dense to sparse polynomials.

>>> :set -XFlexibleContexts
>>> denseToSparse (1 `plus` Data.Poly.X^2) :: Data.Poly.Sparse.UPoly Int
1 * X^2 + 1

sparseToDense :: (Semiring a, Vector v a, Vector v (Vector 1 Word, a)) => Poly v a -> Poly v a

Convert from sparse to dense polynomials.

>>> :set -XFlexibleContexts
>>> sparseToDense (1 `plus` Data.Poly.Sparse.X^2) :: Data.Poly.UPoly Int
1 * X^2 + 0 * X + 1