Data.Poly

Dense polynomials and a Num-based interface.

Since: 0.1.0.0

Documentation

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

Polynomials of one variable with coefficients from a, backed by a Vector v (boxed, unboxed, storable, etc.).

Use the 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.

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 Poly crucially depends on specialisation of instances. Clients are strongly recommended to compile with ghc-options: -fspecialise-aggressively and suggested to enable -O2.

Since: 0.1.0.0

Instances

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

Since: 0.3.1.0

Defined in Data.Poly.Internal.Dense

Associated Types

type Item (Poly v a)

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 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

(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)

Since: 0.3.2.0

Defined in Data.Poly.Internal.Dense

Methods

rnf :: 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

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

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

Note that degree 0 = 0.

Since: 0.3.0.0

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

Since: 0.3.0.0

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

Defined in Data.Poly.Internal.Dense

Methods

negate :: Poly v a -> Poly v a

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

Note that times is significantly slower than (*) for large polynomials, because Karatsuba multiplication algorithm requires subtraction, which is not provided by Semiring class. Use timesRing instead.

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

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.

Since: 0.2.0.0

type UPoly = Poly Vector

Polynomials backed by unboxed vectors.

Since: 0.2.0.0

unPoly :: Poly v a -> v a

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

Since: 0.1.0.0

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

Return the 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

Since: 0.3.0.0

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

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

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

Since: 0.1.0.0

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

Create a monomial from a power and a coefficient.

Since: 0.3.0.0

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

Since: 0.3.0.0

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

The polynomial X.

X == monomial 1 1

Since: 0.2.0.0

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

Evaluate the polynomial at a given point.

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

Since: 0.2.0.0

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

Since: 0.3.3.0

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

Take the derivative of the polynomial.

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

Since: 0.2.0.0

integral :: (Eq a, Fractional a, Vector v a) => Poly v a -> Poly v a

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

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

Since: 0.2.0.0

quotRemFractional :: (Eq a, Fractional a, Vector v a) => Poly v a -> Poly v a -> (Poly v a, Poly v a)

Polynomial division with remainder.

>>> quotRemFractional (X^3 + 2) (X^2 - 1 :: UPoly Double)
(1.0 * X + 0.0,1.0 * X + 2.0)

Since: 0.5.0.0

denseToSparse :: (Eq a, Num 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 + Data.Poly.X^2) :: Data.Poly.Sparse.UPoly Int
1 * X^2 + 1

Since: 0.5.0.0

sparseToDense :: (Num 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 + Data.Poly.Sparse.X^2) :: Data.Poly.UPoly Int
1 * X^2 + 0 * X + 1

Since: 0.5.0.0