Data.Sparse.Polynomial

data Polynomial a

Represents a polynomial by the discrete list of its non-zero terms, stored in a map

• from Int (type of the degree of a term)
• to a (type of the coefficient of a term: integer, real, complex, polynomic ...).

> -- Working with Sparse Polynomials
> import Data.Sparse.Polynomial 
> 
> -- Defining univariate polynomial with concatenation by (<>)
> -- of terms (monoms). Each term has the form: coef ^ degree.
> -- For instance
> 2.0 ^ 3 <> (-3.0) ^ 0
{fromTuples (Tuple 3 2.0)(Tuple 0 -3.0)}

> -- means x↦2x^3 - 3, so applied to 2:
> (2.0 ^ 3 <> (-3.0) ^ 0) :. 2.0
13.0

> -- as expected :-)
>
> -- Polynomials constitute a ring, so usual mathematical operations can 
> -- be performed:
> a = 1 ^ 2 <> 4 ^ 0 -- working with Int here
> b = 1 ^ 1 <> 1 ^ 0
> a+b
{fromTuples (Tuple 2 1)(Tuple 1 1)(Tuple 0 5)}

> a-b
{fromTuples (Tuple 2 1)(Tuple 1 -1)(Tuple 0 3)}

> a*b
{fromTuples (Tuple 3 1)(Tuple 2 1)(Tuple 1 4)(Tuple 0 4)}

> -- Coefficients can be extracted:
> a ? 0
4

> --
> -- When the embedding structure is a field (Rationals, Reals, 
> -- Complex ...), we can divide too 
> import Data.Ratio
> r = (1%9) ^ 2 <> (2%1) ^ 0 -- meaning x↦(1/9) x^2 + 2
> s = (4%1) ^ 1 -- meaning x↦4x
> r/s
{fromTuples (Tuple 1 1 % 36)}

> r `mod` s
{fromTuples (Tuple 0 2 % 1)}

> gcd r s
fromTuples (Tuple 0 2 % 1)
>  
> -- No surprise with differentiation:
> diff $ (2%1)^3<>(-3%1)^1
{fromTuples (Tuple 2 6 % 1)(Tuple 0 -3 % 1)}

> 
> -- Composition is using the (:.) apply operator:
> bThenA = (:.) b >>> (:.) a
> aThenB = (:.) a >>> (:.) b
>
> -- but this time, the application is the usual function application:
> bThenA  1
8

> aThenB 1
6

> 
> -- There is also a useful tool in case of univariate real polynomials:
> pol = 1.0 ^ 2 <> 7.0 ^ 1 <> 12.0 ^ 0
> roots pol
[-2.9999999996605635-3.769201527786494e-10i,
-4.000000000339432+3.769201528752112e-10i]

> -- which gives the approximative values of all the complex roots of the 
> -- polynomial.
> -- Thanks to the sparse nature of the lib, any abuse is permitted :-)
> -- but best results are given when there is no multiple roots
> roots $ 1.0 ^ 16 <> (-1.0) ^ 0
[1.0+0.0i,0.3826834323650897+0.9238795325112867i,
-0.7071067811865476+0.7071067811865476i,
-0.9238795325112871-0.3826834323650901i,
-2.5434386919291434e-12-1.0000000000025875i,
0.9238795325108287-0.382683432364685i,
0.7071067811865476+0.7071067811865476i,
-0.9238795325112867+0.3826834323650898i,
-0.707106781186544-0.7071067811865521i,
0.382683432330398-0.9238795325016941i,
0.7071067812242033-0.7071067811940133i,
2.825247823205539e-19+1.0i,-0.3826834323650898+0.9238795325112867i,
-1.0-1.7156434035577625e-17i,-0.3826834323650554-0.9238795325112262i,
0.9238795325112867+0.3826834323650898i]
 
> -- To Define multivariate polynomials, it's easier with the 
> -- basis 'vectors'.
> -- For instance, with 4 variables x,y,z and t, unity (=1 so 
> -- not a variable!) is
> u = 1 ^ 0 ^ 0 ^ 0 ^ 0
> -- and similarly
> x = 1 ^ 1 ^ 0 ^ 0 ^ 0
> y = 1 ^ 0 ^ 1 ^ 0 ^ 0
> z = 1 ^ 0 ^ 0 ^ 1 ^ 0
> t = 1 ^ 0 ^ 0 ^ 0 ^ 1
> u
{fromTuples (Tuple 0 {fromTuples (Tuple 0 {fromTuples (Tuple 0 
                                            {fromTuples (Tuple 0 1)})})})}

> -- Setters are little more difficult.
> -- As t is the most shallow, it is the easiest
> setT val = (_ :. val)
> setZ val = (<$>) (_ :. val)
> setY val = (<$>) (setZ val)
> setX val = (<$>) (setY val)
> -- but the scheme is general
> pXYZT = x + y*y + z*z*z + t*t*t*t -- meaning (x,y,z,t)↦x+y²+z³+t⁴
>
> setT 0 $ setZ 0 $ setY 0 $ setX 1 pXYZT
1

> setT 0 $ setZ 0 $ setY 2 $ setX 0 pXYZT
4

> setT 0 $ setZ 3 $ setY 0 $ setX 0 pXYZT
27

> setT 4 $ setZ 0 $ setY 0 $ setX 0 pXYZT
256

> setT 4 $ setZ 3 $ setY 2 $ setX 1 pXYZT
288

> -- Coefficients can be extracted but [WARNING], in the reversed
> -- order relative to insertion
> pXYZT T ? 0 ? 0 ? 2 ? 0 -- meaning coefficient of y²
1

Constructors

• Poly (Map Int a)

Instances

• Semigroup (Polynomial a)

  Warning : the 2 appended maps are assumed without common keys and when they aren't, <> is used as the operator of resetting the argument to its right by the argument to its left

• (Eq a) => Eq (Polynomial a)
• Functor Polynomial
• (Eq a, Semiring a) => Semiring (Polynomial a)
• (Eq a, Semiring a, Ring a) => Ring (Polynomial a)
• (Eq a, CommutativeRing a) => CommutativeRing (Polynomial a)
• (Eq a, DivisionRing a, CommutativeRing a) => EuclideanRing (Polynomial a)

  Warning : prelude's gcd will not work as the condition degree = 0 is not sufficient to stop the recursion asking for value = 0

• (Ord a, Eq a, CommutativeRing a) => Ord (Polynomial a)
• (Show a) => Show (Polynomial a)

class IntLiftable a  where

Members

• fromInt :: Int -> a

Instances

• IntLiftable Int
• IntLiftable Number
• (Semiring a, Ring a, IntLiftable a) => IntLiftable (Cartesian a)
• (Ord a, IntLiftable a, EuclideanRing a) => IntLiftable (Ratio a)

applyPoly :: forall a. Semiring a => Polynomial a -> a -> a

Polynomial application

bezout :: forall a. Eq a => CommutativeRing a => DivisionRing a => Polynomial a -> Polynomial a -> { u :: Polynomial a, v :: Polynomial a }

Find 2 polynomials u and v such that u p1 + v p2 == gcd (p1,p2)

derivative :: forall a. Eq a => Semiring a => (Int -> a) -> Polynomial a -> Polynomial a

diff :: forall a. Eq a => Ord a => Semiring a => EuclideanRing a => IntLiftable a => Polynomial a -> Polynomial a

Univariate polynomial differentiation

dominantMonom :: forall a. Eq a => Semiring a => Polynomial a -> Tuple Int a

Leading term

gcd :: forall a. Eq a => DivisionRing a => CommutativeRing a => Polynomial a -> Polynomial a -> Polynomial a

Greatest common divisor of 2 univariate polynomials

liftC :: Polynomial Number -> Polynomial (Cartesian Number)

Transforms a polynomial with real arguments into a polynomial with complex arguments

monoPol :: forall a. a -> Int -> Polynomial a

Monoterm polynomial

pow :: forall a. Semiring a => a -> Int -> a

Integer power

query :: forall a. Semiring a => Polynomial a -> Int -> a

Coefficient extraction

roots :: Polynomial Number -> Array (Cartesian Number)

Returns the n approximative roots of a polynomial of degree n

sortedMonoms :: forall a. Polynomial a -> Array (Tuple Int a)

Dispatches the terms in list of tuples (degree,coefficient) and order it by decreasing degree

Operator alias for Data.Sparse.Polynomial.applyPoly (left-associative / precedence 5)

Polynomial application infix notation

Operator alias for Data.Sparse.Polynomial.query (left-associative / precedence 8)

Coefficient extraction infix notation

Operator alias for Data.Sparse.Polynomial.monoPol (left-associative / precedence 8)

Monoterm polynomial infix notation