{-# LANGUAGE ViewPatterns, TypeFamilies, GADTs, UndecidableInstances #-}
-- |Low-level interface for the 'Poly' type.
module Math.Polynomial.Type 
    ( Endianness(..)
    , Poly
    
    , zero
    
    , poly, polyN
    , unboxedPoly, unboxedPolyN
    
    , mapPoly
    , rawMapPoly
    , wrapPoly
    , unwrapPoly
    
    , unboxPoly
    
    , rawListPoly
    , rawListPolyN
    , rawVectorPoly
    , rawUVectorPoly
    , trim
    , vTrim
    
    , polyIsZero
    , polyIsOne
    
    , polyCoeffs
    , vPolyCoeffs
    , rawCoeffsOrder
    , rawPolyCoeffs
    , untrimmedPolyCoeffs
    
    , polyDegree
    , rawPolyDegree
    , rawPolyLength
    
    ) where

import Control.DeepSeq
-- import Data.List.Extras.LazyLength
import Data.AdditiveGroup
import Data.VectorSpace
import Data.VectorSpace.WrappedNum
import Data.List.ZipSum
import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as UV

-- 'unsafeCoerce' is only used in 'wrapPoly' and 'unwrapPoly', which are
-- type-safe alternatives to 'fmap'ing the 'WrappedNum' newtype constructor/projector
import Unsafe.Coerce (unsafeCoerce)

data Endianness 
    = BE 
    -- ^ Big-Endian (head is highest-order term)
    | LE
    -- ^ Little-Endian (head is const term)
    deriving (Endianness -> Endianness -> Bool
(Endianness -> Endianness -> Bool)
-> (Endianness -> Endianness -> Bool) -> Eq Endianness
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Endianness -> Endianness -> Bool
$c/= :: Endianness -> Endianness -> Bool
== :: Endianness -> Endianness -> Bool
$c== :: Endianness -> Endianness -> Bool
Eq, Eq Endianness
Eq Endianness =>
(Endianness -> Endianness -> Ordering)
-> (Endianness -> Endianness -> Bool)
-> (Endianness -> Endianness -> Bool)
-> (Endianness -> Endianness -> Bool)
-> (Endianness -> Endianness -> Bool)
-> (Endianness -> Endianness -> Endianness)
-> (Endianness -> Endianness -> Endianness)
-> Ord Endianness
Endianness -> Endianness -> Bool
Endianness -> Endianness -> Ordering
Endianness -> Endianness -> Endianness
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: Endianness -> Endianness -> Endianness
$cmin :: Endianness -> Endianness -> Endianness
max :: Endianness -> Endianness -> Endianness
$cmax :: Endianness -> Endianness -> Endianness
>= :: Endianness -> Endianness -> Bool
$c>= :: Endianness -> Endianness -> Bool
> :: Endianness -> Endianness -> Bool
$c> :: Endianness -> Endianness -> Bool
<= :: Endianness -> Endianness -> Bool
$c<= :: Endianness -> Endianness -> Bool
< :: Endianness -> Endianness -> Bool
$c< :: Endianness -> Endianness -> Bool
compare :: Endianness -> Endianness -> Ordering
$ccompare :: Endianness -> Endianness -> Ordering
$cp1Ord :: Eq Endianness
Ord, Int -> Endianness
Endianness -> Int
Endianness -> [Endianness]
Endianness -> Endianness
Endianness -> Endianness -> [Endianness]
Endianness -> Endianness -> Endianness -> [Endianness]
(Endianness -> Endianness)
-> (Endianness -> Endianness)
-> (Int -> Endianness)
-> (Endianness -> Int)
-> (Endianness -> [Endianness])
-> (Endianness -> Endianness -> [Endianness])
-> (Endianness -> Endianness -> [Endianness])
-> (Endianness -> Endianness -> Endianness -> [Endianness])
-> Enum Endianness
forall a.
(a -> a)
-> (a -> a)
-> (Int -> a)
-> (a -> Int)
-> (a -> [a])
-> (a -> a -> [a])
-> (a -> a -> [a])
-> (a -> a -> a -> [a])
-> Enum a
enumFromThenTo :: Endianness -> Endianness -> Endianness -> [Endianness]
$cenumFromThenTo :: Endianness -> Endianness -> Endianness -> [Endianness]
enumFromTo :: Endianness -> Endianness -> [Endianness]
$cenumFromTo :: Endianness -> Endianness -> [Endianness]
enumFromThen :: Endianness -> Endianness -> [Endianness]
$cenumFromThen :: Endianness -> Endianness -> [Endianness]
enumFrom :: Endianness -> [Endianness]
$cenumFrom :: Endianness -> [Endianness]
fromEnum :: Endianness -> Int
$cfromEnum :: Endianness -> Int
toEnum :: Int -> Endianness
$ctoEnum :: Int -> Endianness
pred :: Endianness -> Endianness
$cpred :: Endianness -> Endianness
succ :: Endianness -> Endianness
$csucc :: Endianness -> Endianness
Enum, Endianness
Endianness -> Endianness -> Bounded Endianness
forall a. a -> a -> Bounded a
maxBound :: Endianness
$cmaxBound :: Endianness
minBound :: Endianness
$cminBound :: Endianness
Bounded, Int -> Endianness -> ShowS
[Endianness] -> ShowS
Endianness -> String
(Int -> Endianness -> ShowS)
-> (Endianness -> String)
-> ([Endianness] -> ShowS)
-> Show Endianness
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Endianness] -> ShowS
$cshowList :: [Endianness] -> ShowS
show :: Endianness -> String
$cshow :: Endianness -> String
showsPrec :: Int -> Endianness -> ShowS
$cshowsPrec :: Int -> Endianness -> ShowS
Show)

instance NFData Endianness where
    rnf :: Endianness -> ()
rnf x :: Endianness
x = Endianness -> () -> ()
forall a b. a -> b -> b
seq Endianness
x ()

data Poly a where
    ListPoly ::
        { Poly a -> Bool
trimmed    :: !Bool
        , Poly a -> Endianness
endianness :: !Endianness
        , Poly a -> [a]
listCoeffs :: ![a]
        } -> Poly a
    VectorPoly ::
        { trimmed    :: !Bool
        , endianness :: !Endianness
        , Poly a -> Vector a
vCoeffs    :: !(V.Vector a)
        } -> Poly a
    UVectorPoly :: UV.Unbox a => 
        { trimmed    :: !Bool
        , endianness :: !Endianness
        , Poly a -> Vector a
uvCoeffs   :: !(UV.Vector a)
        } -> Poly a

instance NFData a => NFData (Poly a) where
    rnf :: Poly a -> ()
rnf (ListPoly    _ _ c :: [a]
c) = [a] -> ()
forall a. NFData a => a -> ()
rnf [a]
c
    rnf (VectorPoly  _ _ c :: Vector a
c) = (a -> () -> ()) -> () -> Vector a -> ()
forall a b. (a -> b -> b) -> b -> Vector a -> b
V.foldr' a -> () -> ()
forall a b. a -> b -> b
seq () Vector a
c
    rnf (UVectorPoly _ _ _) = ()

instance Show a => Show (Poly a) where
    showsPrec :: Int -> Poly a -> ShowS
showsPrec p :: Int
p f :: Poly a
f
        = Bool -> ShowS -> ShowS
showParen (Int
p Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> 10) 
            ( String -> ShowS
showString "poly "
            ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Endianness -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec 11 (Poly a -> Endianness
forall a. Poly a -> Endianness
rawCoeffsOrder Poly a
f)
            ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> ShowS
showChar ' '
            ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> [a] -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec 11 (Poly a -> [a]
forall a. Poly a -> [a]
rawPolyCoeffs Poly a
f)
            )

-- TODO: specialize for case where one is a list and other is a vector;
--  use native order of the list
-- TODO: think about plain Num support...
instance (AdditiveGroup a, Eq a) => Eq (Poly a) where
    p :: Poly a
p == :: Poly a -> Poly a -> Bool
== q :: Poly a
q  
        | Poly a -> Endianness
forall a. Poly a -> Endianness
rawCoeffsOrder Poly a
p Endianness -> Endianness -> Bool
forall a. Eq a => a -> a -> Bool
== Poly a -> Endianness
forall a. Poly a -> Endianness
rawCoeffsOrder Poly a
q
        =  Poly a -> [a]
forall a. Poly a -> [a]
rawPolyCoeffs ((a -> Bool) -> Poly a -> Poly a
forall a. (a -> Bool) -> Poly a -> Poly a
trim (a
forall v. AdditiveGroup v => v
zeroVa -> a -> Bool
forall a. Eq a => a -> a -> Bool
==) Poly a
p) 
        [a] -> [a] -> Bool
forall a. Eq a => a -> a -> Bool
== Poly a -> [a]
forall a. Poly a -> [a]
rawPolyCoeffs ((a -> Bool) -> Poly a -> Poly a
forall a. (a -> Bool) -> Poly a -> Poly a
trim (a
forall v. AdditiveGroup v => v
zeroVa -> a -> Bool
forall a. Eq a => a -> a -> Bool
==) Poly a
q)
        | Bool
otherwise 
        =  Endianness -> Poly a -> [a]
forall a. (Eq a, AdditiveGroup a) => Endianness -> Poly a -> [a]
vPolyCoeffs Endianness
LE Poly a
p
        [a] -> [a] -> Bool
forall a. Eq a => a -> a -> Bool
== Endianness -> Poly a -> [a]
forall a. (Eq a, AdditiveGroup a) => Endianness -> Poly a -> [a]
vPolyCoeffs Endianness
LE Poly a
q

-- -- Ord would be nice for some purposes, but it really just doesn't
-- -- make sense (there is no natural order that is much better than any
-- -- other, AFAIK), so I'm leaving it out.
-- instance (Num a, Ord a) => Ord (Poly a) where
--     compare p q = mconcat
--             [ lengthCompare pCoeffs qCoeffs
--             , compare       pCoeffs qCoeffs
--             ]
--         where
--             pCoeffs = polyCoeffs BE p
--             qCoeffs = polyCoeffs BE q

instance Functor Poly where
    fmap :: (a -> b) -> Poly a -> Poly b
fmap f :: a -> b
f (ListPoly    _ end :: Endianness
end cs :: [a]
cs) = Bool -> Endianness -> [b] -> Poly b
forall a. Bool -> Endianness -> [a] -> Poly a
ListPoly   Bool
False Endianness
end ((a -> b) -> [a] -> [b]
forall a b. (a -> b) -> [a] -> [b]
map a -> b
f [a]
cs)
    fmap f :: a -> b
f (VectorPoly  _ end :: Endianness
end cs :: Vector a
cs) = Bool -> Endianness -> Vector b -> Poly b
forall a. Bool -> Endianness -> Vector a -> Poly a
VectorPoly Bool
False Endianness
end ((a -> b) -> Vector a -> Vector b
forall a b. (a -> b) -> Vector a -> Vector b
V.map a -> b
f Vector a
cs)
    -- TODO: make sure this gets fused
    fmap f :: a -> b
f (UVectorPoly _ end :: Endianness
end cs :: Vector a
cs) = Bool -> Endianness -> Vector b -> Poly b
forall a. Bool -> Endianness -> Vector a -> Poly a
VectorPoly Bool
False Endianness
end (Int -> [b] -> Vector b
forall a. Int -> [a] -> Vector a
V.fromListN Int
n ([b] -> Vector b) -> ([a] -> [b]) -> [a] -> Vector b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b) -> [a] -> [b]
forall a b. (a -> b) -> [a] -> [b]
map a -> b
f ([a] -> Vector b) -> [a] -> Vector b
forall a b. (a -> b) -> a -> b
$ Vector a -> [a]
forall a. Unbox a => Vector a -> [a]
UV.toList Vector a
cs)
        where n :: Int
n = Vector a -> Int
forall a. Unbox a => Vector a -> Int
UV.length Vector a
cs

-- |Like fmap, but able to preserve unboxedness
mapPoly :: (Num a, Eq a) => (a -> a) -> Poly a -> Poly a
mapPoly :: (a -> a) -> Poly a -> Poly a
mapPoly f :: a -> a
f = (a -> Bool) -> Poly a -> Poly a
forall a. (a -> Bool) -> Poly a -> Poly a
trim (0a -> a -> Bool
forall a. Eq a => a -> a -> Bool
==) (Poly a -> Poly a) -> (Poly a -> Poly a) -> Poly a -> Poly a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a) -> Poly a -> Poly a
forall a. (a -> a) -> Poly a -> Poly a
rawMapPoly a -> a
f

rawMapPoly :: (a -> a) -> Poly a -> Poly a
rawMapPoly :: (a -> a) -> Poly a -> Poly a
rawMapPoly f :: a -> a
f (ListPoly    _ e :: Endianness
e cs :: [a]
cs) = Bool -> Endianness -> [a] -> Poly a
forall a. Bool -> Endianness -> [a] -> Poly a
ListPoly    Bool
False Endianness
e (   (a -> a) -> [a] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map a -> a
f [a]
cs)
rawMapPoly f :: a -> a
f (VectorPoly  _ e :: Endianness
e cs :: Vector a
cs) = Bool -> Endianness -> Vector a -> Poly a
forall a. Bool -> Endianness -> Vector a -> Poly a
VectorPoly  Bool
False Endianness
e ( (a -> a) -> Vector a -> Vector a
forall a b. (a -> b) -> Vector a -> Vector b
V.map a -> a
f Vector a
cs)
rawMapPoly f :: a -> a
f (UVectorPoly _ e :: Endianness
e cs :: Vector a
cs) = Bool -> Endianness -> Vector a -> Poly a
forall a. Unbox a => Bool -> Endianness -> Vector a -> Poly a
UVectorPoly Bool
False Endianness
e ((a -> a) -> Vector a -> Vector a
forall a b. (Unbox a, Unbox b) => (a -> b) -> Vector a -> Vector b
UV.map a -> a
f Vector a
cs)

{-# RULES "wrapPoly/unwrapPoly"   forall x. wrapPoly (unwrapPoly x) = x #-}
{-# RULES "unwrapPoly/wrapPoly"   forall x. unwrapPoly (wrapPoly x) = x #-}
{-# RULES "wrapPoly.unwrapPoly"   wrapPoly . unwrapPoly = id #-}
{-# RULES "unwrapPoly.wrapPoly"   unwrapPoly . wrapPoly = id #-}
-- |like @fmap WrapNum@ but using 'unsafeCoerce' to avoid a pointless traversal
wrapPoly :: Poly a -> Poly (WrappedNum a)
wrapPoly :: Poly a -> Poly (WrappedNum a)
wrapPoly = Poly a -> Poly (WrappedNum a)
forall a b. a -> b
unsafeCoerce

-- |like @fmap unwrapNum@ but using 'unsafeCoerce' to avoid a pointless traversal
unwrapPoly :: Poly (WrappedNum a) -> Poly a
unwrapPoly :: Poly (WrappedNum a) -> Poly a
unwrapPoly = Poly (WrappedNum a) -> Poly a
forall a b. a -> b
unsafeCoerce

instance AdditiveGroup a => AdditiveGroup (Poly a) where
    zeroV :: Poly a
zeroV = Bool -> Endianness -> [a] -> Poly a
forall a. Bool -> Endianness -> [a] -> Poly a
ListPoly Bool
True Endianness
LE []
    (Endianness -> Poly a -> [a]
forall a. Endianness -> Poly a -> [a]
untrimmedPolyCoeffs Endianness
LE ->  [a]
a) ^+^ :: Poly a -> Poly a -> Poly a
^+^ (Endianness -> Poly a -> [a]
forall a. Endianness -> Poly a -> [a]
untrimmedPolyCoeffs Endianness
LE ->  [a]
b) 
        = Bool -> Endianness -> [a] -> Poly a
forall a. Bool -> Endianness -> [a] -> Poly a
ListPoly Bool
False Endianness
LE ([a] -> [a] -> [a]
forall t. AdditiveGroup t => [t] -> [t] -> [t]
zipSumV [a]
a [a]
b)
    negateV :: Poly a -> Poly a
negateV = (a -> a) -> Poly a -> Poly a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> a
forall v. AdditiveGroup v => v -> v
negateV

instance (Eq a, VectorSpace a, AdditiveGroup (Scalar a), Eq (Scalar a)) => VectorSpace (Poly a) where
    type Scalar (Poly a) = Scalar a
    s :: Scalar (Poly a)
s *^ :: Scalar (Poly a) -> Poly a -> Poly a
*^ v :: Poly a
v
         | Scalar a
Scalar (Poly a)
s Scalar a -> Scalar a -> Bool
forall a. Eq a => a -> a -> Bool
== Scalar a
forall v. AdditiveGroup v => v
zeroV   = Poly a
forall v. AdditiveGroup v => v
zeroV
         | Bool
otherwise    = Poly a -> Poly a
forall a. (Eq a, AdditiveGroup a) => Poly a -> Poly a
vTrim ((a -> a) -> Poly a -> Poly a
forall a. (a -> a) -> Poly a -> Poly a
rawMapPoly (Scalar a
Scalar (Poly a)
s Scalar a -> a -> a
forall v. VectorSpace v => Scalar v -> v -> v
*^) Poly a
v)

-- |Trim zeroes from a polynomial (given a predicate for identifying zero).
-- In particular, drops zeroes from the highest-order coefficients, so that
-- @0x^n + 0x^(n-1) + 0x^(n-2) + ... + ax^k + ...@, @a /= 0@
-- is normalized to @ax^k + ...@.  
-- 
-- The 'Eq' instance for 'Poly' and all the standard constructors / destructors
-- are defined using @trim (0==)@.
trim :: (a -> Bool) -> Poly a -> Poly a
trim :: (a -> Bool) -> Poly a -> Poly a
trim _ p :: Poly a
p | Poly a -> Bool
forall a. Poly a -> Bool
trimmed Poly a
p = Poly a
p
trim isZero :: a -> Bool
isZero   (ListPoly    _ LE cs :: [a]
cs) = Bool -> Endianness -> [a] -> Poly a
forall a. Bool -> Endianness -> [a] -> Poly a
ListPoly    Bool
True Endianness
LE ((a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
dropEnd   a -> Bool
isZero [a]
cs)
trim isZero :: a -> Bool
isZero   (ListPoly    _ BE cs :: [a]
cs) = Bool -> Endianness -> [a] -> Poly a
forall a. Bool -> Endianness -> [a] -> Poly a
ListPoly    Bool
True Endianness
BE ((a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
dropWhile a -> Bool
isZero [a]
cs)
trim isZero :: a -> Bool
isZero   (VectorPoly  _ LE cs :: Vector a
cs) = Bool -> Endianness -> Vector a -> Poly a
forall a. Bool -> Endianness -> Vector a -> Poly a
VectorPoly  Bool
True Endianness
LE (Vector a -> Vector a
forall a. Vector a -> Vector a
V.reverse (Vector a -> Vector a)
-> (Vector a -> Vector a) -> Vector a -> Vector a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Bool) -> Vector a -> Vector a
forall a. (a -> Bool) -> Vector a -> Vector a
V.dropWhile a -> Bool
isZero (Vector a -> Vector a)
-> (Vector a -> Vector a) -> Vector a -> Vector a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vector a -> Vector a
forall a. Vector a -> Vector a
V.reverse (Vector a -> Vector a) -> Vector a -> Vector a
forall a b. (a -> b) -> a -> b
$ Vector a
cs)
trim isZero :: a -> Bool
isZero   (VectorPoly  _ BE cs :: Vector a
cs) = Bool -> Endianness -> Vector a -> Poly a
forall a. Bool -> Endianness -> Vector a -> Poly a
VectorPoly  Bool
True Endianness
BE ((a -> Bool) -> Vector a -> Vector a
forall a. (a -> Bool) -> Vector a -> Vector a
V.dropWhile a -> Bool
isZero Vector a
cs)
trim isZero :: a -> Bool
isZero   (UVectorPoly _ LE cs :: Vector a
cs) = Bool -> Endianness -> Vector a -> Poly a
forall a. Unbox a => Bool -> Endianness -> Vector a -> Poly a
UVectorPoly Bool
True Endianness
LE (Vector a -> Vector a
forall a. Unbox a => Vector a -> Vector a
UV.reverse (Vector a -> Vector a)
-> (Vector a -> Vector a) -> Vector a -> Vector a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Bool) -> Vector a -> Vector a
forall a. Unbox a => (a -> Bool) -> Vector a -> Vector a
UV.dropWhile a -> Bool
isZero (Vector a -> Vector a)
-> (Vector a -> Vector a) -> Vector a -> Vector a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vector a -> Vector a
forall a. Unbox a => Vector a -> Vector a
UV.reverse (Vector a -> Vector a) -> Vector a -> Vector a
forall a b. (a -> b) -> a -> b
$ Vector a
cs)
trim isZero :: a -> Bool
isZero   (UVectorPoly _ BE cs :: Vector a
cs) = Bool -> Endianness -> Vector a -> Poly a
forall a. Unbox a => Bool -> Endianness -> Vector a -> Poly a
UVectorPoly Bool
True Endianness
BE ((a -> Bool) -> Vector a -> Vector a
forall a. Unbox a => (a -> Bool) -> Vector a -> Vector a
UV.dropWhile a -> Bool
isZero Vector a
cs)

vTrim :: (Eq a, AdditiveGroup a) => Poly a -> Poly a
vTrim :: Poly a -> Poly a
vTrim = (a -> Bool) -> Poly a -> Poly a
forall a. (a -> Bool) -> Poly a -> Poly a
trim (a
forall v. AdditiveGroup v => v
zeroV a -> a -> Bool
forall a. Eq a => a -> a -> Bool
==)

-- |The polynomial \"0\"
zero :: Poly a
zero :: Poly a
zero = Bool -> Endianness -> [a] -> Poly a
forall a. Bool -> Endianness -> [a] -> Poly a
ListPoly Bool
True Endianness
LE []

-- |Make a 'Poly' from a list of coefficients using the specified coefficient order.
poly :: (Num a, Eq a) => Endianness -> [a] -> Poly a
poly :: Endianness -> [a] -> Poly a
poly end :: Endianness
end = (a -> Bool) -> Poly a -> Poly a
forall a. (a -> Bool) -> Poly a -> Poly a
trim (0a -> a -> Bool
forall a. Eq a => a -> a -> Bool
==) (Poly a -> Poly a) -> ([a] -> Poly a) -> [a] -> Poly a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Endianness -> [a] -> Poly a
forall a. Endianness -> [a] -> Poly a
rawListPoly Endianness
end

-- |Make a 'Poly' from a list of coefficients, at most 'n' of which are significant.
polyN :: (Num a, Eq a) => Int -> Endianness -> [a] -> Poly a
polyN :: Int -> Endianness -> [a] -> Poly a
polyN n :: Int
n end :: Endianness
end = (a -> Bool) -> Poly a -> Poly a
forall a. (a -> Bool) -> Poly a -> Poly a
trim (0a -> a -> Bool
forall a. Eq a => a -> a -> Bool
==) (Poly a -> Poly a) -> ([a] -> Poly a) -> [a] -> Poly a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Endianness -> Vector a -> Poly a
forall a. Endianness -> Vector a -> Poly a
rawVectorPoly Endianness
end (Vector a -> Poly a) -> ([a] -> Vector a) -> [a] -> Poly a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> [a] -> Vector a
forall a. Int -> [a] -> Vector a
V.fromListN Int
n

unboxedPoly :: (UV.Unbox a, Num a, Eq a) => Endianness -> [a] -> Poly a
unboxedPoly :: Endianness -> [a] -> Poly a
unboxedPoly end :: Endianness
end = (a -> Bool) -> Poly a -> Poly a
forall a. (a -> Bool) -> Poly a -> Poly a
trim (0a -> a -> Bool
forall a. Eq a => a -> a -> Bool
==) (Poly a -> Poly a) -> ([a] -> Poly a) -> [a] -> Poly a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Endianness -> Vector a -> Poly a
forall a. Unbox a => Endianness -> Vector a -> Poly a
rawUVectorPoly Endianness
end (Vector a -> Poly a) -> ([a] -> Vector a) -> [a] -> Poly a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> Vector a
forall a. Unbox a => [a] -> Vector a
UV.fromList

unboxedPolyN :: (UV.Unbox a, Num a, Eq a) => Int -> Endianness -> [a] -> Poly a
unboxedPolyN :: Int -> Endianness -> [a] -> Poly a
unboxedPolyN n :: Int
n end :: Endianness
end = (a -> Bool) -> Poly a -> Poly a
forall a. (a -> Bool) -> Poly a -> Poly a
trim (0a -> a -> Bool
forall a. Eq a => a -> a -> Bool
==) (Poly a -> Poly a) -> ([a] -> Poly a) -> [a] -> Poly a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Endianness -> Vector a -> Poly a
forall a. Unbox a => Endianness -> Vector a -> Poly a
rawUVectorPoly Endianness
end (Vector a -> Poly a) -> ([a] -> Vector a) -> [a] -> Poly a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> [a] -> Vector a
forall a. Unbox a => Int -> [a] -> Vector a
UV.fromListN Int
n

unboxPoly :: UV.Unbox a => Poly a -> Poly a
unboxPoly :: Poly a -> Poly a
unboxPoly (ListPoly   t :: Bool
t e :: Endianness
e cs :: [a]
cs) = Bool -> Endianness -> Vector a -> Poly a
forall a. Unbox a => Bool -> Endianness -> Vector a -> Poly a
UVectorPoly Bool
t Endianness
e ([a] -> Vector a
forall a. Unbox a => [a] -> Vector a
UV.fromList [a]
cs)
unboxPoly (VectorPoly t :: Bool
t e :: Endianness
e cs :: Vector a
cs) = Bool -> Endianness -> Vector a -> Poly a
forall a. Unbox a => Bool -> Endianness -> Vector a -> Poly a
UVectorPoly Bool
t Endianness
e (Int -> [a] -> Vector a
forall a. Unbox a => Int -> [a] -> Vector a
UV.fromListN (Vector a -> Int
forall a. Vector a -> Int
V.length Vector a
cs) (Vector a -> [a]
forall a. Vector a -> [a]
V.toList Vector a
cs))
unboxPoly p :: Poly a
p@UVectorPoly{} = Poly a
p

-- |Make a 'Poly' from a list of coefficients using the specified coefficient order,
-- without the 'Num' context (and therefore without trimming zeroes from the 
-- coefficient list)
rawListPoly :: Endianness -> [a] -> Poly a
rawListPoly :: Endianness -> [a] -> Poly a
rawListPoly = Bool -> Endianness -> [a] -> Poly a
forall a. Bool -> Endianness -> [a] -> Poly a
ListPoly Bool
False

rawListPolyN :: Int -> Endianness -> [a] -> Poly a
rawListPolyN :: Int -> Endianness -> [a] -> Poly a
rawListPolyN n :: Int
n e :: Endianness
e = Endianness -> Vector a -> Poly a
forall a. Endianness -> Vector a -> Poly a
rawVectorPoly Endianness
e (Vector a -> Poly a) -> ([a] -> Vector a) -> [a] -> Poly a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> [a] -> Vector a
forall a. Int -> [a] -> Vector a
V.fromListN Int
n

rawVectorPoly :: Endianness -> V.Vector a -> Poly a
rawVectorPoly :: Endianness -> Vector a -> Poly a
rawVectorPoly = Bool -> Endianness -> Vector a -> Poly a
forall a. Bool -> Endianness -> Vector a -> Poly a
VectorPoly Bool
False

rawUVectorPoly :: UV.Unbox a => Endianness -> UV.Vector a -> Poly a
rawUVectorPoly :: Endianness -> Vector a -> Poly a
rawUVectorPoly = Bool -> Endianness -> Vector a -> Poly a
forall a. Unbox a => Bool -> Endianness -> Vector a -> Poly a
UVectorPoly Bool
False

-- |Get the degree of a a 'Poly' (the highest exponent with nonzero coefficient)
polyDegree :: (Num a, Eq a) => Poly a -> Int
polyDegree :: Poly a -> Int
polyDegree p :: Poly a
p = Poly a -> Int
forall a. Poly a -> Int
rawPolyDegree ((a -> Bool) -> Poly a -> Poly a
forall a. (a -> Bool) -> Poly a -> Poly a
trim (0a -> a -> Bool
forall a. Eq a => a -> a -> Bool
==) Poly a
p)

rawPolyDegree :: Poly a -> Int
rawPolyDegree :: Poly a -> Int
rawPolyDegree p :: Poly a
p = Poly a -> Int
forall a. Poly a -> Int
rawPolyLength Poly a
p Int -> Int -> Int
forall a. Num a => a -> a -> a
- 1

rawPolyLength :: Poly a -> Int
rawPolyLength :: Poly a -> Int
rawPolyLength (ListPoly    _ _ cs :: [a]
cs) =    [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
cs
rawPolyLength (VectorPoly  _ _ cs :: Vector a
cs) =  Vector a -> Int
forall a. Vector a -> Int
V.length Vector a
cs
rawPolyLength (UVectorPoly _ _ cs :: Vector a
cs) = Vector a -> Int
forall a. Unbox a => Vector a -> Int
UV.length Vector a
cs


-- |Get the coefficients of a a 'Poly' in the specified order.
polyCoeffs :: (Num a, Eq a) => Endianness -> Poly a -> [a]
polyCoeffs :: Endianness -> Poly a -> [a]
polyCoeffs end :: Endianness
end p :: Poly a
p = Endianness -> Poly a -> [a]
forall a. Endianness -> Poly a -> [a]
untrimmedPolyCoeffs Endianness
end ((a -> Bool) -> Poly a -> Poly a
forall a. (a -> Bool) -> Poly a -> Poly a
trim (0 a -> a -> Bool
forall a. Eq a => a -> a -> Bool
==) Poly a
p)

-- |Get the coefficients of a a 'Poly' in the specified order.
vPolyCoeffs :: (Eq a, AdditiveGroup a) => Endianness -> Poly a -> [a]
vPolyCoeffs :: Endianness -> Poly a -> [a]
vPolyCoeffs end :: Endianness
end p :: Poly a
p = Endianness -> Poly a -> [a]
forall a. Endianness -> Poly a -> [a]
untrimmedPolyCoeffs Endianness
end (Poly a -> Poly a
forall a. (Eq a, AdditiveGroup a) => Poly a -> Poly a
vTrim Poly a
p)

polyIsZero :: (Num a, Eq a) => Poly a -> Bool
polyIsZero :: Poly a -> Bool
polyIsZero = [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null ([a] -> Bool) -> (Poly a -> [a]) -> Poly a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Poly a -> [a]
forall a. Poly a -> [a]
rawPolyCoeffs (Poly a -> [a]) -> (Poly a -> Poly a) -> Poly a -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Bool) -> Poly a -> Poly a
forall a. (a -> Bool) -> Poly a -> Poly a
trim (0a -> a -> Bool
forall a. Eq a => a -> a -> Bool
==)

polyIsOne :: (Num a, Eq a) => Poly a -> Bool
polyIsOne :: Poly a -> Bool
polyIsOne = ([1][a] -> [a] -> Bool
forall a. Eq a => a -> a -> Bool
==) ([a] -> Bool) -> (Poly a -> [a]) -> Poly a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Poly a -> [a]
forall a. Poly a -> [a]
rawPolyCoeffs (Poly a -> [a]) -> (Poly a -> Poly a) -> Poly a -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Bool) -> Poly a -> Poly a
forall a. (a -> Bool) -> Poly a -> Poly a
trim (0a -> a -> Bool
forall a. Eq a => a -> a -> Bool
==)

rawCoeffsOrder :: Poly a -> Endianness
rawCoeffsOrder :: Poly a -> Endianness
rawCoeffsOrder = Poly a -> Endianness
forall a. Poly a -> Endianness
endianness

rawPolyCoeffs :: Poly a -> [a]
rawPolyCoeffs :: Poly a -> [a]
rawPolyCoeffs p :: Poly a
p@ListPoly{}         = Poly a -> [a]
forall a. Poly a -> [a]
listCoeffs Poly a
p
rawPolyCoeffs p :: Poly a
p@VectorPoly{}       = Vector a -> [a]
forall a. Vector a -> [a]
V.toList (Poly a -> Vector a
forall a. Poly a -> Vector a
vCoeffs Poly a
p)
rawPolyCoeffs p :: Poly a
p@UVectorPoly{}      = Vector a -> [a]
forall a. Unbox a => Vector a -> [a]
UV.toList (Poly a -> Vector a
forall a. Poly a -> Vector a
uvCoeffs Poly a
p)

-- TODO: make sure (V.toList . V.reverse) gets fused
untrimmedPolyCoeffs :: Endianness -> Poly a -> [a]
untrimmedPolyCoeffs :: Endianness -> Poly a -> [a]
untrimmedPolyCoeffs e1 :: Endianness
e1 (VectorPoly  _ e2 :: Endianness
e2 cs :: Vector a
cs)
    | Endianness
e1 Endianness -> Endianness -> Bool
forall a. Eq a => a -> a -> Bool
== Endianness
e2  = Vector a -> [a]
forall a. Vector a -> [a]
V.toList Vector a
cs
    | Bool
otherwise = Vector a -> [a]
forall a. Vector a -> [a]
V.toList  (Vector a -> Vector a
forall a. Vector a -> Vector a
V.reverse Vector a
cs)
untrimmedPolyCoeffs e1 :: Endianness
e1 (UVectorPoly _ e2 :: Endianness
e2 cs :: Vector a
cs)
    | Endianness
e1 Endianness -> Endianness -> Bool
forall a. Eq a => a -> a -> Bool
== Endianness
e2  = Vector a -> [a]
forall a. Unbox a => Vector a -> [a]
UV.toList Vector a
cs
    | Bool
otherwise = Vector a -> [a]
forall a. Unbox a => Vector a -> [a]
UV.toList (Vector a -> Vector a
forall a. Unbox a => Vector a -> Vector a
UV.reverse Vector a
cs)
untrimmedPolyCoeffs e1 :: Endianness
e1 (ListPoly _ e2 :: Endianness
e2 cs :: [a]
cs)
    | Endianness
e1 Endianness -> Endianness -> Bool
forall a. Eq a => a -> a -> Bool
== Endianness
e2  = [a]
cs
    | Bool
otherwise = [a] -> [a]
forall a. [a] -> [a]
reverse [a]
cs

dropEnd :: (a -> Bool) -> [a] -> [a]
-- dropEnd p = reverse . dropWhile p . reverse
dropEnd :: (a -> Bool) -> [a] -> [a]
dropEnd p :: a -> Bool
p = ([a] -> [a]) -> [a] -> [a]
go [a] -> [a]
forall a. a -> a
id
    where
        go :: ([a] -> [a]) -> [a] -> [a]
go t :: [a] -> [a]
t (x :: a
x:xs :: [a]
xs)
            -- if p x, stash x (will only be used if 'not (any p xs)')
            | a -> Bool
p a
x       =        ([a] -> [a]) -> [a] -> [a]
go ([a] -> [a]
t([a] -> [a]) -> ([a] -> [a]) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:))  [a]
xs
            -- otherwise insert x and all stashed values in output and reset the stash
            | Bool
otherwise = [a] -> [a]
t (a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: ([a] -> [a]) -> [a] -> [a]
go  [a] -> [a]
forall a. a -> a
id       [a]
xs)
        -- at end of string discard the stash
        go _ [] = []