-- |
-- 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 = v (Vector 1 Word, a) -> MultiPoly v 1 a
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' (v (Vector 1 Word, a) -> MultiPoly v 1 a)
-> (v (Word, a) -> v (Vector 1 Word, a))
-> v (Word, a)
-> MultiPoly v 1 a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Word, a) -> (Vector 1 Word, a))
-> v (Word, a) -> v (Vector 1 Word, a)
forall (v :: * -> *) a b.
(Vector v a, Vector v b) =>
(a -> b) -> v a -> v b
G.map ((Word -> Vector 1 Word) -> (Word, a) -> (Vector 1 Word, a)
forall b c d. (b -> c) -> (b, d) -> (c, d)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first Word -> Vector 1 Word
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 = Vector 1 Word -> a -> MultiPoly v 1 a
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' (Vector 1 Word -> a -> MultiPoly v 1 a)
-> (Word -> Vector 1 Word) -> Word -> a -> MultiPoly v 1 a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word -> Vector 1 Word
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 = Vector 1 Word -> a -> MultiPoly v 1 a -> MultiPoly v 1 a
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' (Vector 1 Word -> a -> MultiPoly v 1 a -> MultiPoly v 1 a)
-> (Word -> Vector 1 Word)
-> Word
-> a
-> MultiPoly v 1 a
-> MultiPoly v 1 a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word -> Vector 1 Word
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 $mX :: forall {r} {a} {v :: * -> *}.
(Eq a, Semiring a, Vector v (Vector 1 Word, a)) =>
Poly v a -> ((# #) -> r) -> ((# #) -> r) -> r
$bX :: forall a (v :: * -> *).
(Eq a, Semiring a, Vector v (Vector 1 Word, a)) =>
Poly v a
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 = Poly v a -> Vector Vector 1 a -> a
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 (Vector Vector 1 a -> a) -> (a -> Vector Vector 1 a) -> a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Vector Vector 1 a
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 = Poly v a -> Vector 1 (MultiPoly w 1 a) -> MultiPoly w 1 a
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 (Vector 1 (MultiPoly w 1 a) -> MultiPoly w 1 a)
-> (MultiPoly w 1 a -> Vector 1 (MultiPoly w 1 a))
-> MultiPoly w 1 a
-> MultiPoly w 1 a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MultiPoly w 1 a -> Vector 1 (MultiPoly w 1 a)
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 = Finite 1 -> MultiPoly v 1 a -> MultiPoly v 1 a
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 = Finite 1 -> MultiPoly v 1 a -> MultiPoly v 1 a
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 = Poly v a -> Poly v a
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 = Poly v a -> Poly v a
forall a (v :: * -> *).
(Semiring a, Vector v a, Vector v (Vector 1 Word, a)) =>
Poly v a -> Poly v a
Convert.sparseToDense'
{-# INLINABLE sparseToDense #-}