poly-0.5.1.0: Polynomials

Data.Poly

Description

Dense polynomials and a Num-based interface.

Since: 0.1.0.0

Synopsis

# Documentation

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

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

Instances details
 (Eq a, Semiring a, Vector v a) => IsList (Poly v a) Source # Since: 0.3.1.0 Instance detailsDefined in Data.Poly.Internal.Dense Associated Typestype Item (Poly v a) # MethodsfromList :: [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) Source # Note that abs = id and signum = const 1. Instance detailsDefined 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) Source # Instance detailsDefined in Data.Poly.Internal.Dense MethodsshowsPrec :: Int -> Poly v a -> ShowS #show :: Poly v a -> String #showList :: [Poly v a] -> ShowS # NFData (v a) => NFData (Poly v a) Source # Since: 0.3.2.0 Instance detailsDefined in Data.Poly.Internal.Dense Methodsrnf :: Poly v a -> () # Eq (v a) => Eq (Poly v a) Source # Instance detailsDefined 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) Source # Instance detailsDefined in Data.Poly.Internal.Dense Methodscompare :: 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) Source # Note that degree 0 = 0.Since: 0.3.0.0 Instance detailsDefined in Data.Poly.Internal.Dense.Field MethodsquotRem :: 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) Source # Since: 0.3.0.0 Instance detailsDefined in Data.Poly.Internal.Dense.GcdDomain Methodsdivide :: 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) Source # Instance detailsDefined in Data.Poly.Internal.Dense Methodsnegate :: Poly v a -> Poly v a # (Eq a, Semiring a, Vector v a) => Semiring (Poly v a) Source # 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. Instance detailsDefined in Data.Poly.Internal.Dense Methodsplus :: 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) Source # Instance detailsDefined in Data.Poly.Internal.Dense type Item (Poly v a) = a

Polynomials backed by boxed vectors.

Since: 0.2.0.0

Polynomials backed by unboxed vectors.

Since: 0.2.0.0

unPoly :: Poly v a -> v a Source #

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) Source #

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

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

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

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

The polynomial X.

X == monomial 1 1

Since: 0.2.0.0

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

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

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

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

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) Source #

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

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

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