poly

 Version on this page: 0.3.1.0 LTS Haskell 14.10: 0.3.1.0 Stackage Nightly 2019-10-20: 0.3.2.0 Latest on Hackage: 0.3.2.0

See all snapshots `poly` appears in

Module documentation for 0.3.1.0

This version can be pinned in stack with:`poly-0.3.1.0@sha256:3e015e84d304c4197a2cff4a78400ed619eb850922d566028edb6c7254f2095f,1875`

poly

Haskell library for univariate polynomials, backed by `Vector`.

``````> (X + 1) + (X - 1) :: VPoly Integer
2 * X + 0

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

Vectors

`Poly v a` is polymorphic over a container `v`, implementing `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 coefficients are `Int` or `Double`.

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, a type is 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 (head is the constant term):

``````> 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 convenient to `scale` by 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 `semirings` package. These type classes cover main functionality of `Integral`, providing division with remainder and `gcd` / `lcm`:

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

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

Miscellaneous utilities include `eval` for evaluation at a given value of indeterminate, and reciprocals `deriv` / `integral`:

``````> 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 (head is the constant term):

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

The same API is exposed in four flavours:

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

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

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

• `Data.Poly.Sparse.Semiring` provides sparse polynomials with `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 `polynomial` library. Multiplication is implemented via Karatsuba algorithm. Here is 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

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

• Fix a bug in `Num.(-)`.
• Add functions `constant`, `eval`, `deriv`, `integral`.
• Add a handy pattern synonym `X`.

0.1.0.0

• Initial release.
Depends on 5 packages(full list with versions):