module Math.Polynomial.Type
( Endianness(..)
, Poly, poly, polyCoeffs
, trim, rawPoly, rawPolyCoeffs
, polyIsZero, polyIsOne
) where
import Control.DeepSeq
import Data.AdditiveGroup
import Data.VectorSpace
import Data.List.ZipSum
dropEnd :: (a -> Bool) -> [a] -> [a]
dropEnd p = go id
where
go t (x:xs)
| p x = go (t.(x:)) xs
| otherwise = t (x : go id xs)
go _ [] = []
trim :: (a -> Bool) -> Poly a -> Poly a
trim _ p@(Poly _ True _) = p
trim isZero (Poly LE _ cs) = Poly LE True (dropEnd isZero cs)
trim isZero (Poly BE _ cs) = Poly BE True (dropWhile isZero cs)
poly :: Num a => Endianness -> [a] -> Poly a
poly end cs = trim (0==) (rawPoly end cs)
rawPoly :: Endianness -> [a] -> Poly a
rawPoly end cs = Poly end False cs
polyCoeffs :: Num a => Endianness -> Poly a -> [a]
polyCoeffs end p = rawPolyCoeffs end (trim (0==) p)
rawPolyCoeffs :: Endianness -> Poly a -> [a]
rawPolyCoeffs end (Poly e _ cs)
| e == end = cs
| otherwise = reverse cs
polyIsZero :: Num a => Poly a -> Bool
polyIsZero = null . coeffs . trim (0==)
polyIsOne :: Num a => Poly a -> Bool
polyIsOne = ([1]==) . coeffs . trim (0==)
data Endianness
= BE
| LE
deriving (Eq, Ord, Enum, Bounded, Show)
instance NFData Endianness where
rnf x = seq x ()
data Poly a = Poly
{ endianness :: !Endianness
, _trimmed :: !Bool
, coeffs :: ![a]
}
instance NFData a => NFData (Poly a) where
rnf (Poly e t c) = rnf e `seq` rnf t `seq` rnf c
instance Num a => Show (Poly a) where
showsPrec p (trim (0==) -> Poly end _ cs)
= showParen (p > 10)
( showString "poly "
. showsPrec 11 end
. showChar ' '
. showsPrec 11 cs
)
instance (Num a, Eq a) => Eq (Poly a) where
p == q
| endianness p == endianness q
= coeffs (trim (0==) p) == coeffs (trim (0==) q)
| otherwise
= polyCoeffs BE p == polyCoeffs BE q
instance Functor Poly where
fmap f (Poly end _ cs) = Poly end False (map f cs)
instance AdditiveGroup a => AdditiveGroup (Poly a) where
zeroV = Poly LE True []
(rawPolyCoeffs LE -> a) ^+^ (rawPolyCoeffs LE -> b)
= Poly LE False (zipSumV a b)
negateV = fmap negateV
instance VectorSpace a => VectorSpace (Poly a) where
type Scalar (Poly a) = Scalar a
(*^) s = fmap (s *^)