poly-0.3.1.0: Polynomials

Copyright(c) 2019 Andrew Lelechenko
LicenseBSD3
MaintainerAndrew Lelechenko <andrew.lelechenko@gmail.com>
Safe HaskellNone
LanguageHaskell2010

Data.Poly.Semiring

Contents

Description

Dense polynomials and a Semiring-based interface.

Synopsis

Documentation

data Poly v a Source #

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, Eq (v a), Ring a, GcdDomain a, Fractional a, Vector v a) => GcdDomain (PolyOverFractional (Poly v a)) Source # 
Instance details

Defined in Data.Poly.Internal.PolyOverFractional

(Eq a, Eq (v a), Ring a, GcdDomain a, Fractional a, Vector v a) => Euclidean (PolyOverFractional (Poly v a)) Source # 
Instance details

Defined in Data.Poly.Internal.PolyOverFractional

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

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

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

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 #

(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 a, Ring a, GcdDomain a, Eq (v a), Vector v a) => GcdDomain (Poly v a) Source #

Consider using PolyOverFractional wrapper, which provides a much faster implementation of gcd for Fractional coefficients.

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, Eq (v a), Ring a, GcdDomain a, Fractional a, Vector v a) => Euclidean (Poly v a) Source # 
Instance details

Defined in Data.Poly.Internal.Dense.Fractional

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

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

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.

type UPoly = Poly Vector Source #

Polynomials backed by unboxed vectors.

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

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

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

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

Semiring interface

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

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

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

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

Create an identity polynomial.

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

Evaluate at a given point.

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

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

Take a derivative.

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

Fractional coefficients

newtype PolyOverFractional poly Source #

Wrapper over polynomials, providing a faster GcdDomain instance, when coefficients are Fractional.

Constructors

PolyOverFractional 

Fields

Instances
Eq poly => Eq (PolyOverFractional poly) Source # 
Instance details

Defined in Data.Poly.Internal.PolyOverFractional

Num poly => Num (PolyOverFractional poly) Source # 
Instance details

Defined in Data.Poly.Internal.PolyOverFractional

Ord poly => Ord (PolyOverFractional poly) Source # 
Instance details

Defined in Data.Poly.Internal.PolyOverFractional

Show poly => Show (PolyOverFractional poly) Source # 
Instance details

Defined in Data.Poly.Internal.PolyOverFractional

(Eq a, Eq (v a), Ring a, GcdDomain a, Fractional a, Vector v a) => GcdDomain (PolyOverFractional (Poly v a)) Source # 
Instance details

Defined in Data.Poly.Internal.PolyOverFractional

(Eq a, Eq (v a), Ring a, GcdDomain a, Fractional a, Vector v a) => Euclidean (PolyOverFractional (Poly v a)) Source # 
Instance details

Defined in Data.Poly.Internal.PolyOverFractional

Semiring poly => Semiring (PolyOverFractional poly) Source # 
Instance details

Defined in Data.Poly.Internal.PolyOverFractional

Ring poly => Ring (PolyOverFractional poly) Source # 
Instance details

Defined in Data.Poly.Internal.PolyOverFractional