-- |
-- Module:      Data.Poly.Sparse.Semiring
-- Copyright:   (c) 2019 Andrew Lelechenko
-- Licence:     BSD3
-- Maintainer:  Andrew Lelechenko <andrew.lelechenko@gmail.com>
--
-- Sparse polynomials with a 'Semiring' instance.
--
-- @since 0.3.0.0
--

{-# LANGUAGE DataKinds        #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE PatternSynonyms  #-}

module Data.Poly.Sparse.Semiring
  ( Poly
  , VPoly
  , UPoly
  , unPoly
  , toPoly
  , leading
  , monomial
  , scale
  , pattern X
  , eval
  , subst
  , deriv
  , integral
  , denseToSparse
  , sparseToDense
  ) where

import Control.Arrow
import Data.Euclidean (Field)
import Data.Semiring (Semiring(..))
import qualified Data.Vector.Generic as G
import qualified Data.Vector.Unboxed.Sized as SU
import qualified Data.Vector.Sized as SV

import qualified Data.Poly.Internal.Convert as Convert
import qualified Data.Poly.Internal.Dense as Dense
import Data.Poly.Internal.Multi (Poly, VPoly, UPoly, unPoly, leading)
import qualified Data.Poly.Internal.Multi as Multi
import Data.Poly.Internal.Multi.Field ()
import Data.Poly.Internal.Multi.GcdDomain ()

-- | Make a 'Poly' from a list of (power, coefficient) pairs.
--
-- >>> :set -XOverloadedLists
-- >>> toPoly [(0,1),(1,2),(2,3)] :: VPoly Integer
-- 3 * X^2 + 2 * X + 1
-- >>> toPoly [(0,0),(1,0),(2,0)] :: UPoly Int
-- 0
--
-- @since 0.3.0.0
toPoly
  :: (Eq a, Semiring a, G.Vector v (Word, a), G.Vector v (SU.Vector 1 Word, a))
  => v (Word, a)
  -> Poly v a
toPoly :: forall a (v :: * -> *).
(Eq a, Semiring a, Vector v (Word, a),
 Vector v (Vector 1 Word, a)) =>
v (Word, a) -> Poly v a
toPoly = forall a (v :: * -> *) (n :: Natural).
(Eq a, Semiring a, Vector v (Vector n Word, a)) =>
v (Vector n Word, a) -> MultiPoly v n a
Multi.toMultiPoly' forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (v :: * -> *) a b.
(Vector v a, Vector v b) =>
(a -> b) -> v a -> v b
G.map (forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first forall a. Unbox a => a -> Vector 1 a
SU.singleton)
{-# INLINABLE toPoly #-}

-- | Create a monomial from a power and a coefficient.
--
-- @since 0.3.0.0
monomial
  :: (Eq a, Semiring a, G.Vector v (SU.Vector 1 Word, a))
  => Word
  -> a
  -> Poly v a
monomial :: forall a (v :: * -> *).
(Eq a, Semiring a, Vector v (Vector 1 Word, a)) =>
Word -> a -> Poly v a
monomial = forall a (v :: * -> *) (n :: Natural).
(Eq a, Semiring a, Vector v (Vector n Word, a)) =>
Vector n Word -> a -> MultiPoly v n a
Multi.monomial' forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Unbox a => a -> Vector 1 a
SU.singleton
{-# INLINABLE monomial #-}

-- | 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
--
-- @since 0.3.0.0
scale
  :: (Eq a, Semiring a, G.Vector v (SU.Vector 1 Word, a))
  => Word
  -> a
  -> Poly v a
  -> Poly v a
scale :: forall a (v :: * -> *).
(Eq a, Semiring a, Vector v (Vector 1 Word, a)) =>
Word -> a -> Poly v a -> Poly v a
scale = forall a (n :: Natural) (v :: * -> *).
(Eq a, Semiring a, KnownNat n, Vector v (Vector n Word, a)) =>
Vector n Word -> a -> MultiPoly v n a -> MultiPoly v n a
Multi.scale' forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Unbox a => a -> Vector 1 a
SU.singleton
{-# INLINABLE scale #-}

-- | The polynomial 'X'.
--
-- > X == monomial 1 one
--
-- @since 0.3.0.0
pattern X
  :: (Eq a, Semiring a, G.Vector v (SU.Vector 1 Word, a))
  => Poly v a
pattern $bX :: forall a (v :: * -> *).
(Eq a, Semiring a, Vector v (Vector 1 Word, a)) =>
Poly v a
$mX :: forall {r} {a} {v :: * -> *}.
(Eq a, Semiring a, Vector v (Vector 1 Word, a)) =>
Poly v a -> ((# #) -> r) -> ((# #) -> r) -> r
X = Multi.X'

-- | Evaluate the polynomial at a given point.
--
-- >>> eval (X^2 + 1 :: UPoly Int) 3
-- 10
--
-- @since 0.3.0.0
eval
  :: (Semiring a, G.Vector v (SU.Vector 1 Word, a))
  => Poly v a
  -> a
  -> a
eval :: forall a (v :: * -> *).
(Semiring a, Vector v (Vector 1 Word, a)) =>
Poly v a -> a -> a
eval Poly v a
p = forall a (v :: * -> *) (n :: Natural) (u :: * -> *).
(Semiring a, Vector v (Vector n Word, a), Vector u a) =>
MultiPoly v n a -> Vector u n a -> a
Multi.eval' Poly v a
p forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. a -> Vector 1 a
SV.singleton
{-# INLINABLE eval #-}

-- | Substitute another polynomial instead of 'X'.
--
-- >>> subst (X^2 + 1 :: UPoly Int) (X + 1 :: UPoly Int)
-- 1 * X^2 + 2 * X + 2
--
-- @since 0.3.3.0
subst
  :: (Eq a, Semiring a, G.Vector v (SU.Vector 1 Word, a), G.Vector w (SU.Vector 1 Word, a))
  => Poly v a
  -> Poly w a
  -> Poly w a
subst :: forall a (v :: * -> *) (w :: * -> *).
(Eq a, Semiring a, Vector v (Vector 1 Word, a),
 Vector w (Vector 1 Word, a)) =>
Poly v a -> Poly w a -> Poly w a
subst Poly v a
p = forall a (m :: Natural) (v :: * -> *) (n :: Natural) (w :: * -> *).
(Eq a, Semiring a, KnownNat m, Vector v (Vector n Word, a),
 Vector w (Vector m Word, a)) =>
MultiPoly v n a -> Vector n (MultiPoly w m a) -> MultiPoly w m a
Multi.subst' Poly v a
p forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. a -> Vector 1 a
SV.singleton
{-# INLINABLE subst #-}

-- | Take the derivative of the polynomial.
--
-- >>> deriv (X^3 + 3 * X) :: UPoly Int
-- 3 * X^2 + 3
--
-- @since 0.3.0.0
deriv
  :: (Eq a, Semiring a, G.Vector v (SU.Vector 1 Word, a))
  => Poly v a
  -> Poly v a
deriv :: forall a (v :: * -> *).
(Eq a, Semiring a, Vector v (Vector 1 Word, a)) =>
Poly v a -> Poly v a
deriv = forall a (v :: * -> *) (n :: Natural).
(Eq a, Semiring a, Vector v (Vector n Word, a)) =>
Finite n -> MultiPoly v n a -> MultiPoly v n a
Multi.deriv' Finite 1
0
{-# INLINABLE deriv #-}

-- | Compute an indefinite integral of the polynomial,
-- setting the constant term to zero.
--
-- >>> integral (3 * X^2 + 3) :: UPoly Double
-- 1.0 * X^3 + 3.0 * X
--
-- @since 0.3.2.0
integral
  :: (Field a, G.Vector v (SU.Vector 1 Word, a))
  => Poly v a
  -> Poly v a
integral :: forall a (v :: * -> *).
(Field a, Vector v (Vector 1 Word, a)) =>
Poly v a -> Poly v a
integral = forall a (v :: * -> *) (n :: Natural).
(Field a, Vector v (Vector n Word, a)) =>
Finite n -> MultiPoly v n a -> MultiPoly v n a
Multi.integral' Finite 1
0
{-# INLINABLE integral #-}

-- | Convert from dense to sparse polynomials.
--
-- >>> :set -XFlexibleContexts
-- >>> denseToSparse (1 `Data.Semiring.plus` Data.Poly.X^2) :: Data.Poly.Sparse.UPoly Int
-- 1 * X^2 + 1
--
-- @since 0.5.0.0
denseToSparse
  :: (Eq a, Semiring a, G.Vector v a, G.Vector v (SU.Vector 1 Word, a))
  => Dense.Poly v a
  -> Multi.Poly v a
denseToSparse :: forall a (v :: * -> *).
(Eq a, Semiring a, Vector v a, Vector v (Vector 1 Word, a)) =>
Poly v a -> Poly v a
denseToSparse = forall a (v :: * -> *).
(Eq a, Semiring a, Vector v a, Vector v (Vector 1 Word, a)) =>
Poly v a -> Poly v a
Convert.denseToSparse'
{-# INLINABLE denseToSparse #-}

-- | Convert from sparse to dense polynomials.
--
-- >>> :set -XFlexibleContexts
-- >>> sparseToDense (1 `Data.Semiring.plus` Data.Poly.Sparse.X^2) :: Data.Poly.UPoly Int
-- 1 * X^2 + 0 * X + 1
--
-- @since 0.5.0.0
sparseToDense
  :: (Semiring a, G.Vector v a, G.Vector v (SU.Vector 1 Word, a))
  => Multi.Poly v a
  -> Dense.Poly v a
sparseToDense :: forall a (v :: * -> *).
(Semiring a, Vector v a, Vector v (Vector 1 Word, a)) =>
Poly v a -> Poly v a
sparseToDense = forall a (v :: * -> *).
(Semiring a, Vector v a, Vector v (Vector 1 Word, a)) =>
Poly v a -> Poly v a
Convert.sparseToDense'
{-# INLINABLE sparseToDense #-}