Numeric.Polynomial.Simple

Basic operations

data Poly a

Polynomial with coefficients in a.

Instances

NFData1 Poly

Defined in Numeric.Polynomial.Simple

Methods

liftRnf :: (a -> ()) -> Poly a -> ()

Generic1 Poly

Defined in Numeric.Polynomial.Simple

Associated Types

type Rep1 Poly :: k -> Type

Methods

from1 :: forall (a :: k). Poly a -> Rep1 Poly a

to1 :: forall (a :: k). Rep1 Poly a -> Poly a

Generic (Poly a)

Defined in Numeric.Polynomial.Simple

Associated Types

type Rep (Poly a) :: Type -> Type

Methods

from :: Poly a -> Rep (Poly a) x

to :: Rep (Poly a) x -> Poly a

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

Algebraic operations (+), (*) and negate on polynomials.

The functions abs and signum are undefined.

Defined in Numeric.Polynomial.Simple

Methods

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

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

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

negate :: Poly a -> Poly a

abs :: Poly a -> Poly a

signum :: Poly a -> Poly a

fromInteger :: Integer -> Poly a

Show a => Show (Poly a)

Defined in Numeric.Polynomial.Simple

Methods

showsPrec :: Int -> Poly a -> ShowS

show :: Poly a -> String

showList :: [Poly a] -> ShowS

NFData a => NFData (Poly a)

Defined in Numeric.Polynomial.Simple

Methods

rnf :: Poly a -> ()

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

Defined in Numeric.Polynomial.Simple

Methods

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

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

Num a => Function (Poly a)

Evaluate a polynomial at a point.

eval :: Poly a -> a -> a

Defined in Numeric.Polynomial.Simple

Associated Types

type Domain (Poly a)

type Codomain (Poly a)

Methods

eval :: Poly a -> Domain (Poly a) -> Codomain (Poly a)

type Rep1 Poly

Defined in Numeric.Polynomial.Simple

type Rep1 Poly = D1 ('MetaData "Poly" "Numeric.Polynomial.Simple" "probability-polynomial-1.0.0.0-Io9HtYYYG7kKdjpxqhKwNY" 'True) (C1 ('MetaCons "Poly" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec1 List)))

type Rep (Poly a)

Defined in Numeric.Polynomial.Simple

type Rep (Poly a) = D1 ('MetaData "Poly" "Numeric.Polynomial.Simple" "probability-polynomial-1.0.0.0-Io9HtYYYG7kKdjpxqhKwNY" 'True) (C1 ('MetaCons "Poly" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 [a])))

type Codomain (Poly a)

Defined in Numeric.Polynomial.Simple

type Codomain (Poly a) = a

type Domain (Poly a)

Defined in Numeric.Polynomial.Simple

type Domain (Poly a) = a

eval :: Num a => Poly a -> a -> a

Evaluate a polynomial at a point.

eval :: Poly a -> a -> a

Uses Horner's method to minimise the number of multiplications.

a0 + a1·x + a2·x^2 + ... + a{n-1}·x^{n-1} + an·x^n
  = a0 + x·(a1 + x·(a2 + x·(… + x·(a{n-1} + x·an)) ))

degree :: (Eq a, Num a) => Poly a -> Int

Degree of a polynomial.

The degree of a constant polynomial is 0, but the degree of the zero polynomial is -1 for Euclidean division.

constant :: a -> Poly a

The constant polynomial.

eval (constant a) = const a

zero :: Num a => Poly a

The zero polynomial.

monomial :: (Eq a, Num a) => Int -> a -> Poly a

monomial n a is the polynomial a * x^n.

fromCoefficients :: (Eq a, Num a) => [a] -> Poly a

Construct a polynomial a0 + a1·x + … from its list of coefficients [a0, a1, …].

toCoefficients :: Poly a -> [a]

List the coefficients [a0, a1, …] of a polynomial a0 + a1·x + ….

scale :: Num a => a -> Poly a -> Poly a

Scale a polynomial by a scalar. More efficient than multiplying by a constant polynomial.

eval (scale a p) x = a * eval p x

scaleX :: (Eq a, Num a) => Poly a -> Poly a

Multiply the polynomial by the unknown x.

eval (scaleX p) x = x * eval p x
degree (scaleX p) = 1 + degree p  if  degree p >= 0

Advanced operations

Convenience

display :: (Ord a, Eq a, Num a) => Poly a -> (a, a) -> a -> [(a, a)]

Return a list of pairs (x, eval p x) from the graph of the polynomial. The values x are from the range (l, u) with uniform spacing s.

Specifically,

map fst (display p (l, u) s)
  = [l, l+s, l + 2·s, … , u'] ++ if u' == l then [] else [l]

where u' is the largest number of the form u' = l + s·k, k natural, that still satisfies u' < l. We always display the last point as well.

lineFromTo :: (Eq a, Fractional a) => (a, a) -> (a, a) -> Poly a

Linear polymonial connecting the points (x1, y1) and (x2, y2), assuming that x1 ≠ x2.

If the points are equal, we return a constant polynomial.

let p = lineFromTo (x1, y1) (x2, y2)

degree p <= 1
eval p x1 = y1
eval p x2 = y2

Algebraic

translate :: forall a. (Fractional a, Eq a, Num a) => a -> Poly a -> Poly a

Translate the argument of a polynomial by summing binomial expansions.

eval (translate y p) x = eval p (x - y)

integrate :: (Eq a, Fractional a) => Poly a -> Poly a

Indefinite integral of a polynomial with constant term zero.

The integral of x^n is 1/(n+1)·x^(n+1).

eval (integrate p) 0 = 0
integrate (differentiate p) = p - constant (eval p 0)

differentiate :: Num a => Poly a -> Poly a

Differentiate a polynomial.

We have dx^n/dx = n·x^(n-1).

differentiate (integrate p) = p
differentiate (p * q) = (differentiate p) * q + p * (differentiate q)

euclidianDivision :: forall a. (Fractional a, Eq a, Ord a) => Poly a -> Poly a -> (Poly a, Poly a)

Euclidian division of polynomials takes two polynomials a and b ≠ 0, and returns two polynomials, the quotient q and the remainder r, such that

a = q * b + r
degree r < degree b

convolve :: (Fractional a, Eq a, Ord a) => (a, a, Poly a) -> (a, a, Poly a) -> [(a, Poly a)]

Convolution of two polynomials defined on bounded intervals. Produces three contiguous pieces as a result.

Numerical

compareToZero :: (Fractional a, Eq a, Ord a) => (a, a, Poly a) -> Maybe Ordering

Measure whether or not a polynomial is consistently above or below zero, or equals zero.

Need to consider special cases where there is a root at a boundary point.

countRoots :: (Fractional a, Ord a) => (a, a, Poly a) -> Int

countRoots (x1, x2, p) returns the number of distinct real roots of the polynomial on the open interval \( (x_1, x_2) \).

(Roots with higher multiplicity are each counted as a single distinct root.)

This function uses Sturm's theorem, with special provisions for roots on the boundary of the interval.

isMonotonicallyIncreasingOn :: (Fractional a, Eq a, Ord a) => Poly a -> (a, a) -> Bool

Check whether a polynomial is monotonically increasing on a given interval.

root :: (Ord a, Num a, Eq a, Fractional a) => a -> a -> (a, a) -> Poly a -> Maybe a

Otherwise we have a polynomial: subtract the value we are looking for so that we seek a zero crossing