Data.Poly.Sparse.Laurent

Sparse Laurent polynomials.

Documentation

data Laurent v a

Laurent polynomials of one variable with coefficients from a, backed by a Vector v (boxed, unboxed, storable, etc.).

Use pattern X and operator ^- for construction:

>>> (X + 1) + (X^-1 - 1) :: VLaurent Integer
1 * X + 1 * X^-1
>>> (X + 1) * (1 - X^-1) :: ULaurent Int
1 * X + (-1) * X^-1

Polynomials are stored normalized, without zero coefficients, so 0 * X + 1 + 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.

Instances

(Eq a, Semiring a, Vector v (Word, a)) => IsList (Laurent v a)

Defined in Data.Poly.Sparse.Laurent

Associated Types

type Item (Laurent v a) :: Type

Methods

fromList :: [Item (Laurent v a)] -> Laurent v a

fromListN :: Int -> [Item (Laurent v a)] -> Laurent v a

toList :: Laurent v a -> [Item (Laurent v a)]

Eq (v (Word, a)) => Eq (Laurent v a)

Defined in Data.Poly.Sparse.Laurent

Methods

(==) :: Laurent v a -> Laurent v a -> Bool

(/=) :: Laurent v a -> Laurent v a -> Bool

(Eq a, Num a, Vector v (Word, a)) => Num (Laurent v a)

Note that abs = id and signum = const 1.

Defined in Data.Poly.Sparse.Laurent

Methods

(+) :: Laurent v a -> Laurent v a -> Laurent v a

(-) :: Laurent v a -> Laurent v a -> Laurent v a

(*) :: Laurent v a -> Laurent v a -> Laurent v a

negate :: Laurent v a -> Laurent v a

abs :: Laurent v a -> Laurent v a

signum :: Laurent v a -> Laurent v a

fromInteger :: Integer -> Laurent v a

Ord (v (Word, a)) => Ord (Laurent v a)

Defined in Data.Poly.Sparse.Laurent

Methods

compare :: Laurent v a -> Laurent v a -> Ordering

(<) :: Laurent v a -> Laurent v a -> Bool

(<=) :: Laurent v a -> Laurent v a -> Bool

(>) :: Laurent v a -> Laurent v a -> Bool

(>=) :: Laurent v a -> Laurent v a -> Bool

max :: Laurent v a -> Laurent v a -> Laurent v a

min :: Laurent v a -> Laurent v a -> Laurent v a

(Show a, Vector v (Word, a)) => Show (Laurent v a)

Defined in Data.Poly.Sparse.Laurent

Methods

showsPrec :: Int -> Laurent v a -> ShowS

show :: Laurent v a -> String

showList :: [Laurent v a] -> ShowS

NFData (v (Word, a)) => NFData (Laurent v a)

Defined in Data.Poly.Sparse.Laurent

Methods

rnf :: Laurent v a -> ()

(Eq a, Ring a, GcdDomain a, Eq (v (Word, a)), Vector v (Word, a)) => GcdDomain (Laurent v a)

Defined in Data.Poly.Sparse.Laurent

Methods

divide :: Laurent v a -> Laurent v a -> Maybe (Laurent v a)

gcd :: Laurent v a -> Laurent v a -> Laurent v a

lcm :: Laurent v a -> Laurent v a -> Laurent v a

coprime :: Laurent v a -> Laurent v a -> Bool

(Eq a, Semiring a, Vector v (Word, a)) => Semiring (Laurent v a)

Defined in Data.Poly.Sparse.Laurent

Methods

plus :: Laurent v a -> Laurent v a -> Laurent v a

zero :: Laurent v a

times :: Laurent v a -> Laurent v a -> Laurent v a

one :: Laurent v a

fromNatural :: Natural -> Laurent v a

(Eq a, Ring a, Vector v (Word, a)) => Ring (Laurent v a)

Defined in Data.Poly.Sparse.Laurent

Methods

negate :: Laurent v a -> Laurent v a

type Item (Laurent v a)

Defined in Data.Poly.Sparse.Laurent

type Item (Laurent v a) = (Int, a)

type VLaurent = Laurent Vector

Laurent polynomials backed by boxed vectors.

type ULaurent = Laurent Vector

Laurent polynomials backed by unboxed vectors.

unLaurent :: Laurent v a -> (Int, Poly v a)

Deconstruct a Laurent polynomial into an offset (largest possible) and a regular polynomial.

>>> unLaurent (2 * X + 1 :: ULaurent Int)
(0,2 * X + 1)
>>> unLaurent (1 + 2 * X^-1 :: ULaurent Int)
(-1,1 * X + 2)
>>> unLaurent (2 * X^2 + X :: ULaurent Int)
(1,2 * X + 1)
>>> unLaurent (0 :: ULaurent Int)
(0,0)

toLaurent :: (Eq a, Semiring a, Vector v (Word, a)) => Int -> Poly v a -> Laurent v a

Construct Laurent polynomial from an offset and a regular polynomial. One can imagine it as scale', but allowing negative offsets.

>>> toLaurent 2 (2 * Data.Poly.Sparse.X + 1) :: ULaurent Int
2 * X^3 + 1 * X^2
>>> toLaurent (-2) (2 * Data.Poly.Sparse.X + 1) :: ULaurent Int
2 * X^-1 + 1 * X^-2

leading :: Vector v (Word, a) => Laurent v a -> Maybe (Int, a)

Return a leading power and coefficient of a non-zero polynomial.

>>> leading ((2 * X + 1) * (2 * X^2 - 1) :: ULaurent Int)
Just (3,4)
>>> leading (0 :: ULaurent Int)
Nothing

monomial :: (Eq a, Semiring a, Vector v (Word, a)) => Int -> a -> Laurent v a

Create a monomial from a power and a coefficient.

scale :: (Eq a, Semiring a, Vector v (Word, a)) => Int -> a -> Laurent v a -> Laurent v a

Multiply a polynomial by a monomial, expressed as a power and a coefficient.

>>> scale 2 3 (X^2 + 1) :: ULaurent Int
3 * X^4 + 3 * X^2

pattern X :: (Eq a, Semiring a, Vector v (Word, a), Eq (v (Word, a))) => Laurent v a

Create an identity polynomial.

(^-) :: (Eq a, Semiring a, Vector v (Word, a), Eq (v (Word, a))) => Laurent v a -> Int -> Laurent v a

This operator can be applied only to X, but is instrumental to express Laurent polynomials in mathematical fashion:

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

eval :: (Field a, Vector v (Word, a)) => Laurent v a -> a -> a

Evaluate at a given point.

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

subst :: (Eq a, Semiring a, Vector v (Word, a), Vector w (Word, a)) => Poly v a -> Laurent w a -> Laurent w a

Substitute another polynomial instead of X.

>>> subst (X^2 + 1 :: UPoly Int) (X + 1 :: ULaurent Int)
1 * X^2 + 2 * X + 2

deriv :: (Eq a, Ring a, Vector v (Word, a)) => Laurent v a -> Laurent v a

Take a derivative.

>>> deriv (X^3 + 3 * X) :: ULaurent Int
3 * X^2 + 3