    -- |
    -- 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 #-}