Data.Poly

Dense polynomials and a Num-based interface.

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 + 0
>>> (X + 1) * (X - 1) :: UPoly Int
1 * X^2 + 0 * X + (-1)

Polynomials are stored normalized, without leading 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, Eq (v a), Field a, Vector v a) => GcdDomain (PolyOverField (Poly v a))

Defined in Data.Poly.Internal.PolyOverField

Methods

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

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

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

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

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

Defined in Data.Poly.Internal.PolyOverField

Methods

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

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

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

degree :: PolyOverField (Poly v a) -> Natural

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

Defined in Data.Poly.Internal.Dense

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 a) => Eq (Poly v a)

Defined in Data.Poly.Internal.Dense

Methods

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

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

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

Note that abs = id and signum = const 1.

Defined in Data.Poly.Internal.Dense

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 a) => Ord (Poly v a)

Defined in Data.Poly.Internal.Dense

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 a) => Show (Poly v a)

Defined in Data.Poly.Internal.Dense

Methods

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

show :: Poly v a -> String

showList :: [Poly v a] -> ShowS

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

Defined in Data.Poly.Internal.Dense

Methods

rnf :: Poly v a -> ()

(Eq a, Ring a, GcdDomain a, Eq (v a), Vector v 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.Dense.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 a), Field a, Vector v a) => Euclidean (Poly v a)

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

Defined in Data.Poly.Internal.Dense

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 a) => Ring (Poly v a)

Defined in Data.Poly.Internal.Dense

Methods

negate :: Poly v a -> Poly v a

type Item (Poly v a)

Defined in Data.Poly.Internal.Dense

type Item (Poly v a) = a

type VPoly = Poly Vector

Polynomials backed by boxed vectors.

type UPoly = Poly Vector

Polynomials backed by unboxed vectors.

unPoly :: Poly v a -> v a

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

leading :: Vector v 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

Num interface

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

Make Poly from a list of coefficients (first element corresponds to a constant term).

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

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

Create a monomial from a power and a coefficient.

scale :: (Eq a, Num a, Vector v 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 + 0 * X^3 + 3 * X^2 + 0 * X + 0

pattern X :: (Eq a, Num a, Vector v a, Eq (v a)) => Poly v a

Create an identity polynomial.

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

Evaluate at a given point.

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

subst :: (Eq a, Num a, Vector v a, Vector w 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, Num a, Vector v a) => Poly v a -> Poly v a

Take a derivative.

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

integral :: (Eq a, Fractional a, Vector v 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 + 0.0 * X^2 + 3.0 * X + 0.0

Polynomials over Field

newtype PolyOverField poly

Wrapper for polynomials over Field, providing a faster GcdDomain instance.

Constructors

PolyOverField

Fields

• unPolyOverField :: poly

Instances

Eq poly => Eq (PolyOverField poly)

Defined in Data.Poly.Internal.PolyOverField

Methods

(==) :: PolyOverField poly -> PolyOverField poly -> Bool

(/=) :: PolyOverField poly -> PolyOverField poly -> Bool

Num poly => Num (PolyOverField poly)

Defined in Data.Poly.Internal.PolyOverField

Methods

(+) :: PolyOverField poly -> PolyOverField poly -> PolyOverField poly

(-) :: PolyOverField poly -> PolyOverField poly -> PolyOverField poly

(*) :: PolyOverField poly -> PolyOverField poly -> PolyOverField poly

negate :: PolyOverField poly -> PolyOverField poly

abs :: PolyOverField poly -> PolyOverField poly

signum :: PolyOverField poly -> PolyOverField poly

fromInteger :: Integer -> PolyOverField poly

Ord poly => Ord (PolyOverField poly)

Defined in Data.Poly.Internal.PolyOverField

Methods

compare :: PolyOverField poly -> PolyOverField poly -> Ordering

(<) :: PolyOverField poly -> PolyOverField poly -> Bool

(<=) :: PolyOverField poly -> PolyOverField poly -> Bool

(>) :: PolyOverField poly -> PolyOverField poly -> Bool

(>=) :: PolyOverField poly -> PolyOverField poly -> Bool

max :: PolyOverField poly -> PolyOverField poly -> PolyOverField poly

min :: PolyOverField poly -> PolyOverField poly -> PolyOverField poly

Show poly => Show (PolyOverField poly)

Defined in Data.Poly.Internal.PolyOverField

Methods

showsPrec :: Int -> PolyOverField poly -> ShowS

show :: PolyOverField poly -> String

showList :: [PolyOverField poly] -> ShowS

NFData poly => NFData (PolyOverField poly)

Defined in Data.Poly.Internal.PolyOverField

Methods

rnf :: PolyOverField poly -> ()

(Eq a, Eq (v a), Field a, Vector v a) => GcdDomain (PolyOverField (Poly v a))

Defined in Data.Poly.Internal.PolyOverField

Methods

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

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

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

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

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

Defined in Data.Poly.Internal.PolyOverField

Methods

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

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

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

degree :: PolyOverField (Poly v a) -> Natural

Semiring poly => Semiring (PolyOverField poly)

Defined in Data.Poly.Internal.PolyOverField

Methods

plus :: PolyOverField poly -> PolyOverField poly -> PolyOverField poly

zero :: PolyOverField poly

times :: PolyOverField poly -> PolyOverField poly -> PolyOverField poly

one :: PolyOverField poly

fromNatural :: Natural -> PolyOverField poly

Ring poly => Ring (PolyOverField poly)

Defined in Data.Poly.Internal.PolyOverField

Methods

negate :: PolyOverField poly -> PolyOverField poly

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

type PolyOverFractional = PolyOverField

Deprecated: Use PolyOverField

pattern PolyOverFractional :: poly -> PolyOverField poly

Deprecated: Use PolyOverField

unPolyOverFractional :: PolyOverField poly -> poly

Deprecated: Use unPolyOverField