{-# LANGUAGE 
      FlexibleContexts, TypeFamilies, TypeSynonymInstances, FlexibleInstances, 
      GeneralizedNewtypeDeriving, ConstraintKinds
  #-}

module Math.Algebra.Polynomial.Class where

--------------------------------------------------------------------------------

import Data.List ( foldl' , foldl1' , maximum , null )
import Data.Typeable
import Data.Proxy

import Math.Algebra.Polynomial.Misc
import Math.Algebra.Polynomial.Pretty
import Math.Algebra.Polynomial.FreeModule ( FreeModule(..) ) 

--------------------------------------------------------------------------------
-- * Indices

-- | The index of a variable. This will be used as the variable type 
-- when the set of variables is a continguous set like @{x_1, x_2, ... , x_N}@ 
newtype Index 
  = Index Int 
  deriving (Index -> Index -> Bool
(Index -> Index -> Bool) -> (Index -> Index -> Bool) -> Eq Index
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Index -> Index -> Bool
$c/= :: Index -> Index -> Bool
== :: Index -> Index -> Bool
$c== :: Index -> Index -> Bool
Eq,Eq Index
Eq Index
-> (Index -> Index -> Ordering)
-> (Index -> Index -> Bool)
-> (Index -> Index -> Bool)
-> (Index -> Index -> Bool)
-> (Index -> Index -> Bool)
-> (Index -> Index -> Index)
-> (Index -> Index -> Index)
-> Ord Index
Index -> Index -> Bool
Index -> Index -> Ordering
Index -> Index -> Index
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 :: Index -> Index -> Index
$cmin :: Index -> Index -> Index
max :: Index -> Index -> Index
$cmax :: Index -> Index -> Index
>= :: Index -> Index -> Bool
$c>= :: Index -> Index -> Bool
> :: Index -> Index -> Bool
$c> :: Index -> Index -> Bool
<= :: Index -> Index -> Bool
$c<= :: Index -> Index -> Bool
< :: Index -> Index -> Bool
$c< :: Index -> Index -> Bool
compare :: Index -> Index -> Ordering
$ccompare :: Index -> Index -> Ordering
$cp1Ord :: Eq Index
Ord,Int -> Index -> ShowS
[Index] -> ShowS
Index -> String
(Int -> Index -> ShowS)
-> (Index -> String) -> ([Index] -> ShowS) -> Show Index
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Index] -> ShowS
$cshowList :: [Index] -> ShowS
show :: Index -> String
$cshow :: Index -> String
showsPrec :: Int -> Index -> ShowS
$cshowsPrec :: Int -> Index -> ShowS
Show,Int -> Index
Index -> Int
Index -> [Index]
Index -> Index
Index -> Index -> [Index]
Index -> Index -> Index -> [Index]
(Index -> Index)
-> (Index -> Index)
-> (Int -> Index)
-> (Index -> Int)
-> (Index -> [Index])
-> (Index -> Index -> [Index])
-> (Index -> Index -> [Index])
-> (Index -> Index -> Index -> [Index])
-> Enum Index
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 :: Index -> Index -> Index -> [Index]
$cenumFromThenTo :: Index -> Index -> Index -> [Index]
enumFromTo :: Index -> Index -> [Index]
$cenumFromTo :: Index -> Index -> [Index]
enumFromThen :: Index -> Index -> [Index]
$cenumFromThen :: Index -> Index -> [Index]
enumFrom :: Index -> [Index]
$cenumFrom :: Index -> [Index]
fromEnum :: Index -> Int
$cfromEnum :: Index -> Int
toEnum :: Int -> Index
$ctoEnum :: Int -> Index
pred :: Index -> Index
$cpred :: Index -> Index
succ :: Index -> Index
$csucc :: Index -> Index
Enum)

fromIndex :: Index -> Int
fromIndex :: Index -> Int
fromIndex (Index Int
j) = Int
j

instance Pretty Index where
  pretty :: Index -> String
pretty (Index Int
j) = String
"x_" String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
j

--------------------------------------------------------------------------------
-- * Rings

-- | The class of coefficient rings. 
--
-- Since base rings like integers or rational behave differently than say
-- another polynomial ring as a coefficient ring, we have to be explicit
-- about some things (mainly for pretty-printing purposes
--
-- TODO: clean this up!
class (Eq c, Ord c, Num c, IsSigned c, Show c, Pretty c, Typeable c) => Ring c where
  isZeroR   :: c -> Bool
  signumR   :: c -> Maybe Sign
  absR      :: c -> c
  isSignedR :: Proxy c -> Bool
  isAtomicR :: Proxy c -> Bool

  isZeroR   = (c -> c -> Bool
forall a. Eq a => a -> a -> Bool
==c
0)
  signumR   = c -> Maybe Sign
forall a. IsSigned a => a -> Maybe Sign
signOf
  absR      = c -> c
forall a. Num a => a -> a
abs
  isSignedR = Bool -> Proxy c -> Bool
forall a b. a -> b -> a
const Bool
True
  isAtomicR = Bool -> Proxy c -> Bool
forall a b. a -> b -> a
const Bool
True

instance Ring Int
instance Ring Integer
instance Ring Rational

-- | The class of coefficient fields (this is just a constraint synonym for now)
type Field c = (Ring c, Fractional c)

--------------------------------------------------------------------------------

-- | The class of types whose inhabitants can serve as variables
-- (this is just a constraint synonym for now)
type Variable v = (Ord v, Show v, Pretty v, Typeable v)

--------------------------------------------------------------------------------
-- * Monomials

-- | The class of (multivariate) monomials
-- 
-- The @Maybe@-s are there to allow truncated and exterior polynomial rings
class (Pretty m) => Monomial m where
  -- | the type of variables
  type VarM m :: *                          
  
  -- checking the invariant
  normalizeM  :: m -> m                         -- ^ enforce the invariant 
  isNormalM   :: m -> Bool                      -- ^ check the invariant
  -- construction and deconstruction
  fromListM   :: [(VarM m,Int)] -> m            -- ^ construction from @(variable,exponent)@ pairs
  toListM     :: m -> [(VarM m,Int)]            -- ^ extracting @(variable,exponent)@ pairs
  -- simple monomials
  emptyM      :: m                              -- ^ the empty monomial (corresponding to the polynomial 1)
  isEmptyM    :: m -> Bool                      -- ^ checks whether it is empty
  variableM   :: VarM m        -> m             -- ^ a single variable
  singletonM  :: VarM m -> Int -> m             -- ^ a single variable raised to a power
  -- algebra
  mulM        :: m -> m -> m                    -- ^ multiplication of monomials
  productM    :: [m] -> m                       -- ^ product of several monomials
  powM        :: m -> Int -> m                  -- ^ raising to a power
  divM        :: m -> m -> Maybe m              -- ^ division of monomials
  -- calculus
  diffM       :: Num c => VarM m -> Int -> m -> Maybe (m,c)       -- ^ differentiation
  -- degrees
  maxDegM     :: m -> Int                       -- ^ maximum degree
  totalDegM   :: m -> Int                       -- ^ total degree
  -- substitution and evaluation
  evalM       :: Num c => (VarM m -> c) -> m -> c                 -- ^ ring substitution (evaluation)
  varSubsM    :: (VarM m -> VarM m) -> m -> m                     -- ^ simple variable substitution
  termSubsM   :: Num c => (VarM m -> Maybe c) -> (m,c) -> (m,c)   -- ^ term substitution

{-
  -- some (inefficient) default implementations
  normalizeM     = id
  isNormalM      = const True
  productM       = foldl' mulM emptyM
  mulM a b       = productM [a,b]
  emptyM         = fromListM []
  variableM  v   = fromListM [(v,1)]
  singletonM v e = fromListM [(v,e)]
  maxDegM        = maximum      . map snd . toListM
  totalDegM      = foldl' (+) 0 . map snd . toListM
  isEmptyM       = null . toListM
-}

proxyVarM :: Monomial m => m -> Proxy (VarM m)
proxyVarM :: m -> Proxy (VarM m)
proxyVarM m
_ = Proxy (VarM m)
forall k (t :: k). Proxy t
Proxy

--------------------------------------------------------------------------------
-- * Polynomial rings

-- | The class of almost polynomial rings
class (Pretty p, Ring (CoeffP p), FreeModule p, CoeffP p ~ CoeffF p, MonomP p ~ BaseF p) => AlmostPolynomial p where

  -- | Type of coefficients
  type CoeffP p :: *
  -- | Type of monomials
  type MonomP p :: *
  -- | Type of variables
  type VarP   p :: *

  -- conversion
  fromListP     :: [(MonomP p, CoeffP p)] -> p       -- ^ construction from @(variable,exponent)@ pairs
  toListP       :: p -> [(MonomP p, CoeffP p)]       -- ^ extracting @(variable,exponent)@ pairs

  -- zero, one
  zeroP         :: p
  isZeroP       :: p -> Bool
  oneP          :: p

  -- construction
  variableP     :: VarP p        -> p                -- ^ a single variable
  singletonP    :: VarP p -> Int -> p                -- ^ a single variable raised to a power
  monomP        :: MonomP p -> p
  monomP'       :: MonomP p -> CoeffP p -> p
  scalarP       :: CoeffP p -> p

  -- algebra
  addP          :: p -> p -> p
  subP          :: p -> p -> p
  negP          :: p -> p 
  sumP          :: [p] -> p

  mulP          :: p -> p -> p
  productP      :: [p] -> p

  coeffOfP      :: MonomP p -> p -> CoeffP p
  mulByMonomP   :: MonomP p -> p -> p
  scaleP        :: CoeffP p -> p -> p 

  -- default implementations
  sumP     [p]
ps = case [p]
ps of { [] -> p
forall p. AlmostPolynomial p => p
zeroP ; [p]
_ -> (p -> p -> p) -> [p] -> p
forall a. (a -> a -> a) -> [a] -> a
foldl1' p -> p -> p
forall p. AlmostPolynomial p => p -> p -> p
addP [p]
ps }
  productP [p]
ps = case [p]
ps of { [] -> p
forall p. AlmostPolynomial p => p
oneP  ; [p]
_ -> (p -> p -> p) -> [p] -> p
forall a. (a -> a -> a) -> [a] -> a
foldl1' p -> p -> p
forall p. AlmostPolynomial p => p -> p -> p
mulP [p]
ps }

--------------------------------------------------------------------------------

-- | The class of polynomial rings
class (AlmostPolynomial p, Num p, Monomial (MonomP p), VarM (MonomP p) ~ VarP p) => Polynomial p where

  evalP         :: Num d => (CoeffP p -> d) -> (VarP p -> d) -> p -> d
  varSubsP      :: (VarP p -> VarP p) -> p -> p
  coeffSubsP    :: (VarP p -> Maybe (CoeffP p)) -> p -> p
  subsP         :: (VarP p -> p) -> p -> p

--------------------------------------------------------------------------------

proxyCoeffP :: AlmostPolynomial p => p -> Proxy (CoeffP p)
proxyCoeffP :: p -> Proxy (CoeffP p)
proxyCoeffP p
_ = Proxy (CoeffP p)
forall k (t :: k). Proxy t
Proxy

proxyMonomP :: AlmostPolynomial p => p -> Proxy (MonomP p)
proxyMonomP :: p -> Proxy (MonomP p)
proxyMonomP p
_ = Proxy (MonomP p)
forall k (t :: k). Proxy t
Proxy

proxyVarP :: AlmostPolynomial p => p -> Proxy (VarP p)
proxyVarP :: p -> Proxy (VarP p)
proxyVarP p
_ = Proxy (VarP p)
forall k (t :: k). Proxy t
Proxy

--------------------------------------------------------------------------------