{-
	Copyright (C) 2011 Dr. Alistair Ward

	This program is free software: you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation, either version 3 of the License, or
	(at your option) any later version.

	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with this program.  If not, see <http://www.gnu.org/licenses/>.
-}
{- |
 [@AUTHOR@]	Dr. Alistair Ward

 [@DESCRIPTION@]

	* Describes a /monic polynomial; <https://en.wikipedia.org/wiki/Monic_polynomial#Classifications>;
	ie. in which the /coefficient/ of the /leading term/ is one.
-}

module Factory.Data.MonicPolynomial(
-- * Types
-- ** Data-types
	MonicPolynomial(getPolynomial),	-- Hide the data-constructor.
-- * Functions
-- ** Constructor
	mkMonicPolynomial
) where

import qualified	Control.Arrow
import qualified	Factory.Data.Monomial		as Data.Monomial
import			Factory.Data.Polynomial((*=))
import qualified	Factory.Data.Polynomial		as Data.Polynomial
import qualified	Factory.Data.QuotientRing	as Data.QuotientRing
import			Factory.Data.Ring((=*=), (=+=), (=-=))
import qualified	Factory.Data.Ring		as Data.Ring
import qualified	ToolShed.Data.Pair

-- | A type of 'Data.Polynomial.Polynomial', in which the /leading term/ is required to have a /coefficient/ of one.
newtype MonicPolynomial c e	= MkMonicPolynomial {
	MonicPolynomial c e -> Polynomial c e
getPolynomial	:: Data.Polynomial.Polynomial c e
} deriving (MonicPolynomial c e -> MonicPolynomial c e -> Bool
(MonicPolynomial c e -> MonicPolynomial c e -> Bool)
-> (MonicPolynomial c e -> MonicPolynomial c e -> Bool)
-> Eq (MonicPolynomial c e)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall c e.
(Eq c, Eq e) =>
MonicPolynomial c e -> MonicPolynomial c e -> Bool
/= :: MonicPolynomial c e -> MonicPolynomial c e -> Bool
$c/= :: forall c e.
(Eq c, Eq e) =>
MonicPolynomial c e -> MonicPolynomial c e -> Bool
== :: MonicPolynomial c e -> MonicPolynomial c e -> Bool
$c== :: forall c e.
(Eq c, Eq e) =>
MonicPolynomial c e -> MonicPolynomial c e -> Bool
Eq, Int -> MonicPolynomial c e -> ShowS
[MonicPolynomial c e] -> ShowS
MonicPolynomial c e -> String
(Int -> MonicPolynomial c e -> ShowS)
-> (MonicPolynomial c e -> String)
-> ([MonicPolynomial c e] -> ShowS)
-> Show (MonicPolynomial c e)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall c e. (Show c, Show e) => Int -> MonicPolynomial c e -> ShowS
forall c e. (Show c, Show e) => [MonicPolynomial c e] -> ShowS
forall c e. (Show c, Show e) => MonicPolynomial c e -> String
showList :: [MonicPolynomial c e] -> ShowS
$cshowList :: forall c e. (Show c, Show e) => [MonicPolynomial c e] -> ShowS
show :: MonicPolynomial c e -> String
$cshow :: forall c e. (Show c, Show e) => MonicPolynomial c e -> String
showsPrec :: Int -> MonicPolynomial c e -> ShowS
$cshowsPrec :: forall c e. (Show c, Show e) => Int -> MonicPolynomial c e -> ShowS
Show)

-- | Smart constructor. Constructs an arbitrary /monic polynomial/.
mkMonicPolynomial :: (
	Eq	c,
	Num	c,
	Show	c,
	Show	e
 ) => Data.Polynomial.Polynomial c e -> MonicPolynomial c e
mkMonicPolynomial :: Polynomial c e -> MonicPolynomial c e
mkMonicPolynomial Polynomial c e
polynomial
	| Bool -> Bool
not (Bool -> Bool) -> Bool -> Bool
forall a b. (a -> b) -> a -> b
$ Polynomial c e -> Bool
forall c e. (Eq c, Num c) => Polynomial c e -> Bool
Data.Polynomial.isMonic Polynomial c e
polynomial	= String -> MonicPolynomial c e
forall a. HasCallStack => String -> a
error (String -> MonicPolynomial c e) -> String -> MonicPolynomial c e
forall a b. (a -> b) -> a -> b
$ String
"Factory.Data.MonicPolynomial.mkMonicPolynomial:\tnot monic; " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Polynomial c e -> String
forall a. Show a => a -> String
show Polynomial c e
polynomial
	| Bool
otherwise					= Polynomial c e -> MonicPolynomial c e
forall c e. Polynomial c e -> MonicPolynomial c e
MkMonicPolynomial Polynomial c e
polynomial

{-
	* This instance-declaration merely delegates to the 'Data.Polynomial.Polynomial' payload.

	* CAVEAT: it's not strictly an instance of this class, since the result of some methods isn't /monic/.
-}
instance (
	Eq	c,
	Num	c,
	Num	e,
	Ord	e,
	Show	c,
	Show	e
 ) => Data.Ring.Ring (MonicPolynomial c e)	where
	MkMonicPolynomial Polynomial c e
l =*= :: MonicPolynomial c e -> MonicPolynomial c e -> MonicPolynomial c e
=*= MkMonicPolynomial Polynomial c e
r	= Polynomial c e -> MonicPolynomial c e
forall c e. Polynomial c e -> MonicPolynomial c e
MkMonicPolynomial (Polynomial c e -> MonicPolynomial c e)
-> Polynomial c e -> MonicPolynomial c e
forall a b. (a -> b) -> a -> b
$ Polynomial c e
l Polynomial c e -> Polynomial c e -> Polynomial c e
forall r. Ring r => r -> r -> r
=*= Polynomial c e
r
	MkMonicPolynomial Polynomial c e
l =+= :: MonicPolynomial c e -> MonicPolynomial c e -> MonicPolynomial c e
=+= MkMonicPolynomial Polynomial c e
r	= Polynomial c e -> MonicPolynomial c e
forall c e.
(Eq c, Num c, Show c, Show e) =>
Polynomial c e -> MonicPolynomial c e
mkMonicPolynomial (Polynomial c e -> MonicPolynomial c e)
-> Polynomial c e -> MonicPolynomial c e
forall a b. (a -> b) -> a -> b
$ Polynomial c e
l Polynomial c e -> Polynomial c e -> Polynomial c e
forall r. Ring r => r -> r -> r
=+= Polynomial c e
r	-- CAVEAT: potentially non-monic.
--	additiveInverse (MkMonicPolynomial p)		= MkMonicPolynomial $ Data.Ring.additiveInverse p	-- CAVEAT: not monic !
	additiveInverse :: MonicPolynomial c e -> MonicPolynomial c e
additiveInverse MonicPolynomial c e
_				= String -> MonicPolynomial c e
forall a. HasCallStack => String -> a
error String
"Factory.Data.MonicPolynomial.additiveInverse:\tresult isn't monic"
	multiplicativeIdentity :: MonicPolynomial c e
multiplicativeIdentity				= Polynomial c e -> MonicPolynomial c e
forall c e. Polynomial c e -> MonicPolynomial c e
MkMonicPolynomial Polynomial c e
forall r. Ring r => r
Data.Ring.multiplicativeIdentity
	additiveIdentity :: MonicPolynomial c e
additiveIdentity				= Polynomial c e -> MonicPolynomial c e
forall c e. Polynomial c e -> MonicPolynomial c e
MkMonicPolynomial Polynomial c e
forall r. Ring r => r
Data.Ring.additiveIdentity	-- CAVEAT: not monic !

-- Since the /leading term/ of the /denominator/ is one, the /coefficient/ isn't required to implement 'Fractional'.
instance (
	Eq	c,
	Num	c,
	Num	e,
	Ord	e,
	Show	c,
	Show	e
 ) => Data.QuotientRing.QuotientRing (MonicPolynomial c e)	where
	MkMonicPolynomial Polynomial c e
polynomialN quotRem' :: MonicPolynomial c e
-> MonicPolynomial c e
-> (MonicPolynomial c e, MonicPolynomial c e)
`quotRem'` MkMonicPolynomial Polynomial c e
polynomialD	= (Polynomial c e -> MonicPolynomial c e)
-> (Polynomial c e, Polynomial c e)
-> (MonicPolynomial c e, MonicPolynomial c e)
forall a b. (a -> b) -> (a, a) -> (b, b)
ToolShed.Data.Pair.mirror Polynomial c e -> MonicPolynomial c e
forall c e. Polynomial c e -> MonicPolynomial c e
MkMonicPolynomial ((Polynomial c e, Polynomial c e)
 -> (MonicPolynomial c e, MonicPolynomial c e))
-> (Polynomial c e, Polynomial c e)
-> (MonicPolynomial c e, MonicPolynomial c e)
forall a b. (a -> b) -> a -> b
$ Polynomial c e -> (Polynomial c e, Polynomial c e)
longDivide Polynomial c e
polynomialN	where
--		longDivide :: (Num c, Num e, Ord e) => Polynomial c e -> (Polynomial c e, Polynomial c e)
		longDivide :: Polynomial c e -> (Polynomial c e, Polynomial c e)
longDivide Polynomial c e
numerator
			| Polynomial c e -> Bool
forall c e. Polynomial c e -> Bool
Data.Polynomial.isZero Polynomial c e
numerator Bool -> Bool -> Bool
|| Monomial c e -> e
forall c e. Monomial c e -> e
Data.Monomial.getExponent Monomial c e
quotient e -> e -> Bool
forall a. Ord a => a -> a -> Bool
< e
0	= (Polynomial c e
forall c e. Polynomial c e
Data.Polynomial.zero, Polynomial c e
numerator)
			| Bool
otherwise									= (Polynomial c e -> Polynomial c e)
-> (Polynomial c e, Polynomial c e)
-> (Polynomial c e, Polynomial c e)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
Control.Arrow.first ((MonomialList c e -> MonomialList c e)
-> Polynomial c e -> Polynomial c e
forall c1 e1 c2 e2.
(MonomialList c1 e1 -> MonomialList c2 e2)
-> Polynomial c1 e1 -> Polynomial c2 e2
Data.Polynomial.lift (Monomial c e
quotient Monomial c e -> MonomialList c e -> MonomialList c e
forall a. a -> [a] -> [a]
:)) ((Polynomial c e, Polynomial c e)
 -> (Polynomial c e, Polynomial c e))
-> (Polynomial c e, Polynomial c e)
-> (Polynomial c e, Polynomial c e)
forall a b. (a -> b) -> a -> b
$ Polynomial c e -> (Polynomial c e, Polynomial c e)
longDivide (Polynomial c e
numerator Polynomial c e -> Polynomial c e -> Polynomial c e
forall r. Ring r => r -> r -> r
=-= Polynomial c e
polynomialD Polynomial c e -> Monomial c e -> Polynomial c e
forall c e.
(Eq c, Num c, Num e) =>
Polynomial c e -> Monomial c e -> Polynomial c e
*= Monomial c e
quotient)
			where
--				quotient :: Num e => Data.Monomial.Monomial c e
				quotient :: Monomial c e
quotient	= Polynomial c e -> Monomial c e
forall c e. Polynomial c e -> Monomial c e
Data.Polynomial.getLeadingTerm Polynomial c e
numerator Monomial c e -> e -> Monomial c e
forall e c. Num e => Monomial c e -> e -> Monomial c e
`Data.Monomial.shiftExponent` e -> e
forall a. Num a => a -> a
negate (Monomial c e -> e
forall c e. Monomial c e -> e
Data.Monomial.getExponent (Monomial c e -> e) -> Monomial c e -> e
forall a b. (a -> b) -> a -> b
$ Polynomial c e -> Monomial c e
forall c e. Polynomial c e -> Monomial c e
Data.Polynomial.getLeadingTerm Polynomial c e
polynomialD)