Data.Poly.Sparse.Semiring

Sparse polynomials with Semiring instance.

Documentation

data Poly v a

Polynomials of one variable 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.

Instances

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

Defined in Data.Poly.Internal.Sparse

Associated Types

type Item (Poly v a) :: Type

Methods

fromList :: [Item (Poly v a)] -> Poly v a

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

toList :: Poly v a -> [Item (Poly v a)]

Eq (v (Word, a)) => Eq (Poly v a)

Defined in Data.Poly.Internal.Sparse

Methods

(==) :: Poly v a -> Poly v a -> Bool

(/=) :: Poly v a -> Poly v a -> Bool

(Eq a, Num a, Vector v (Word, a)) => Num (Poly v a)

Note that abs = id and signum = const 1.

Defined in Data.Poly.Internal.Sparse

Methods

(+) :: Poly v a -> Poly v a -> Poly v a

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

(*) :: Poly v a -> Poly v a -> Poly v a

negate :: Poly v a -> Poly v a

abs :: Poly v a -> Poly v a

signum :: Poly v a -> Poly v a

fromInteger :: Integer -> Poly v a

Ord (v (Word, a)) => Ord (Poly v a)

Defined in Data.Poly.Internal.Sparse

Methods

compare :: Poly v a -> Poly v a -> Ordering

(<) :: Poly v a -> Poly v a -> Bool

(<=) :: Poly v a -> Poly v a -> Bool

(>) :: Poly v a -> Poly v a -> Bool

(>=) :: Poly v a -> Poly v a -> Bool

max :: Poly v a -> Poly v a -> Poly v a

min :: Poly v a -> Poly v a -> Poly v a

(Show a, Vector v (Word, a)) => Show (Poly v a)

Defined in Data.Poly.Internal.Sparse

Methods

showsPrec :: Int -> Poly v a -> ShowS

show :: Poly v a -> String

showList :: [Poly v a] -> ShowS

NFData (v (Word, a)) => NFData (Poly v a)

Defined in Data.Poly.Internal.Sparse

Methods

rnf :: Poly v a -> ()

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

Consider using PolyOverField wrapper, which provides a much faster implementation of gcd for polynomials over Field.

Defined in Data.Poly.Internal.Sparse.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, Eq (v (Word, a)), Field a, Vector v (Word, a)) => Euclidean (Poly v a)

Defined in Data.Poly.Internal.Sparse.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, Semiring a, Vector v (Word, a)) => Semiring (Poly v a)

Defined in Data.Poly.Internal.Sparse

Methods

plus :: Poly v a -> Poly v a -> Poly v a

zero :: Poly v a

times :: Poly v a -> Poly v a -> Poly v a

one :: Poly v a

fromNatural :: Natural -> Poly v a

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

Defined in Data.Poly.Internal.Sparse

Methods

negate :: Poly v a -> Poly v a

type Item (Poly v a)

Defined in Data.Poly.Internal.Sparse

type Item (Poly v a) = (Word, a)

type VPoly = Poly Vector

Polynomials backed by boxed vectors.

type UPoly = Poly Vector

Polynomials backed by unboxed vectors.

unPoly :: Poly v a -> v (Word, a)

Convert Poly to a vector of coefficients (first element corresponds to a constant term).

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

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

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

Semiring interface

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

Make Poly from a list of (power, coefficient) pairs. (first element corresponds to a constant term).

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

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

Create a monomial from a power and a coefficient.

scale :: (Eq a, Semiring a, Vector v (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 (Word, a), Eq (v (Word, a))) => Poly v a

Create an identity polynomial.

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

Evaluate at a given point.

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

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

Take a derivative.

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

integral :: (Eq a, Field a, Vector v (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

Polynomials over Field

gcdExt :: (Eq a, Field a, Vector v (Word, a), Eq (v (Word, a))) => Poly v a -> Poly v a -> (Poly v a, Poly v a)

Execute the extended Euclidean algorithm. For polynomials a and b, compute their unique greatest common divisor g and the unique coefficient polynomial s satisfying as + bt = g, such that either g is monic, or g = 0 and s is monic, or g = s = 0.

>>> gcdExt (X^2 + 1 :: UPoly Double) (X^3 + 3 * X :: UPoly Double)
(1.0, 0.5 * X^2 + (-0.0) * X + 1.0)
>>> gcdExt (X^3 + 3 * X :: UPoly Double) (3 * X^4 + 3 * X^2 :: UPoly Double)
(1.0 * X + 0.0,(-0.16666666666666666) * X^2 + (-0.0) * X + 0.3333333333333333)