Data.Poly.Semiring

Dense polynomials and a Semiring-based interface.

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

Ord instance does not make much sense mathematically, it is defined only for the sake of Set, Map, etc.

Instances

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

Defined in Data.Poly.Internal.Dense

Associated Types

type Item (Poly v a) :: Type

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

(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

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

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

Defined in Data.Poly.Internal.Dense

Methods

rnf :: Poly v a -> ()

(Eq a, Ring a, GcdDomain a, Vector v a) => GcdDomain (Poly v a)

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

Note that degree 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, Semiring a, Vector v a) => Semiring (Poly v a)

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

(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

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.

type UPoly = Poly Vector

Polynomials backed by unboxed vectors.

unPoly :: Poly v a -> v a

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

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

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

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

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

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

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

Create a monomial from a power and a coefficient.

scale :: (Eq a, Semiring 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

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

Create an identity polynomial.

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

Evaluate at a given point.

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

subst :: (Eq a, Semiring 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

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

Take a derivative.

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

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

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

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

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

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

dft

Arguments

:: (Ring a, Vector v a)

=> a

primitive root \( \sqrt[N]{1} \), otherwise behaviour is undefined

-> v a

\( \{ x_k \}_{k=0}^{N-1} \) (currently only \( N = 2^n \) is supported)

-> v a

\( \{ y_k \}_{k=0}^{N-1} \)

Discrete Fourier transform \( y_k = \sum_{j=0}^{N-1} x_j \sqrt[N]{1}^{jk} \).

inverseDft

Arguments

:: (Field a, Vector v a)

=> a

primitive root \( \sqrt[N]{1} \), otherwise behaviour is undefined

-> v a

\( \{ y_k \}_{k=0}^{N-1} \) (currently only \( N = 2^n \) is supported)

-> v a

\( \{ x_k \}_{k=0}^{N-1} \)

Inverse discrete Fourier transform \( x_k = {1\over N} \sum_{j=0}^{N-1} y_j \sqrt[N]{1}^{-jk} \).

dftMult

Arguments

:: (Eq a, Field a, Vector v a)

=> (Int -> a)

mapping from \( N = 2^n \) to a primitive root \( \sqrt[N]{1} \)

-> Poly v a

-> Poly v a

-> Poly v a

Multiplication of polynomials using discrete Fourier transform. It could be faster than '(*)' for large polynomials if multiplication of coefficients is particularly expensive.