-- |
-- Module    : Numeric.Polynomial
-- Copyright : (c) 2012 Aleksey Khudyakov
-- License   : BSD3
--
-- Maintainer  : bos@serpentine.com
-- Stability   : experimental
-- Portability : portable
--
-- Function for evaluating polynomials using Horher's method.
module Numeric.Polynomial (
    -- * Polynomials
    evaluatePolynomial
  , evaluateEvenPolynomial
  , evaluateOddPolynomial
    -- ** Lists
    -- $list
  , evaluatePolynomialL
  , evaluateEvenPolynomialL
  , evaluateOddPolynomialL
  ) where

import qualified Data.Vector.Generic as G
import qualified Data.Vector         as V
import           Data.Vector.Generic  (Vector)


-- | Evaluate polynomial using Horner's method. Coefficients starts
-- from lowest. In pseudocode:
--
-- > evaluateOddPolynomial x [1,2,3] = 1 + 2*x + 3*x^2
evaluatePolynomial :: (Vector v a, Num a)
                   => a    -- ^ /x/
                   -> v a  -- ^ Coefficients
                   -> a
{-# INLINE evaluatePolynomial #-}
evaluatePolynomial :: forall (v :: * -> *) a. (Vector v a, Num a) => a -> v a -> a
evaluatePolynomial a
x v a
v
  | v a -> Bool
forall (v :: * -> *) a. Vector v a => v a -> Bool
G.null v a
v  = a
0
  | Bool
otherwise = (a -> a -> a) -> v a -> a
forall (v :: * -> *) a. Vector v a => (a -> a -> a) -> v a -> a
G.foldr1 (\a
a a
r -> a
a a -> a -> a
forall a. Num a => a -> a -> a
+ a
ra -> a -> a
forall a. Num a => a -> a -> a
*a
x) v a
v

-- | Evaluate polynomial with only even powers using Horner's method.
-- Coefficients starts from lowest. In pseudocode:
--
-- > evaluateOddPolynomial x [1,2,3] = 1 + 2*x^2 + 3*x^4
evaluateEvenPolynomial :: (Vector v a, Num a)
                       => a    -- ^ /x/
                       -> v a  -- ^ Coefficients
                       -> a
{-# INLINE evaluateEvenPolynomial #-}
evaluateEvenPolynomial :: forall (v :: * -> *) a. (Vector v a, Num a) => a -> v a -> a
evaluateEvenPolynomial a
x
  = a -> v a -> a
forall (v :: * -> *) a. (Vector v a, Num a) => a -> v a -> a
evaluatePolynomial (a
xa -> a -> a
forall a. Num a => a -> a -> a
*a
x)


-- | Evaluate polynomial with only odd powers using Horner's method.
-- Coefficients starts from lowest. In pseudocode:
--
-- > evaluateOddPolynomial x [1,2,3] = 1*x + 2*x^3 + 3*x^5
evaluateOddPolynomial :: (Vector v a, Num a)
                       => a    -- ^ /x/
                       -> v a  -- ^ Coefficients
                       -> a
{-# INLINE evaluateOddPolynomial #-}
evaluateOddPolynomial :: forall (v :: * -> *) a. (Vector v a, Num a) => a -> v a -> a
evaluateOddPolynomial a
x v a
coefs
  = a
x a -> a -> a
forall a. Num a => a -> a -> a
* a -> v a -> a
forall (v :: * -> *) a. (Vector v a, Num a) => a -> v a -> a
evaluatePolynomial (a
xa -> a -> a
forall a. Num a => a -> a -> a
*a
x) v a
coefs




-- $lists
--
-- When all coefficients are known statically it's more convenient to
-- pass coefficient in a list instead of vector. Functions below
-- provide just that functionality. If list is known statically it
-- will be inlined anyway.

evaluatePolynomialL :: (Num a) => a -> [a] -> a
evaluatePolynomialL :: forall a. Num a => a -> [a] -> a
evaluatePolynomialL a
x = a -> Vector a -> a
forall (v :: * -> *) a. (Vector v a, Num a) => a -> v a -> a
evaluatePolynomial a
x (Vector a -> a) -> ([a] -> Vector a) -> [a] -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> Vector a
forall a. [a] -> Vector a
V.fromList
{-# INLINE evaluatePolynomialL #-}

evaluateEvenPolynomialL :: (Num a) => a -> [a] -> a
evaluateEvenPolynomialL :: forall a. Num a => a -> [a] -> a
evaluateEvenPolynomialL a
x = a -> Vector a -> a
forall (v :: * -> *) a. (Vector v a, Num a) => a -> v a -> a
evaluateEvenPolynomial a
x (Vector a -> a) -> ([a] -> Vector a) -> [a] -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> Vector a
forall a. [a] -> Vector a
V.fromList
{-# INLINE evaluateEvenPolynomialL #-}

evaluateOddPolynomialL :: (Num a) => a -> [a] -> a
evaluateOddPolynomialL :: forall a. Num a => a -> [a] -> a
evaluateOddPolynomialL a
x = a -> Vector a -> a
forall (v :: * -> *) a. (Vector v a, Num a) => a -> v a -> a
evaluateOddPolynomial a
x (Vector a -> a) -> ([a] -> Vector a) -> [a] -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> Vector a
forall a. [a] -> Vector a
V.fromList
{-# INLINE evaluateOddPolynomialL #-}