Data.Sparse.Polynomial

newtype Polynomial a

Represents a non-null 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 ...).

and a null polynomial by the empty map.

> -- Working with Sparse Polynomials
> import Data.Sparse.Polynomial 
 
> -- Defining univariate polynomial
> -- ------------------------------
>
> --  * by concat / reset with (<>) [see Semigroup instance note] or
> --  * by summation with (+) and (-)
>
> -- of terms (monoms). Each term has the form: coef ^ degree.
> -- For instance
>
> display ["x"] $ 2.0 ^ 3 <> (-4.0) ^ 0
"(2.0)×x^3+(-4.0)"
>
> 2.0 ^ 3 <> (-4.0) ^ 0
(2.0)×x^3+(-4.0)
>
> display ["z"] $ 2.0 ^ 3 + (-4.0) ^ 0
"(2.0)×z^3+(-4.0)"
>
> -- displays (with variable "x" by default) the polynomial 
> -- that subtract 4 from the double of the cube, 
> -- so evaluated at 5 with the (:.) evaluation operator:
>
> (2.0 ^ 3 <> (-4.0) ^ 0) :. 5.0
246.0
>
> -- or with `xpose`, its flipped version:
>
> 5.0 `xpose` (2.0 ^ 3 <> (-4.0) ^ 0)
246.0
>
> -- without having to specify the variable name.


> -- Polynomials constitute a Ring, so usual mathematical operations can 
> -- be performed:
> 
> a = 1 ^ 2 <> 4 ^ 0 -- working with Int as the underlying structure
>                    -- here 
> b = 1 ^ 1 <> 1 ^ 0
> 
> a
(1)×x^2+4
> 
> b
(1)×x+1
> 
> a+b
(1)×x^2+(1)×x+5
>
> a-b
(1)×x^2+(-1)×x+3
>
> a*b
(1)×x^3+(1)×x^2+(4)×x+4

> -- Composition is using the (.-) substitution operator:
>
> aAfterB = a .- b
> aAfterB
(1)×x^2+(2)×x+5
>
> b .- a
(1)×x^2+5
>
> -- or `xpand`, its flipped version:
>
> bThenA = b `xpand` a
> bThenA
(1)×x^2+(2)×x+5
>
> a `xpand` b
(1)×x^2+5


> -- Coefficients can be extracted with the (!) query operator :
> a ! 0
4


> -- When the underlying structure is a Division ring (Rationals, Reals, 
> -- Complex, or any other field), we can divide too. (Technically, when
> -- the underlying structure is only a Euclidean ring -- like  Int --,
> -- the algorithm works when the rest is null and occasionnally loops
> -- forever if not.)
>
> 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
(1 % 36)×x
>
> r `mod` s
2 % 1
>
> gcd r s
32 % 1
>
> -- [WARNING] the implemented gcd is designed to be useful 
> -- for non-constant polynomials modulo some scaling factor.
> -- This has 2 major consequences :
>
> -- 1) `Prelude.gcd a b` is generally _different_ from 
> --    `Data.Sparse.Polynomial.gcd (a^0) (b^0)`
> --    because the scaling factor is left unchanged 
> --    at the end of the algorithm (see gcd's comment)
> -- 2) Little Bézout's theorem doesn't hold : for any two multivariate
> --    polynomials P and Q, it's _not_ always possible to find two
> --    polynomials U and V, and a ring element r such that
> --    U×P + V×Q = r GCD(P,Q).
> --    [Consider P(X,Y)=X, Q(X,Y)=Y then no (U,V) possible
> --    since GCD(P,Q)=1]


> -- No surprise with differentiation:
> diff $ (2%1)^3<>(-4%1)^1
(6 % 1)×x^2+(-4 % 1)


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

> ------------------------------------
> --                                --
> -- ABOUT MULTIVARIATE POLYNOMIALS --
> --                                --
> --           -------              --
> --          |  API  |             --
> --           -------              --
> ------------------------------------

> --    This set of notes shows several uses of the functions
> --    performing  multivariate polynomial manipulation provided 
> --    by this library, along with (^) and (!) : 
> --
> --     * `set`,  for evaluation and arity decrease, more efficient 
> --               but demanding than
> --     * `fill`, for substitution (or `full` for full evaluation)
> --               where arity is conserved.
> --
> --    Then, two functions are provided to increase arity :
> --     * `pad`,  rather coarse, useful in particular
> --               with numerical constants, and
> --     * `nest`, for more specific uses.
> --
> --    The inverse of `pad`  :
> --     * `unpad`, carelessly decreases arity.
> --
> --    Finally, one function makes variable changes :
> --     * the `swap` function,
> --
> --    and one function extracts the constant coefficient
> --    of any polynomial :
> --     * the `peel` function.
> --
> --    See documentation of each function for more specifications. 


> -- 1) DEFINITION : There are (at least) three possible 
> --    ----------   and equivalent ways to define multivariate
> --                 polynomials with this library:

> --    a) By using a sum of terms where each term is defined with 
> --       the enumerative representation "n ^ ... ^ e_Z ^ e_Y ^ e_X",
> --       generalizing the construction seen with univariate polynomials
> --       where n is an element of the underlying structure and the e_i, 
> --       of type Int, correspond to respective variable's degrees.
>
> 3^0^2
(3)×x^2
>
> 4^1^1^0
((4)×z)×y
>
> 3^0^0^0^2 + 4^0^1^1^0 + 5^1^0^0^0
(3)×x^2+((4)×z)×y+(5)×t

> --    b) By using
> --       * the basis axes where each axis (aka term that embodies
> --         a variable) is defined with the enumerative representation,
> --         and
> --       * a wrapping function that lifts the constant numeric values
> --         (refered as n in a))  to the required (multivariate) 
> --         polynomial type (see the `axes`  function).
> --        
>
> -- For instance, with arity = 4 and Int as the underlying structure :
>
> x = 1^0^0^0^1
> y = 1^0^0^1^0
> z = 1^0^1^0^0
> t = 1^1^0^0^0
> kst v = v^0^0^0^0 
>
> kst 3*x*x + kst 4*y*z + kst 5*t 
(3)×x^2+((4)×z)×y+(5)×t

> --    Note that, in the enumerative representation of a term, the 
> --    positions of the exponents listed from left to right were 
> --    designed to be of decreasing proximity (i.e of decreasing 
> --    technical accessibility) so that the righter the position 
> --    of a 1, the more remote and more difficult to access.
> --    In other words, if an integer is associated with the proximity of
> --    a term, and if `@` is the function returning that integer,
> --    
> --    @(x) < @(y) < ... < @(nearest) < @(kst one).
> --
> --    In addition, this library has been built, for any arity,
> --    following these four principles : 
> --
> --     * the proximity of two consecutive axes defer by 1,
> --     * the proximity of the most remote axis ("x") is set to 0,
> --     * thus, the proximity of the most accessible (aka nearest) axis
> --       is set to arity-1,
> --     * and the constant terms (like `kst one`) are more accessible 
> --       than any other axis.

> --    This leads to the preferred third option:

> --    c) By using 
> --     * proximity of axes, 
> --     * `one^1`, the _univariate_ axis, and
> --     * `pad` and `swap` functions : 
>
> --========= DEFINING SCHEME FOR ANY ARITY > 1 (arity=4 here) ==========
>              ---------------------------------                                                 
>
>                     -- *) Keep the 0, 1, .., arity-1 sequence in mind
>                           as the x, y, .., t sequence of axes.
>
> kst = pad @3        -- *) Define the wrapping function = pad @(arity-1)
>
>                     -- *) Choose a underlying structure to define `one`
>                     --    then :
> t = pad @2 (1^1)    --    Nearest axis = pad @(arity-2) $ one^1
>
>                     -- *) Other axis =
> x = swap @0 @3 t    --      swap @self @(arity-1) $ nearest axis
> y = swap @1 @3 t    --    ...
> z = swap @2 @3 t    --    ...
> ...                 --    ...
> --=====================================================================
>
> kst 3*x*x + kst 4*y*z + kst 5*t          
(3)×x^2+((4)×z)×y+(5)×t

> --     ------------------------------
> --    | Using `pad` increases arity. |
> --     ------------------------------

> -- Note that, for arity=1, `kst = pad @0` and `x = one^1`.

> -- 2) DISPLAY : By defaut, the first 4 variables are printed with the 
> --    -------
> --    "x","y","z" and "t" strings in that order, but, for five
> --    or more variables, the variables names are proximity-indexed
> --    versions of "x".
> --    So,
>
> display ["a","b","c"] $ 2^0^0^0 + 4^0^1^0
> --    returns
"(4)×b+2"
> --    whereas
> 2^0^0^0 + 4^0^1^0
> --    displays
(4)×y+2
> --    and
> 2^0^0^0^0^0 + 4^0^0^0^1^0
> --    displays
(4)×x1+2


> -- 3) EVALUATION : A multivariate polynomial, say with arity = 4 
> --    ----------   for instance, like
>
> p = kst 2 * x - y * y + z * z * t - z * t * t
> p
(2)×x+((-1))×y^2+((1)×t)×z^2+((-1)×t^2)×z
>
> --    has been modeled in this library as
> --    a polynomial in x whose coefficients are
> --    polynomials in y whose coefficients are
> --    polynomials in z whose coefficients are
> --    polynomials in t whose coefficients are numbers
> --    (in other words, polynomials in the most accessible variable
> --    are univariate polynomials).

> --    As a consequence, if we evaluate (`set`) the t-component of p
> --    at a constant value,
> 
> 4 `set @3` p
(2)×x+((-1))×y^2+(4)×z^2+(-16)×z
>
> :t 4 `set @3` p
Polynomial (Polynomial (Polynomial Int))
>
> --    we get the same 3-variate polynomial as if we substitute (`fill`)
> --    the t variable with the corresponding constant polynomial :
> 
> kst 4 `fill @3` p
(2)×x+((-1))×y^2+(4)×z^2+((-16))×z
>
> --    However, with `fill`, the result is in the same scope 
> --    as p (where arity = 4).
>
> :t kst 4 `fill @3` p
Polynomial (Polynomial (Polynomial (Polynomial Int)))

> --     -------------------------------------
> --    | Using `set` _does_ decrement arity, |
> --    | using `fill` does not change arity. |
> --     -------------------------------------

> --    This is a desired behavior because `set` consumes all occurrences 
> --    of a variable so the loss of one unit of arity only reflects
> --    the saved space. On the other hand, with `fill`, all occurrences 
> --    of the replaced variable are consumed as well but replacements 
> --    variables  may include the replaced variable itself (which is
> --    not possible with `set`), so arity is not expected to be 
> --    decreased mecanically in this case.

> --    Here are all the ways to define
> --
> --             q(x,y) = p(x,y,3,4) = (2)×x+(-1)×y^2+(-12)
> --
> --    from p(x,y,z,t) :
>
> --    (xtend = pad @0 : convert a number
> --    to the corresponding univariate constant polynomial)
>
> 3 `set @2` (4 `set @3` p)                -- output arity = 2
> 4 `set @2` (xtend 3 `set @2` p)          -- output arity = 2
> xtend 3 `set @2` (kst 4 `fill @3` p)     -- output arity = 3
> 4 `set @3` (kst 3 `fill @2` p)           -- output arity = 3
> pad @2 3 `fill @2` (4 `set @3` p)        -- output arity = 3
> pad @2 4 `fill @2` (xtend 3 `set @2` p)  -- output arity = 3
> kst 3 `fill @2` (kst 4 `fill @3` p)      -- output arity = 4
> kst 4 `fill @3` (kst 3 `fill @2` p)      -- output arity = 4


> --    Notice that using `set` requires to be careful about the types of 
> --    the provided arguments. This is the first reason `set` is
> --    more demanding to use than `fill`.

> --    Ultimately, the easiest ways to fully evaluate a polynomial 
> --    (numerical result of q(1,2) with arity 0 after all partial 
> --    partial evaluations performed), are either with `set`,
> --    providing the values _in_order_

> set @0 1 $ set @1 2 $ set @2 3 $ set @3 4 p
-14

> --    or with `fill`, providing constant polynomials in any order 
> --    (techically, the result is still a polynomial whose constant 
> --    value can be extracted with `peel`) :

> fill @3 (kst 4) $ fill @0 (kst 1) $ fill @2 (kst 3) $ fill @1 (kst 2) p
-14

> --    or with `full`, a 'saturated' version of `fill` where values have
> --    to be provided in order, this time :

> peel $ map kst [1,2,3,4] `full` p
-14


> --    Similarly, when evaluating the z-component of p at a non-constant
> --    univariate polynomial, it is implicitely expressed in t, 
> --    in respect of the type of the coefficients of the z-component :
>
> pz = (2^1-5^0) `set @2` p
> pz
(2)×x+((-1))×y^2+(2)×z^3+(-15)×z^2+(25)×z
>
> --    Even if any t doesn't seem to be introduced, this expression is 
> --    expected because of the way `set` works : after having been 
> --    replaced with a t expression, each occurrence of z in p has 
> --    vanished. The empty z-slot is vacant, and since t follows z 
> --    by order of proximity, t-content earns an order
> --    of remoteness and everything looks like t has been renamed z. 
> --    As a check, the fact that the same polynomial is obtained when  
> --    filling z with the corresponding polynomial in t should
> --    convince that the expression of pz is right :
> --    
> 
> pt = (kst 2 * t - kst 5) `fill @2` p
> pt
(2)×x+((-1))×y^2+(2)×t^3+(-15)×t^2+(25)×t

> --    This odd process is the second reason `set` is more demanding
> --    than `fill`. In addition, note that, with `fill`, the replacement 
> --    polynomial can include any variable, unlike with `set` where
> --    replacement variables are always stricly more accessible 
> --    than the replaced one :
> 
> (kst 2 * z - kst 5 * y ) `fill @2` p
(2)×x+((25)×t+(-1))×y^2+(((-20)×t)×z+(5)×t^2)×y+((4)×t)×z^2+((-2)×t^2)×z


> --    When needed, it is possible to change pt to pz by evaluating 
> --    the z-component of pt at any polynomial with right arity (say  
> --    zero). Indeed, the empty content associated with z gets removed
> --    since `set` decrements arity and the content associated with t
> --    is shifted one step more remote and gets associated with z,
> --    as already stated.
> 
> zero `set @2` pt
(2)×x+((-1))×y^2+(2)×z^3+(-15)×z^2+(25)×z

> --    It is conceptually easier to change pz to pt, by substituting z 
> --    with t, as long as we use a version of pz with arity at least 4 
> --    because the use of `fill` requires its two arguments of the same
> --    arity :
> --    Note that the `pad` function can't be used to change arity here
> --    since it shifts all the axes several times, unlike the `nest` 
> --    function which shifts several chosen axes once  : 
> --    
> 
> t `fill @2` (nest @2 pz)
(2)×x+((-1))×y^2+(2)×t^3+(-15)×t^2+(25)×t
>
> --     --------------------------------
> --    | Using `nest` increments arity. |
> --     --------------------------------

> --    This method can be used to change pt to pz as well
> --    (arity won't match though, `set @3 zero` would fix that)

> z `fill @3` pt
(2)×x+((-1))×y^2+(2)×z^3+((-15))×z^2+(25)×z


> --    There is another way to change pt to pz using 
> --    a function that unconditionnally swaps two axes
> --    (and keeps scope).
>
> swap @2 @3 pt
(2)×x+((-1))×y^2+(2)×z^3+((-15))×z^2+(25)×z

> --     --------------------------------------
> --    | Using `swap` does not change arity. |
> --     --------------------------------------

> --    Finally, it is possible to `swap` pz to pt too, but
> --    pz's arity is only 3, so swaping z and t requires to `nest`
> --    a t-slot beforehand just like in one of the preceeding examples
>
> swap @2 @3 $ nest @3 pz
(2)×x+((-1))×y^2+(2)×t^3+(-15)×t^2+(25)×t
>
> --    and a simpler way is to just `nest` a z-slot, thanks to the fact
> --    that `nest` shifts all previous z content on step nearer, to t:
>
> nest @2 pz
(2)×x+((-1))×y^2+(2)×t^3+(-15)×t^2+(25)×t


> --    Notation used in the documentation of the manipulation functions
> --    ----------------------------------------------------------------
> --    P : natural number reflecting the arity of the polynomial
> --    P = 0 for the elements of the underlying structure
> --    P = 1 for univariate polynomials
> --    P = 2 for bivariate polynomials and more generally,
> --          multivariate polynomials are P-variate.


> -- 4) COEFFICIENT EXTRACTION :
> --    ----------------------
> --
> -- coefficient of zt², beware, orders ...
> let p = 10^0^0^1^2 + 20^1^2^0^0 + 42^2^1^0^0 in p ! 0 ! 0 ! 1 ! 2
42

Constructors

• Poly (Map Int a)

Instances

• Pad 0 a (Polynomial a)
• (Pad n1 a b, Add n1 1 n) => Pad n a (Polynomial b)
• (Unpad n (Polynomial (Polynomial a)) b, Add n 1 n1, Semiring a, Eq a) => Unpad n1 (Polynomial a) b
• (Eq a, Semiring a) => 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, Semiring a) => Monoid (Polynomial a)
• (Set n1 a b, Add n1 1 n, Semiring a) => Set n a (Polynomial b)
• (FillValid n1 a, Eq a, Semiring a, Add n1 1 n) => FillValid n (Polynomial a)
• (Eq a) => Eq (Polynomial a)
• Functor Polynomial
• (Eq a, Semiring a) => Semiring (Polynomial a)
• (Eq a, Ring a) => Ring (Polynomial a)
• (Eq a, Ring a) => CommutativeRing (Polynomial a)
• (Eq a, Leadable a, Semiring a) => Leadable (Polynomial a)
• (Semiring a, Divisible a) => Divisible (Polynomial a)
• (Eq a, Divisible a, Ring a, Leadable 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, Divisible a, Leadable a, CommutativeRing a, EuclideanRing a, Primitivable a) => Primitivable (Polynomial a)
• (Ord a, Eq a, CommutativeRing a) => Ord (Polynomial a)
• Univariate (Polynomial (Polynomial a))
• (Arity (Polynomial a) n1, Add n1 1 n) => Arity (Polynomial (Polynomial a)) n
• Arity (Polynomial a) 1
• (Peel a b, Eq a, Semiring a) => Peel (Polynomial a) b
• (Axed a r, Semiring a, Peel a r) => Axed (Polynomial a) r
• (Nest n1 a, Add n1 1 n) => Nest n (Polynomial a)
• (SwapAdjacent n1 a, Semiring a, Add n1 1 n) => SwapAdjacent n (Polynomial a)
• (Display a, Ord a, Semiring a) => Display (Polynomial a)
• (Display a, Ord a, Semiring a) => Show (Polynomial a)
• (Eq a, IntLiftable a, Semiring a) => IntLiftable (Polynomial a)

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

Monoterm polynomial

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

Monoterm polynomial infix notation

class NextAxis :: Int -> Int -> Constraintclass NextAxis a n | a -> n, n -> a where

Members

• nextAxis :: Proxy a -> Proxy n
• prevAxis :: Proxy n -> Proxy a

Instances

• (Add a 1 n) => NextAxis a n

class Pad :: Int -> Type -> Type -> Constraintclass Pad n a b | n a -> b where

> --     ---------------------------------------------------
> --    | PAD : the lifting function that introduces        |
> --    | ---                                               |
> --    | in a polynomial as many new variables as 1 + the  |
> --    | provided size, shifting the content of each       |
> --    | of the initial variables as many orders nearer.   |
> --     ---------------------------------------------------
> --    | input : polynomial |
> --     ----------------------------------------------------
> --    |                            |    arity  |  arity    |
> --    |           usage            |    input  |  output   |
> --    |                            |           |           |
> --     ====================================================
> --    |         pad @size          |    P>=0   |  P+size+1 |
> --     ----------------------------------------------------

> pad @0 5
5

> pad @0 (5^0)
5

> pad @0 (5^1)
(5)×y

> pad @1 (5^0)
5

> pad @1 (5^1)
(5)×z

> pad @1 (5^1^1)
((5)×t)×z

Members

• _pad :: Proxy n -> a -> b

Instances

• Pad 0 a (Polynomial a)
• (Pad n1 a b, Add n1 1 n) => Pad n a (Polynomial b)

pad :: forall @n a b. Pad n a b => a -> b

class Unpad :: Int -> Type -> Type -> Constraintclass Unpad n a b | n b -> a where

> --     -----------------------------------------------------
> --    | UNPAD : the inverse of `pad` that decreases the     |
> --    | -----                                               |
> --    | arity of a polynomial of 1 + the                    |
> --    | provided size, shifting the content of each         |
> --    | of the initial variables to a more remote position. |
> --     -----------------------------------------------------
> --    | input : polynomial |
> --     ------------------------------------------------------
> --    |                            |    arity    |  arity    |
> --    |             usage          |    input    | output    |
> --    |                            |             |           |
> --     ======================================================
> --    |          unpad @size       | P >= 2+size | P-size-1  |
> --     ------------------------------------------------------

> unpad @0 (5^1^1 + 6^1^0)
(6)×x

> unpad @1 (5^1^1^0 + 6^1^0^0 + 7^0^0^0)
(6)×x+7

Members

• _unpad :: Proxy n -> b -> a

Instances

• (Semiring a) => Unpad -1 a a
• (Unpad n (Polynomial (Polynomial a)) b, Add n 1 n1, Semiring a, Eq a) => Unpad n1 (Polynomial a) b

unpad :: forall @n a b. Unpad n a b => b -> a

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

Coefficient extraction

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

Coefficient extraction infix notation

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

Integer power

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

Univariate polynomial evaluation

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

Univariate polynomial evaluation infix notation

class Set :: Int -> Type -> Type -> Constraintclass Set n a b | n b -> a where

> --     ---------------------------------------------------------
> --    | SET : the evaluating function that removes the variable |
> --    | ---                                                     |
> --    | at focus in a polynomial by setting it to the provided  |
> --    | value, and shifts the content of each of the other      |      
> --    | nearer variables and associates it to the variable      |
> --    | one order more remote.                                  |
> --     ---------------------------------------------------------
> --    | input1 : value || input2 : polynomial |
> --     ---------------------------------------------------
> --    |    arity    |               |    arity   |  arity |
> --    |    input1   |     `usage`   |   input2   = output |
> --    |             |               |            |        |
> --     ===================================================
> --    | P-(focus+1) |  `set @focus` |   P>focus  =   P-1  |
> --     ----------------------------------------------------

> 1^0^0^1 + 2^1^3^0
(1)×x+((2)×z)×y^3

> (5^0^0) `set @0` (1^0^0^1 + 2^1^3^0)
((2)×y)×x^3+5

> (5^1^3) `set @0` (1^0^0^1 + 2^1^3^0)
((7)×y)×x^3

> (5^0) `set @1` (1^0^0^1 + 2^1^3^0) 
(1)×x+(250)×y

> (5) `set @2` (1^0^0^1 + 2^1^3^0) 
(1)×x+(10)×y^3

Members

• _set :: Proxy n -> a -> Polynomial b -> b

Instances

• (Semiring a) => Set 0 a a
• (Set n1 a b, Add n1 1 n, Semiring a) => Set n a (Polynomial b)

set :: forall @n a b. Set n a b => a -> Polynomial b -> b

down :: forall f a c d. Functor f => Semiring a => (a -> c -> d) -> a -> f c -> f d

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

flipXpand :: forall a. Eq a => Semiring a => Polynomial a -> Polynomial a -> Polynomial a

Multivariate polynomial substitution

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

Multivariate polynomial substitution infix notation

class FillValid :: Int -> Type -> Constraintclass FillValid n a  where

Members

• fillValid :: Proxy n -> (Polynomial a -> Polynomial a -> Polynomial a)

Instances

• (Eq a, Semiring a) => FillValid 0 a
• (FillValid n1 a, Eq a, Semiring a, Add n1 1 n) => FillValid n (Polynomial a)

deep :: forall f a c d. Functor f => Semiring a => (a -> c -> d) -> Polynomial a -> f c -> f d

xpand :: forall a. Eq a => Semiring a => Polynomial a -> Polynomial a -> Polynomial a

_fill :: forall a v w. Eq a => Semiring a => NextAxis v w => GoSwap 0 w a => Proxy v -> Polynomial a -> Polynomial a -> Polynomial a

> --     ------------------------------------------------
> --    | FILL : the substitution function that replaces |
> --    | ----                                           |
> --    | each occurrence of the focus in a polynomial   |
> --    | by the provided value.                         |
> --     ------------------------------------------------
> --    | input1 : value || input2 : polynomial |
> --     -------------------------------------------------
> --    |    arity  |                |    arity  |  arity |
> --    |   input1  |     `usage`    |   input2  = output |
> --    |           |                |           |        |
> --     =================================================
> --    |      P    | `fill @focus`  |  P>focus  =    P   |
> --     -------------------------------------------------

> 1^0^0^1 + 2^1^3^0
(1)×x+((2)×z)×y^3

> 1^0^0^1 + 1^0^1^0
(1)×x+(1)×y

> (1^0^0^1 + 1^0^1^0) `fill @0` (1^0^0^1 + 2^1^3^0)
(1)×x+((2)×z)×y^3+(1)×y

> (1^0^0^1 + 1^0^1^0) `fill @1` (1^0^0^1 + 2^1^3^0)
((2)×z)×x^3+(((6)×z)×y)×x^2+(((6)×z)×y^2+1)×x+((2)×z)×y^3

> (1^0^0^1 + 1^0^1^0) `fill @2` (1^0^0^1 + 2^1^3^0) 
((2)×y^3+1)×x+(2)×y^4

fill :: forall a @v w. Eq a => Semiring a => NextAxis v w => GoSwap 0 w a => Polynomial a -> Polynomial a -> Polynomial a

class Full :: Int -> Type -> Constraintclass Full n a  where

Members

• fullImpl :: Proxy n -> Array (Polynomial a -> Polynomial a -> Polynomial a)

Instances

• (Eq a, Semiring a) => Full 0 a
• (Full n1 a, Add n1 1 n, NextAxis n w, GoSwap 0 w a, Eq a, Semiring a) => Full n a

full :: forall a n m. Full n a => Add n 1 m => Arity (Polynomial a) m => Array (Polynomial a) -> Polynomial a -> Polynomial a

Saturated version of fill where array values have to be provided in order of proximity : value at index i is set to axis of proximity <i>.

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

Dispatches the terms of a polynomial with respect to its first variable in list of tuples (degree, coefficient) and order it by decreasing degree

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

Terms of a polynomial with respect to its first variable in list of tuples (degree, coefficient)

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

Leading term of a polynomial with respect to its first variable

class (Semiring a) <= Leadable a  where

Leading term of an expanded multivariate polynomial

Members

• leader :: Polynomial a -> Polynomial a

Instances

• (Eq a, Leadable a, Semiring a) => Leadable (Polynomial a)
• (Eq a, Semiring a) => Leadable a

class Divisible a  where

Divisibility between two leaders

Members

• divides :: a -> a -> Maybe a

Instances

• (Semiring a, Divisible a) => Divisible (Polynomial a)
• (EuclideanRing a) => Divisible a

division :: forall a. Ring a => Eq a => Divisible a => Leadable a => Polynomial a -> Polynomial a -> { div :: Polynomial a, mod :: Polynomial a }

Euclidean division between two multivariate polynomials over an Euclidean ring

degreeAccordingToFirstVariable :: forall a. Eq a => Semiring a => Polynomial a -> Int

Degree

class Primitivable a  where

Members

• primitivePart :: Polynomial a -> Polynomial a
• globalFactor :: Polynomial a -> Polynomial a -> Polynomial a

Instances

• (Ord a, Divisible a, Leadable a, CommutativeRing a, EuclideanRing a, Primitivable a) => Primitivable (Polynomial a)
• (Eq a, Semiring a) => Primitivable a

gcds :: forall a. Ord a => Divisible a => Leadable a => EuclideanRing a => Primitivable a => Array (Polynomial a) -> Polynomial a

gcd :: forall a. Ord a => Divisible a => CommutativeRing a => Leadable a => Primitivable a => Polynomial a -> Polynomial a -> Polynomial a

Greatest common divisor of 2 multvariate polynomials The final constant scaling factor is nothing but arbitrary For instance gcd (2xyz) (3yz) gives 2yz

cont :: forall a. Ord a => EuclideanRing a => Divisible a => Leadable a => Primitivable a => Polynomial (Polynomial a) -> Polynomial a

bezout :: forall a. Eq a => Ord a => CommutativeRing a => Divisible a => Leadable a => Univariate (Polynomial a) => Polynomial a -> Polynomial a -> Maybe { u :: Polynomial a, v :: Polynomial a }

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

unity :: forall a. Eq a => Semiring a => Polynomial a -> Polynomial a

Gets the right representation of unity in the context of the provided multivariate polynomial

class Univariate a  where

Members

• isMultivariate :: a -> Boolean

Instances

• Univariate (Polynomial (Polynomial a))
• Univariate a

class Arity :: Type -> Int -> Constraintclass Arity a n | a -> n where

Members

• arity' :: a -> Proxy n

Instances

• (Arity (Polynomial a) n1, Add n1 1 n) => Arity (Polynomial (Polynomial a)) n
• Arity (Polynomial a) 1
• Arity a 0

class Peel a b | a -> b where

> --     -------------------------------------------------
> --    | PEEL : the extracting function that returns     |
> --    | ----                                            |
> --    | the constant term (in the underlying structure) |
> --    | of a polynomial.                                |
> --     -------------------------------------------------
> --    | input : polynomial |
> --     ----------------------------------
> --    |            |    arity  |  arity  |
> --    |     usage  |    input  = output  |
> --    |            |           |         |
> --     ==================================
> --    |     peel   |    P>0    =   0     |
> --     ----------------------------------

> peel $ (1^1+3^0) * (1^1-3^0)
-9

> peel $ (4^2^2 - 12^1^1) / 2^1^1
-6

Members

• peel :: Polynomial a -> b

Instances

• (Peel a b, Eq a, Semiring a) => Peel (Polynomial a) b
• (Semiring a) => Peel a a

class Axed a r  where

Gets the right representation of each of the variables in the context of the provided multivariate unity

Members

• axes :: a -> (r -> a) /\ (Array a)

Instances

• (Axed a r, Semiring a, Peel a r) => Axed (Polynomial a) r
• (Semiring a, Eq a) => Axed a a

class Nest :: Int -> Type -> Constraintclass Nest n a  where

> --     -------------------------------------------------
> --    | NEST : the extension function that introduces a |
> --    | ----                                            |
> --    | new variable before the focus of a polynomial   |
> --    | and shifts each of the other nearer variables   |
> --    | (focus included) one order nearer.              |
> --     -------------------------------------------------
> --    | input : polynomial |
> --     ---------------------------------------
> --    |                |    arity    |  arity |
> --    |      usage     |    input    = output |
> --    |                |             |        |
> --     =======================================
> --    |   nest @focus  |  P >= focus =   P+1  |
> --     ---------------------------------------

> nest @0 $ 5^0
5

> nest @0 $ 8^0^1
(8)×y

> nest @0 $ 21^1^1
((21)×z)×y

> nest @1 $ 5^0^0
5

> nest @1 $ 8^0^0^1
(8)×x

> nest @1 $ 13^0^1^0
(13)×z

> nest @1 $ 34^1^1^1
(((34)×t)×z)×x

> nest @2 $ 5^0^0
5

> nest @2 $ 34^1^1^1
(((34)×t)×y)×x

Members

• _nest :: Proxy n -> a -> Polynomial a

Instances

• Nest 0 a
• (Nest n1 a, Add n1 1 n) => Nest n (Polynomial a)

nest :: forall @n a. Nest n a => a -> Polynomial a

xtend :: forall a. a -> Polynomial a

class SwapAdjacent :: Int -> Type -> Constraintclass SwapAdjacent n a  where

> --     --------------------------------------------
> --    | SWAP : the swapping function that permutes |
> --    | ----                                       |
> --    | two axes in a polynomial.                  |
> --     --------------------------------------------
> --    | input : polynomial |
> --     ----------------------------------------
> --    |                     |  arity  |  arity |
> --    |         usage       |  input  = output |
> --    |                     |         |        |
> --     ========================================
> --    |   swap @ax1 @ax2    |  P>=2   =     P  |
> --     ----------------------------------------

> f = 3^0^0^0^2 + 4^0^1^3^0 + 5^1^0^0^0
> f
(3)×x^2+((4)×z)×y^3+(5)×t
>
> swap @0 @1 f
((4)×z)×x^3+(3)×y^2+(5)×t

> swap @3 @1 f
(3)×x^2+(5)×y+((4)×t^3)×z

Members

• swapAdjacent :: Proxy n -> (Polynomial (Polynomial a) -> Polynomial (Polynomial a))

Instances

• (Eq a, Semiring a) => SwapAdjacent 0 a
• (SwapAdjacent n1 a, Semiring a, Add n1 1 n) => SwapAdjacent n (Polynomial a)

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

class Swap :: Int -> Int -> Type -> Constraintclass Swap m n a  where

Members

• _swap :: Proxy m -> Proxy n -> (Polynomial (Polynomial a) -> Polynomial (Polynomial a))

Instances

• (Compare m n o, SwapSort o m n a) => Swap m n a

swap :: forall @m @n a. Swap m n a => Polynomial (Polynomial a) -> Polynomial (Polynomial a)

class SwapSort :: Ordering -> Int -> Int -> Type -> Constraintclass SwapSort o m n a  where

Members

• swapSort :: Proxy o -> Proxy m -> Proxy n -> (Polynomial (Polynomial a) -> Polynomial (Polynomial a))

Instances

• (SwapInOrder m n a) => SwapSort LT m n a
• (SwapInOrder n m a) => SwapSort GT m n a
• SwapSort EQ m n a

class SwapInOrder :: Int -> Int -> Type -> Constraintclass SwapInOrder m n a  where

Members

• swapInOrder :: Proxy m -> Proxy n -> (Polynomial (Polynomial a) -> Polynomial (Polynomial a))

Instances

• (GoSwap m delta a, Add m delta n) => SwapInOrder m n a

class GoSwap :: Int -> Int -> Type -> Constraintclass GoSwap from delta a  where

Members

• goSwap :: Proxy from -> Proxy delta -> (Polynomial (Polynomial a) -> Polynomial (Polynomial a))

Instances

• GoSwap from 0 a
• (SwapAdjacent from a) => GoSwap from 1 a
• (GoSwap next delta1 a, Add from 1 next, Add delta1 1 delta, SwapAdjacent from a) => GoSwap from delta a

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

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

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

Returns the n approximative roots of a univariate polynomial of degree n

class Display a  where

Displays a multivariate polynomial with respect to the provided list of names. Whatever the arity, the zero polynomial is displayed as the empty string.

Members

• arity :: a -> Int
• display :: Array String -> a -> String

Instances

• (Display a, Ord a, Semiring a) => Display (Polynomial a)
• (Show a, Arity a 0) => Display a

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

class IntLiftable a  where

Members

• fromInt :: Int -> a

Instances

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

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

Univariate polynomial differentiation

interpolate :: forall a. Eq a => Semiring a => EuclideanRing a => Array (a /\ a) -> Polynomial a

Polynomial such that the second element of each tuple is the image of the first element.

isPrime :: forall a. Ord a => Semiring a => EuclideanRing a => a -> Boolean

True if n is < 2 or prime

nextPrime :: forall a. Ord a => Semiring a => EuclideanRing a => a -> a

Ad infinitum

primeFactor :: forall a. Ord a => Eq a => EuclideanRing a => a -> Boolean /\ a

If n is prime, returns true /\ n, otherwise, false /\ d if d | n with d > 1

primeFactorization :: forall base exp. Ord base => Eq base => Semiring base => EuclideanRing base => Semiring exp => base -> Array (base /\ exp)

Factorizes a number > 1 in an array (divider /\ multiplicity)

divisors :: forall a. Semiring a => EuclideanRing a => Eq a => Ord a => a -> Array a

All the divisors of a positive integer

factor :: forall a. Eq a => Ord a => EuclideanRing a => IntLiftable a => Divisible a => Leadable a => Polynomial (Ratio a) -> Array (Polynomial (Ratio a))

At least one non-constant polynomial factor if the univariate input, with rational coefficients, is not irreductible, empty array if it is.

factorOnZ :: forall a. Ord a => Ring a => EuclideanRing a => Divisible a => IntLiftable a => Leadable a => Polynomial a -> Array (Polynomial a)

At least one non-constant polynomial factor if the univariate input, with integer coefficients, is not irreductible, empty array if it is.

eisenstein :: forall a. Eq a => Divisible a => Leadable a => CommutativeRing a => EuclideanRing a => Polynomial a -> a -> Boolean

Eisenstein criterium of irreductibility of f = anx^n + ... + a1x + a0:
                           _
Exists prime p,             |
p   not | an                | => f  irreductible over Q
p       | ai for i=0..n-1   | 
p^2 not | a0                |