-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Polynomials
--
-- Polynomials backed by Vector.
@package poly
@version 0.3.2.0
-- | Dense polynomials and a Num-based interface.
module Data.Poly
-- | 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.
data Poly v a
-- | Polynomials backed by boxed vectors.
type VPoly = Poly Vector
-- | Polynomials backed by unboxed vectors.
type UPoly = Poly Vector
-- | Convert Poly to a vector of coefficients (first element
-- corresponds to a constant term).
unPoly :: Poly v a -> v a
-- | 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
--
leading :: Vector v a => Poly v a -> Maybe (Word, a)
-- | Make Poly from a list 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
--
toPoly :: (Eq a, Num a, Vector v a) => v a -> Poly v a
-- | Create a monomial from a power and a coefficient.
monomial :: (Eq a, Num a, Vector v a) => Word -> a -> Poly v a
-- | 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
--
scale :: (Eq a, Num a, Vector v a) => Word -> a -> Poly v a -> Poly v a
-- | Create an identity polynomial.
pattern X :: (Eq a, Num a, Vector v a, Eq (v a)) => Poly v a
-- | 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
--
eval :: (Num a, Vector v a) => Poly v a -> a -> a
-- | Take a derivative.
--
--
-- >>> deriv (X^3 + 3 * X) :: UPoly Int
-- 3 * X^2 + 0 * X + 3
--
deriv :: (Eq a, Num a, Vector v a) => Poly v a -> Poly v a
-- | Compute an indefinite integral of a polynomial, setting constant term
-- to zero.
--
--
-- >>> integral (3 * X^2 + 3) :: UPoly Double
-- 1.0 * X^3 + 0.0 * X^2 + 3.0 * X + 0.0
--
integral :: (Eq a, Fractional a, Vector v a) => Poly v a -> Poly v a
-- | Wrapper for polynomials over Field, providing a faster
-- GcdDomain instance.
newtype PolyOverField poly
PolyOverField :: poly -> PolyOverField poly
[unPolyOverField] :: PolyOverField poly -> poly
-- | Execute the extended Euclidean algorithm. For polynomials a
-- and b, compute their unique greatest common divisor
-- g and the unique coefficient polynomial s satisfying
-- as + bt = g, such that either g is monic, or g =
-- 0 and s is monic, or g = s = 0.
--
--
-- >>> gcdExt (X^2 + 1 :: UPoly Double) (X^3 + 3 * X :: UPoly Double)
-- (1.0, 0.5 * X^2 + (-0.0) * X + 1.0)
--
-- >>> gcdExt (X^3 + 3 * X :: UPoly Double) (3 * X^4 + 3 * X^2 :: UPoly Double)
-- (1.0 * X + 0.0,(-0.16666666666666666) * X^2 + (-0.0) * X + 0.3333333333333333)
--
gcdExt :: (Eq a, Field a, Vector v a, Eq (v a)) => Poly v a -> Poly v a -> (Poly v a, Poly v a)
-- | Deprecated: Use PolyOverField
type PolyOverFractional = PolyOverField
-- | Deprecated: Use PolyOverField
pattern PolyOverFractional :: poly -> PolyOverField poly
-- | Deprecated: Use unPolyOverField
unPolyOverFractional :: PolyOverField poly -> poly
-- | Dense polynomials and a Semiring-based interface.
module Data.Poly.Semiring
-- | 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.
data Poly v a
-- | Polynomials backed by boxed vectors.
type VPoly = Poly Vector
-- | Polynomials backed by unboxed vectors.
type UPoly = Poly Vector
-- | Convert Poly to a vector of coefficients (first element
-- corresponds to a constant term).
unPoly :: Poly v a -> v a
-- | 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
--
leading :: Vector v a => Poly v a -> Maybe (Word, a)
-- | 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
--
toPoly :: (Eq a, Semiring a, Vector v a) => v a -> Poly v a
-- | Create a monomial from a power and a coefficient.
monomial :: (Eq a, Semiring a, Vector v a) => Word -> a -> Poly v a
-- | 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
--
scale :: (Eq a, Semiring a, Vector v a) => Word -> a -> Poly v a -> Poly v a
-- | Create an identity polynomial.
pattern X :: (Eq a, Semiring a, Vector v a, Eq (v a)) => Poly v a
-- | 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
--
eval :: (Semiring a, Vector v a) => Poly v a -> a -> a
-- | Take a derivative.
--
--
-- >>> deriv (X^3 + 3 * X) :: UPoly Int
-- 3 * X^2 + 0 * X + 3
--
deriv :: (Eq a, Semiring a, Vector v a) => Poly v a -> Poly v a
-- | Compute an indefinite integral of a polynomial, setting constant term
-- to zero.
--
--
-- >>> integral (3 * X^2 + 3) :: UPoly Double
-- 1.0 * X^3 + 0.0 * X^2 + 3.0 * X + 0.0
--
integral :: (Eq a, Field a, Vector v a) => Poly v a -> Poly v a
-- | Wrapper for polynomials over Field, providing a faster
-- GcdDomain instance.
newtype PolyOverField poly
PolyOverField :: poly -> PolyOverField poly
[unPolyOverField] :: PolyOverField poly -> poly
-- | Execute the extended Euclidean algorithm. For polynomials a
-- and b, compute their unique greatest common divisor
-- g and the unique coefficient polynomial s satisfying
-- as + bt = g, such that either g is monic, or g =
-- 0 and s is monic, or g = s = 0.
--
--
-- >>> gcdExt (X^2 + 1 :: UPoly Double) (X^3 + 3 * X :: UPoly Double)
-- (1.0, 0.5 * X^2 + (-0.0) * X + 1.0)
--
-- >>> gcdExt (X^3 + 3 * X :: UPoly Double) (3 * X^4 + 3 * X^2 :: UPoly Double)
-- (1.0 * X + 0.0,(-0.16666666666666666) * X^2 + (-0.0) * X + 0.3333333333333333)
--
gcdExt :: (Eq a, Field a, Vector v a, Eq (v a)) => Poly v a -> Poly v a -> (Poly v a, Poly v a)
-- | Deprecated: Use PolyOverField
type PolyOverFractional = PolyOverField
-- | Deprecated: Use PolyOverField
pattern PolyOverFractional :: poly -> PolyOverField poly
-- | Deprecated: Use unPolyOverField
unPolyOverFractional :: PolyOverField poly -> poly
-- | Sparse polynomials with Num instance.
module Data.Poly.Sparse
-- | 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
--
-- >>> (X + 1) * (X - 1) :: UPoly Int
-- 1 * X^2 + (-1)
--
--
-- Polynomials are stored normalized, without 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.
data Poly v a
-- | Polynomials backed by boxed vectors.
type VPoly = Poly Vector
-- | Polynomials backed by unboxed vectors.
type UPoly = Poly Vector
-- | Convert Poly to a vector of coefficients (first element
-- corresponds to a constant term).
unPoly :: Poly v a -> v (Word, a)
-- | 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
--
leading :: Vector v (Word, a) => Poly v a -> Maybe (Word, a)
-- | Make Poly from a list of (power, coefficient) pairs. (first
-- element corresponds to a constant term).
--
--
-- >>> :set -XOverloadedLists
--
-- >>> toPoly [(0,1),(1,2),(2,3)] :: VPoly Integer
-- 3 * X^2 + 2 * X + 1
--
-- >>> S.toPoly [(0,0),(1,0),(2,0)] :: UPoly Int
-- 0
--
toPoly :: (Eq a, Num a, Vector v (Word, a)) => v (Word, a) -> Poly v a
-- | Create a monomial from a power and a coefficient.
monomial :: (Eq a, Num a, Vector v (Word, a)) => Word -> a -> Poly v a
-- | Multiply a polynomial by a monomial, expressed as a power and a
-- coefficient.
--
--
-- >>> scale 2 3 (X^2 + 1) :: UPoly Int
-- 3 * X^4 + 3 * X^2
--
scale :: (Eq a, Num a, Vector v (Word, a)) => Word -> a -> Poly v a -> Poly v a
-- | Create an identity polynomial.
pattern X :: (Eq a, Num a, Vector v (Word, a), Eq (v (Word, a))) => Poly v a
-- | 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
--
eval :: (Num a, Vector v (Word, a)) => Poly v a -> a -> a
-- | Take a derivative.
--
--
-- >>> deriv (X^3 + 3 * X) :: UPoly Int
-- 3 * X^2 + 3
--
deriv :: (Eq a, Num a, Vector v (Word, a)) => Poly v a -> Poly v a
-- | Compute an indefinite integral of a polynomial, setting constant term
-- to zero.
--
--
-- >>> integral (3 * X^2 + 3) :: UPoly Double
-- 1.0 * X^3 + 3.0 * X
--
integral :: (Eq a, Fractional a, Vector v (Word, a)) => Poly v a -> Poly v a
-- | Execute the extended Euclidean algorithm. For polynomials a
-- and b, compute their unique greatest common divisor
-- g and the unique coefficient polynomial s satisfying
-- as + bt = g, such that either g is monic, or g =
-- 0 and s is monic, or g = s = 0.
--
--
-- >>> gcdExt (X^2 + 1 :: UPoly Double) (X^3 + 3 * X :: UPoly Double)
-- (1.0, 0.5 * X^2 + (-0.0) * X + 1.0)
--
-- >>> gcdExt (X^3 + 3 * X :: UPoly Double) (3 * X^4 + 3 * X^2 :: UPoly Double)
-- (1.0 * X + 0.0,(-0.16666666666666666) * X^2 + (-0.0) * X + 0.3333333333333333)
--
gcdExt :: (Eq a, Field a, Vector v (Word, a), Eq (v (Word, a))) => Poly v a -> Poly v a -> (Poly v a, Poly v a)
-- | Sparse polynomials with Semiring instance.
module Data.Poly.Sparse.Semiring
-- | 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
--
-- >>> (X + 1) * (X - 1) :: UPoly Int
-- 1 * X^2 + (-1)
--
--
-- Polynomials are stored normalized, without 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.
data Poly v a
-- | Polynomials backed by boxed vectors.
type VPoly = Poly Vector
-- | Polynomials backed by unboxed vectors.
type UPoly = Poly Vector
-- | Convert Poly to a vector of coefficients (first element
-- corresponds to a constant term).
unPoly :: Poly v a -> v (Word, a)
-- | 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
--
leading :: Vector v (Word, a) => Poly v a -> Maybe (Word, a)
-- | Make Poly from a list of (power, coefficient) pairs. (first
-- element corresponds to a constant term).
--
--
-- >>> :set -XOverloadedLists
--
-- >>> toPoly [(0,1),(1,2),(2,3)] :: VPoly Integer
-- 3 * X^2 + 2 * X + 1
--
-- >>> S.toPoly [(0,0),(1,0),(2,0)] :: UPoly Int
-- 0
--
toPoly :: (Eq a, Semiring a, Vector v (Word, a)) => v (Word, a) -> Poly v a
-- | Create a monomial from a power and a coefficient.
monomial :: (Eq a, Semiring a, Vector v (Word, a)) => Word -> a -> Poly v a
-- | Multiply a polynomial by a monomial, expressed as a power and a
-- coefficient.
--
--
-- >>> scale 2 3 (X^2 + 1) :: UPoly Int
-- 3 * X^4 + 3 * X^2
--
scale :: (Eq a, Semiring a, Vector v (Word, a)) => Word -> a -> Poly v a -> Poly v a
-- | Create an identity polynomial.
pattern X :: (Eq a, Semiring a, Vector v (Word, a), Eq (v (Word, a))) => Poly v a
-- | 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
--
eval :: (Semiring a, Vector v (Word, a)) => Poly v a -> a -> a
-- | Take a derivative.
--
--
-- >>> deriv (X^3 + 3 * X) :: UPoly Int
-- 3 * X^2 + 3
--
deriv :: (Eq a, Semiring a, Vector v (Word, a)) => Poly v a -> Poly v a
-- | Compute an indefinite integral of a polynomial, setting constant term
-- to zero.
--
--
-- >>> integral (3 * X^2 + 3) :: UPoly Double
-- 1.0 * X^3 + 3.0 * X
--
integral :: (Eq a, Field a, Vector v (Word, a)) => Poly v a -> Poly v a
-- | Execute the extended Euclidean algorithm. For polynomials a
-- and b, compute their unique greatest common divisor
-- g and the unique coefficient polynomial s satisfying
-- as + bt = g, such that either g is monic, or g =
-- 0 and s is monic, or g = s = 0.
--
--
-- >>> gcdExt (X^2 + 1 :: UPoly Double) (X^3 + 3 * X :: UPoly Double)
-- (1.0, 0.5 * X^2 + (-0.0) * X + 1.0)
--
-- >>> gcdExt (X^3 + 3 * X :: UPoly Double) (3 * X^4 + 3 * X^2 :: UPoly Double)
-- (1.0 * X + 0.0,(-0.16666666666666666) * X^2 + (-0.0) * X + 0.3333333333333333)
--
gcdExt :: (Eq a, Field a, Vector v (Word, a), Eq (v (Word, a))) => Poly v a -> Poly v a -> (Poly v a, Poly v a)