# poly

Polynomials

 LTS Haskell 20.15: 0.5.1.0 Stackage Nightly 2023-03-23: 0.5.1.0 Latest on Hackage: 0.5.1.0

See all snapshots `poly` appears in

This version can be pinned in stack with:`poly-0.5.1.0@sha256:08b05c1f80313d759aef546c3999e371c7b7d63a0733dd49e84b8c454f78c56b,3268`

#### Module documentation for 0.5.1.0

Depends on 8 packages(full list with versions):

# poly

Haskell library for univariate and multivariate polynomials, backed by `Vector`s.

``````> -- Univariate polynomials
> (X + 1) + (X - 1) :: VPoly Integer
2 * X
> (X + 1) * (X - 1) :: UPoly Int
1 * X^2 + (-1)

> -- Multivariate polynomials
> (X + Y) * (X - Y) :: VMultiPoly 2 Integer
1 * X^2 + (-1) * Y^2
> (X + Y + Z) ^ 2 :: UMultiPoly 3 Int
1 * X^2 + 2 * X * Y + 2 * X * Z + 1 * Y^2 + 2 * Y * Z + 1 * Z^2

> -- Laurent polynomials
> (X^-2 + 1) * (X - X^-1) :: VLaurent Integer
1 * X + (-1) * X^-3
> (X^-1 + Y) * (X + Y^-1) :: UMultiLaurent 2 Int
1 * X * Y + 2 + 1 * X^-1 * Y^-1
``````

## Vectors

`Poly v a` is polymorphic over a container `v`, implementing the `Vector` interface, and coefficients of type `a`. Usually `v` is either a boxed vector from `Data.Vector` or an unboxed vector from `Data.Vector.Unboxed`. Use unboxed vectors whenever possible, e. g., when the coefficients are `Int`s or `Double`s.

There are handy type synonyms:

``````type VPoly a = Poly Data.Vector.Vector         a
type UPoly a = Poly Data.Vector.Unboxed.Vector a
``````

## Construction

The simplest way to construct a polynomial is using the pattern `X`:

``````> X^2 - 3 * X + 2 :: UPoly Int
1 * X^2 + (-3) * X + 2
``````

(Unfortunately, types are often ambiguous and must be given explicitly.)

While being convenient to read and write in REPL, `X` is relatively slow. The fastest approach is to use `toPoly`, providing it with a vector of coefficients (constant term first):

``````> toPoly (Data.Vector.Unboxed.fromList [2, -3, 1 :: Int])
1 * X^2 + (-3) * X + 2
``````

Alternatively one can enable `{-# LANGUAGE OverloadedLists #-}` and simply write

``````> [2, -3, 1] :: UPoly Int
1 * X^2 + (-3) * X + 2
``````

There is a shortcut to construct a monomial:

``````> monomial 2 3.5 :: UPoly Double
3.5 * X^2 + 0.0 * X + 0.0
``````

## Operations

Most operations are provided by means of instances, like `Eq` and `Num`. For example,

``````> (X^2 + 1) * (X^2 - 1) :: UPoly Int
1 * X^4 + 0 * X^3 + 0 * X^2 + 0 * X + (-1)
``````

One can also find it convenient to `scale` by a monomial (cf. `monomial` above):

``````> scale 2 3.5 (X^2 + 1) :: UPoly Double
3.5 * X^4 + 0.0 * X^3 + 3.5 * X^2 + 0.0 * X + 0.0
``````

While `Poly` cannot be made an instance of `Integral` (because there is no meaningful `toInteger`), it is an instance of `GcdDomain` and `Euclidean` from the `semirings` package. These type classes cover the main functionality of `Integral`, providing division with remainder and `gcd` / `lcm`:

``````> Data.Euclidean.gcd (X^2 + 7 * X + 6) (X^2 - 5 * X - 6) :: UPoly Int
1 * X + 1

> Data.Euclidean.quotRem (X^3 + 2) (X^2 - 1 :: UPoly Double)
(1.0 * X + 0.0,1.0 * X + 2.0)
``````

Miscellaneous utilities include `eval` for evaluation at a given point, and `deriv` / `integral` for taking the derivative and an indefinite integral, respectively:

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

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

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

## Deconstruction

Use `unPoly` to deconstruct a polynomial to a vector of coefficients (constant term first):

``````> unPoly (X^2 - 3 * X + 2 :: UPoly Int)
[2,-3,1]
``````

Further, `leading` is a shortcut to obtain the leading term of a non-zero polynomial, expressed as a power and a coefficient:

``````> leading (X^2 - 3 * X + 2 :: UPoly Double)
Just (2,1.0)
``````

## Flavours

• `Data.Poly` provides dense univariate polynomials with a `Num`-based interface. This is a default choice for most users.

• `Data.Poly.Semiring` provides dense univariate polynomials with a `Semiring`-based interface.

• `Data.Poly.Laurent` provides dense univariate Laurent polynomials with a `Semiring`-based interface.

• `Data.Poly.Sparse` provides sparse univariate polynomials with a `Num`-based interface. Besides that, you may find it easier to use in the REPL because of a more readable `Show` instance, skipping zero coefficients.

• `Data.Poly.Sparse.Semiring` provides sparse univariate polynomials with a `Semiring`-based interface.

• `Data.Poly.Sparse.Laurent` provides sparse univariate Laurent polynomials with a `Semiring`-based interface.

• `Data.Poly.Multi` provides sparse multivariate polynomials with a `Num`-based interface.

• `Data.Poly.Multi.Semiring` provides sparse multivariate polynomials with a `Semiring`-based interface.

• `Data.Poly.Multi.Laurent` provides sparse multivariate Laurent polynomials with a `Semiring`-based interface.

All flavours are available backed by boxed or unboxed vectors.

## Performance

As a rough guide, `poly` is at least 20x-40x faster than the `polynomial` library. Multiplication is implemented via the Karatsuba algorithm. Here are a couple of benchmarks for `UPoly Int`:

Benchmark polynomial, μs poly, μs speedup
addition, 100 coeffs. 45 2 22x
addition, 1000 coeffs. 441 17 25x
addition, 10000 coeffs. 6545 167 39x
multiplication, 100 coeffs. 1733 33 52x
multiplication, 1000 coeffs. 442000 1456 303x

Due to being polymorphic by multiple axis, the performance of `poly` crucially depends on specialisation of instances. Clients are strongly recommended to compile with `ghc-options: -fspecialise-aggressively` and suggested to enable `-O2`.

• Polynomials in Haskell, MuniHac, 12.09.2020: slides, video.

# 0.5.1.0

• Add function `timesRing`.
• Tweak inlining pragmas.

# 0.5.0.0

• Change definition of `Data.Euclidean.degree` to coincide with the degree of polynomial.
• Implement multivariate polynomials (usual and Laurent).
• Reimplement sparse univariate polynomials as a special case of multivariate ones.
• Speed up `gcd` calculations for all flavours of polynomials.
• Decomission `PolyOverField` and `LaurentOverField`: they do not improve performance any more.
• Add function `quotRemFractional`.
• Add an experimental implementation of the discrete Fourier transform.
• Add conversion functions between dense and sparse polynomials.

# 0.4.0.0

• Implement Laurent polynomials.
• Implement orthogonal polynomials.
• Decomission extended GCD, use `Data.Euclidean.gcdExt`.
• Decomission `PolyOverFractional`, use `PolyOverField`.

# 0.3.3.0

• Add function `subst`.
• Fix compatibility issues.

# 0.3.2.0

• Add `NFData` instance.
• Implement extended GCD.
• Rename `PolyOverFractional` to `PolyOverField`.
• Add `integral` with `Semiring`-based interface.

# 0.3.1.0

• Implement Karatsuba multiplication.
• Add `IsList` instance.

# 0.3.0.0

• Implement sparse polynomials.
• Add `GcdDomain` and `Euclidean` instances.
• Add functions `leading`, `monomial`, `scale`.
• Remove function `constant`.

# 0.2.0.0

• Parametrize `Poly` by underlying vector type.
• Introduce `Data.Poly.Semiring` module.
• Fix a bug in `Num.(-)`.
• Add functions `constant`, `eval`, `deriv`, `integral`.
• Add a handy pattern synonym `X`.
• Add type synonyms `VPoly` and `UPoly`.
• Remove function `toPoly'`.

# 0.1.0.0

• Initial release.