poly
Copyright(c) 2019 Andrew Lelechenko
LicenseBSD3
MaintainerAndrew Lelechenko <[email protected]>
Safe HaskellNone
LanguageHaskell2010

Data.Poly

Description

Dense polynomials and a Num-based interface.

Since: 0.1.0.0

Synopsis

Documentation

data Poly (v :: Type -> Type) a 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
NFData (v a) => NFData (Poly v a) Source #

Since: 0.3.2.0

Instance details

Defined in Data.Poly.Internal.Dense

Methods

rnf :: Poly v a -> () #

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

Since: 0.3.1.0

Instance details

Defined in Data.Poly.Internal.Dense

Associated Types

type Item (Poly v a) 
Instance details

Defined in Data.Poly.Internal.Dense

type Item (Poly v a) = 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) Source #

Note that abs = id and signum = const 1.

Instance details

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

Defined in Data.Poly.Internal.Dense

Methods

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

show :: Poly v a -> String #

showList :: [Poly v a] -> ShowS #

Eq (v a) => Eq (Poly v a) Source # 
Instance details

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

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

Note that degree 0 = 0.

Since: 0.3.0.0

Instance details

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

Since: 0.3.0.0

Instance details

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

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

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

Defined in Data.Poly.Internal.Dense

type Item (Poly v a) = a

type VPoly = Poly Vector Source #

Polynomials backed by boxed vectors.

Since: 0.2.0.0

type UPoly = Poly Vector Source #

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 :: forall (v :: Type -> Type) a. 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 :: forall a (v :: Type -> Type). (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 :: forall a (v :: Type -> Type). (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 :: forall a (v :: Type -> Type). (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 :: forall a (v :: Type -> Type) (w :: Type -> Type). (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 :: forall a (v :: Type -> Type). (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 :: forall a (v :: Type -> Type). (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 :: forall a (v :: Type -> Type). (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 :: forall a (v :: Type -> Type). (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 :: forall a (v :: Type -> Type). (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