Copyright	(c) Ross Paterson 2011
License	BSD-style (see the file LICENSE)
Maintainer	[email protected]
Stability	provisional
Portability	portable
Safe Haskell	None
Language	Haskell2010

Data.YAP.Polynomial

Contents

Polynomials
Queries
Composition
- Special compositions

Description

An example instance of the algebraic classes: formal polynomials.

Synopsis

data Polynomial a
constant :: a -> Polynomial a
linear :: AdditiveMonoid a => a -> Polynomial a
fromCoefficients :: [a] -> Polynomial a
fromRoots :: Ring a => [a] -> Polynomial a
type RationalFunction a = Ratio (Polynomial a)
degree :: (Eq a, AdditiveMonoid a) => Polynomial a -> Int
coefficients :: (Eq a, AdditiveMonoid a) => Polynomial a -> [a]
unsafeCoefficients :: Polynomial a -> [a]
evaluate :: Semiring a => Polynomial a -> a -> a
evaluateWith :: (Semiring b, AdditiveMonoid c) => (a -> b -> c) -> Polynomial a -> b -> c
pretty :: ToInteger a => Polynomial a -> String -> String
identity :: Semiring a => Polynomial a
compose :: Semiring a => Polynomial a -> Polynomial a -> Polynomial a
(.*) :: Semiring a => Polynomial a -> a -> Polynomial a
(.^) :: AdditiveMonoid a => Polynomial a -> Int -> Polynomial a

Polynomials

data Polynomial a Source #

Formal polynomials.

Instances

Instances details

AdditiveFunctor Polynomial Source #
Instance details Defined in Data.YAP.Polynomial Methods mapAdditive :: (AdditiveMonoid a, AdditiveMonoid b) => (a -> b) -> Polynomial a -> Polynomial b #
(Eq a, Show a, AdditiveMonoid a) => Show (Polynomial a) Source #
Instance details Defined in Data.YAP.Polynomial Methods showsPrec :: Int -> Polynomial a -> ShowS # show :: Polynomial a -> String # showList :: [Polynomial a] -> ShowS #
(Eq a, AdditiveMonoid a) => Eq (Polynomial a) Source #
Instance details Defined in Data.YAP.Polynomial Methods (==) :: Polynomial a -> Polynomial a -> Bool # (/=) :: Polynomial a -> Polynomial a -> Bool #
(Ord a, AdditiveMonoid a) => Ord (Polynomial a) Source #
Instance details Defined in Data.YAP.Polynomial Methods compare :: Polynomial a -> Polynomial a -> Ordering # (<) :: Polynomial a -> Polynomial a -> Bool # (<=) :: Polynomial a -> Polynomial a -> Bool # (>) :: Polynomial a -> Polynomial a -> Bool # (>=) :: Polynomial a -> Polynomial a -> Bool # max :: Polynomial a -> Polynomial a -> Polynomial a # min :: Polynomial a -> Polynomial a -> Polynomial a #
Semiring a => Differentiable (Polynomial a) Source #
Instance details Defined in Data.YAP.Polynomial Methods derivative :: Polynomial a -> Polynomial a #
FromRational a => Integrable (Polynomial a) Source #
Instance details Defined in Data.YAP.Polynomial Methods integral :: Polynomial a -> Polynomial a #
AbelianGroup a => AbelianGroup (Polynomial a) Source #
Instance details Defined in Data.YAP.Polynomial Methods (-) :: Polynomial a -> Polynomial a -> Polynomial a # negate :: Polynomial a -> Polynomial a # gtimes :: (AbelianGroup b, ToInteger b) => b -> Polynomial a -> Polynomial a #
AdditiveMonoid a => AdditiveMonoid (Polynomial a) Source #
Instance details Defined in Data.YAP.Polynomial Methods (+) :: Polynomial a -> Polynomial a -> Polynomial a # zero :: Polynomial a # atimes :: ToInteger b => b -> Polynomial a -> Polynomial a #
(Eq a, Field a) => Euclidean (Polynomial a) Source #	If `b` is non-zero, `mod a b` has a smaller degree than `b`.
Instance details Defined in Data.YAP.Polynomial Methods div :: Polynomial a -> Polynomial a -> Polynomial a # mod :: Polynomial a -> Polynomial a -> Polynomial a # divMod :: Polynomial a -> Polynomial a -> (Polynomial a, Polynomial a) # euclideanNorm :: Polynomial a -> Natural #
FromRational a => FromRational (Polynomial a) Source #
Instance details Defined in Data.YAP.Polynomial Methods fromRational :: Rational -> Polynomial a #
Ring a => Ring (Polynomial a) Source #
Instance details Defined in Data.YAP.Polynomial Methods fromInteger :: Integer -> Polynomial a #
Semiring a => Semiring (Polynomial a) Source #
Instance details Defined in Data.YAP.Polynomial Methods (*) :: Polynomial a -> Polynomial a -> Polynomial a # one :: Polynomial a # fromNatural :: Natural -> Polynomial a # rescale :: Polynomial a -> Polynomial a -> (Polynomial a, Polynomial a, Polynomial a -> Polynomial a) #
(Eq a, Field a) => StandardAssociate (Polynomial a) Source #	Units are non-sero constants. If `p` is non-zero, `stdUnit p` is the leading coefficient of `p` and `stdAssociate p` is monic (i.e. has a leading coefficient of `1`).
Instance details Defined in Data.YAP.Polynomial Methods stdAssociate :: Polynomial a -> Polynomial a # stdUnit :: Polynomial a -> Polynomial a # stdRecip :: Polynomial a -> Polynomial a #
(Prime p, KnownNat k, KnownNat (ConwayEncoded p k)) => FiniteField (PrimePower p k) Source #
Instance details Defined in Data.YAP.Quotient Methods primitiveElement :: PrimePower p k Source #

constant :: a -> Polynomial a Source #

Polynomial representing a constant value c

linear :: AdditiveMonoid a => a -> Polynomial a Source #

Linear polynomial, i.e. constant a * identity

fromCoefficients :: [a] -> Polynomial a Source #

Construct a polynomial from a list of coefficients, least significant first.

fromRoots :: Ring a => [a] -> Polynomial a Source #

A monic polynomial with the given roots (with multiplicity)

type RationalFunction a = Ratio (Polynomial a) Source #

A rational function with coefficients from a field is a field

Queries

degree :: (Eq a, AdditiveMonoid a) => Polynomial a -> Int Source #

The degree of a polynomial: the highest power of the indeterminate.

coefficients :: (Eq a, AdditiveMonoid a) => Polynomial a -> [a] Source #

The coefficients of a polynomial, least significant first and with no trailing zeros.

unsafeCoefficients :: Polynomial a -> [a] Source #

The coefficients of a polynomial, least significant first and with an arbitrary number of trailing zeros. This is only safe to use in contexts where the number of trailing zeros is immaterial.

evaluate :: Semiring a => Polynomial a -> a -> a Source #

Evaluate a polynomial for a given value of x.

evaluate a x = zipWith (*) (coefficients a) (iterate (*x) 1)

(The implementation uses Horner's rule.)

evaluateWith :: (Semiring b, AdditiveMonoid c) => (a -> b -> c) -> Polynomial a -> b -> c Source #

Evaluate a polynomial for a given value of x, using the given function to combine coefficients and powers.

pretty :: ToInteger a => Polynomial a -> String -> String Source #

Pretty-print a polynomial, e.g.

pretty (fromCoefficients [3, -4, 0, -1, 5]) "x" = "5x^4 - x^3 - 4x + 3"

Composition

identity :: Semiring a => Polynomial a Source #

Identity polynomial, i.e. x

compose :: Semiring a => Polynomial a -> Polynomial a -> Polynomial a Source #

Composition of polynomials:

evaluate (compose a b) = evaluate a . evaluate b

Special compositions

(.*) :: Semiring a => Polynomial a -> a -> Polynomial a infixl 9 Source #

Maps a function \(f(x)\) to \(f(a x)\), equivalent to composition with a*identity.

(.^) :: AdditiveMonoid a => Polynomial a -> Int -> Polynomial a infixl 9 Source #

Maps a function \(f(x)\) to \(f(x^k)\) for positive \(k\), equivalent to composition with identity^k.