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

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

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

import Control.Arrow
import qualified Data.Vector.Generic as G
import qualified Data.Vector.Unboxed.Sized as SU
import qualified Data.Vector.Sized as SV

import Data.Poly.Internal.Convert
import Data.Poly.Internal.Multi (Poly, VPoly, UPoly, unPoly, leading)
import qualified Data.Poly.Internal.Multi as Multi
import Data.Poly.Internal.Multi.Field (quotRemFractional)
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, Num 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, Num 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, Num 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, Num a, G.Vector v (SU.Vector 1 Word, a))
  => Word
  -> a
  -> Poly v a
monomial :: forall a (v :: * -> *).
(Eq a, Num 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, Num 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, Num a, G.Vector v (SU.Vector 1 Word, a))
  => Word
  -> a
  -> Poly v a
  -> Poly v a
scale :: forall a (v :: * -> *).
(Eq a, Num 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, Num 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 1
--
-- @since 0.3.0.0
pattern X
  :: (Eq a, Num a, G.Vector v (SU.Vector 1 Word, a))
  => Poly v a
pattern $mX :: forall {r} {a} {v :: * -> *}.
(Eq a, Num a, Vector v (Vector 1 Word, a)) =>
Poly v a -> ((# #) -> r) -> ((# #) -> r) -> r
$bX :: forall a (v :: * -> *).
(Eq a, Num 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
  :: (Num a, G.Vector v (SU.Vector 1 Word, a))
  => Poly v a
  -> a
  -> a
eval :: forall a (v :: * -> *).
(Num 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 :: * -> *).
(Num 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, Num 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, Num 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, Num 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, Num a, G.Vector v (SU.Vector 1 Word, a))
  => Poly v a
  -> Poly v a
deriv :: forall a (v :: * -> *).
(Eq a, Num 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, Num 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.0.0
integral
  :: (Fractional a, G.Vector v (SU.Vector 1 Word, a))
  => Poly v a
  -> Poly v a
integral :: forall a (v :: * -> *).
(Fractional 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).
(Fractional a, Vector v (Vector n Word, a)) =>
Finite n -> MultiPoly v n a -> MultiPoly v n a
Multi.integral Finite 1
0
{-# INLINABLE integral #-}