-- | Rising and falling factorials
--
-- See <https://en.wikipedia.org/wiki/Falling_and_rising_factorials>

{-# LANGUAGE BangPatterns, DataKinds, KindSignatures #-}
module Math.Algebra.Polynomial.Univariate.Pochhammer where

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

import Data.Array ( Array , (!) , listArray , assocs ) 
import Data.List

import Data.Typeable
import GHC.TypeLits
import Data.Proxy

import Math.Algebra.Polynomial.Pretty
import Math.Algebra.Polynomial.Misc

import qualified Math.Algebra.Polynomial.FreeModule as ZMod
import Math.Algebra.Polynomial.FreeModule ( FreeMod , ZMod , QMod )

import Math.Algebra.Polynomial.Monomial.Univariate ( U(..) )
import Math.Algebra.Polynomial.Univariate

--------------------------------------------------------------------------------
-- * Rising and Falling factorials

risingFactorial :: Int -> Univariate Integer "x"
risingFactorial :: Int -> Univariate Integer "x"
risingFactorial Int
n = RisingF -> Univariate Integer "x"
forall (var :: Symbol) c.
(KnownSymbol var, Typeable c, Eq c, Num c) =>
RisingF -> Univariate c var
expandRisingFactorial (Int -> RisingF
RF Int
n)

fallingFactorial :: Int -> Univariate Integer "x"
fallingFactorial :: Int -> Univariate Integer "x"
fallingFactorial Int
n = FallingF -> Univariate Integer "x"
forall (var :: Symbol) c.
(KnownSymbol var, Typeable c, Eq c, Num c) =>
FallingF -> Univariate c var
expandFallingFactorial (Int -> FallingF
FF Int
n)

--------------------------------------------------------------------------------
-- * Polynomials using rising or falling factorials as bases

-- | Univariate polynomials using /rising factorials/ as a basis function
newtype RisingPoly  coeff = RisingPoly  { RisingPoly coeff -> FreeMod coeff RisingF
fromRisingPoly  :: FreeMod coeff RisingF }  deriving (RisingPoly coeff -> RisingPoly coeff -> Bool
(RisingPoly coeff -> RisingPoly coeff -> Bool)
-> (RisingPoly coeff -> RisingPoly coeff -> Bool)
-> Eq (RisingPoly coeff)
forall coeff.
Eq coeff =>
RisingPoly coeff -> RisingPoly coeff -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: RisingPoly coeff -> RisingPoly coeff -> Bool
$c/= :: forall coeff.
Eq coeff =>
RisingPoly coeff -> RisingPoly coeff -> Bool
== :: RisingPoly coeff -> RisingPoly coeff -> Bool
$c== :: forall coeff.
Eq coeff =>
RisingPoly coeff -> RisingPoly coeff -> Bool
Eq,Int -> RisingPoly coeff -> ShowS
[RisingPoly coeff] -> ShowS
RisingPoly coeff -> String
(Int -> RisingPoly coeff -> ShowS)
-> (RisingPoly coeff -> String)
-> ([RisingPoly coeff] -> ShowS)
-> Show (RisingPoly coeff)
forall coeff. Show coeff => Int -> RisingPoly coeff -> ShowS
forall coeff. Show coeff => [RisingPoly coeff] -> ShowS
forall coeff. Show coeff => RisingPoly coeff -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [RisingPoly coeff] -> ShowS
$cshowList :: forall coeff. Show coeff => [RisingPoly coeff] -> ShowS
show :: RisingPoly coeff -> String
$cshow :: forall coeff. Show coeff => RisingPoly coeff -> String
showsPrec :: Int -> RisingPoly coeff -> ShowS
$cshowsPrec :: forall coeff. Show coeff => Int -> RisingPoly coeff -> ShowS
Show)

-- | Univariate polynomials using /falling factorials/ as a basis function
newtype FallingPoly coeff = FallingPoly { FallingPoly coeff -> FreeMod coeff FallingF
fromFallingPoly :: FreeMod coeff FallingF } deriving (FallingPoly coeff -> FallingPoly coeff -> Bool
(FallingPoly coeff -> FallingPoly coeff -> Bool)
-> (FallingPoly coeff -> FallingPoly coeff -> Bool)
-> Eq (FallingPoly coeff)
forall coeff.
Eq coeff =>
FallingPoly coeff -> FallingPoly coeff -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: FallingPoly coeff -> FallingPoly coeff -> Bool
$c/= :: forall coeff.
Eq coeff =>
FallingPoly coeff -> FallingPoly coeff -> Bool
== :: FallingPoly coeff -> FallingPoly coeff -> Bool
$c== :: forall coeff.
Eq coeff =>
FallingPoly coeff -> FallingPoly coeff -> Bool
Eq,Int -> FallingPoly coeff -> ShowS
[FallingPoly coeff] -> ShowS
FallingPoly coeff -> String
(Int -> FallingPoly coeff -> ShowS)
-> (FallingPoly coeff -> String)
-> ([FallingPoly coeff] -> ShowS)
-> Show (FallingPoly coeff)
forall coeff. Show coeff => Int -> FallingPoly coeff -> ShowS
forall coeff. Show coeff => [FallingPoly coeff] -> ShowS
forall coeff. Show coeff => FallingPoly coeff -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [FallingPoly coeff] -> ShowS
$cshowList :: forall coeff. Show coeff => [FallingPoly coeff] -> ShowS
show :: FallingPoly coeff -> String
$cshow :: forall coeff. Show coeff => FallingPoly coeff -> String
showsPrec :: Int -> FallingPoly coeff -> ShowS
$cshowsPrec :: forall coeff. Show coeff => Int -> FallingPoly coeff -> ShowS
Show)

expandRisingPoly :: (KnownSymbol var, Typeable c, Eq c, Num c) => FreeMod c RisingF -> Univariate c var
expandRisingPoly :: FreeMod c RisingF -> Univariate c var
expandRisingPoly = FreeMod c (U var) -> Univariate c var
forall coeff (var :: Symbol).
FreeMod coeff (U var) -> Univariate coeff var
Uni (FreeMod c (U var) -> Univariate c var)
-> (FreeMod c RisingF -> FreeMod c (U var))
-> FreeMod c RisingF
-> Univariate c var
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (RisingF -> FreeMod c (U var))
-> FreeMod c RisingF -> FreeMod c (U var)
forall b1 b2 c.
(Ord b1, Ord b2, Eq c, Num c) =>
(b1 -> FreeMod c b2) -> FreeMod c b1 -> FreeMod c b2
ZMod.flatMap (Univariate c var -> FreeMod c (U var)
forall c (v :: Symbol). Univariate c v -> FreeMod c (U v)
unUni (Univariate c var -> FreeMod c (U var))
-> (RisingF -> Univariate c var) -> RisingF -> FreeMod c (U var)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. RisingF -> Univariate c var
forall (var :: Symbol) c.
(KnownSymbol var, Typeable c, Eq c, Num c) =>
RisingF -> Univariate c var
expandRisingFactorial)

expandFallingPoly :: (KnownSymbol var, Typeable c, Eq c, Num c) => FreeMod c FallingF -> Univariate c var
expandFallingPoly :: FreeMod c FallingF -> Univariate c var
expandFallingPoly = FreeMod c (U var) -> Univariate c var
forall coeff (var :: Symbol).
FreeMod coeff (U var) -> Univariate coeff var
Uni (FreeMod c (U var) -> Univariate c var)
-> (FreeMod c FallingF -> FreeMod c (U var))
-> FreeMod c FallingF
-> Univariate c var
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (FallingF -> FreeMod c (U var))
-> FreeMod c FallingF -> FreeMod c (U var)
forall b1 b2 c.
(Ord b1, Ord b2, Eq c, Num c) =>
(b1 -> FreeMod c b2) -> FreeMod c b1 -> FreeMod c b2
ZMod.flatMap (Univariate c var -> FreeMod c (U var)
forall c (v :: Symbol). Univariate c v -> FreeMod c (U v)
unUni (Univariate c var -> FreeMod c (U var))
-> (FallingF -> Univariate c var) -> FallingF -> FreeMod c (U var)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FallingF -> Univariate c var
forall (var :: Symbol) c.
(KnownSymbol var, Typeable c, Eq c, Num c) =>
FallingF -> Univariate c var
expandFallingFactorial)

--------------------------------------------------------------------------------
-- * Rising and falling factorial types

-- | Rising factorial @x^(k) = x(x+1)(x+2)...(x+k-1)@
newtype RisingF = RF Int deriving (RisingF -> RisingF -> Bool
(RisingF -> RisingF -> Bool)
-> (RisingF -> RisingF -> Bool) -> Eq RisingF
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: RisingF -> RisingF -> Bool
$c/= :: RisingF -> RisingF -> Bool
== :: RisingF -> RisingF -> Bool
$c== :: RisingF -> RisingF -> Bool
Eq,Eq RisingF
Eq RisingF
-> (RisingF -> RisingF -> Ordering)
-> (RisingF -> RisingF -> Bool)
-> (RisingF -> RisingF -> Bool)
-> (RisingF -> RisingF -> Bool)
-> (RisingF -> RisingF -> Bool)
-> (RisingF -> RisingF -> RisingF)
-> (RisingF -> RisingF -> RisingF)
-> Ord RisingF
RisingF -> RisingF -> Bool
RisingF -> RisingF -> Ordering
RisingF -> RisingF -> RisingF
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 :: RisingF -> RisingF -> RisingF
$cmin :: RisingF -> RisingF -> RisingF
max :: RisingF -> RisingF -> RisingF
$cmax :: RisingF -> RisingF -> RisingF
>= :: RisingF -> RisingF -> Bool
$c>= :: RisingF -> RisingF -> Bool
> :: RisingF -> RisingF -> Bool
$c> :: RisingF -> RisingF -> Bool
<= :: RisingF -> RisingF -> Bool
$c<= :: RisingF -> RisingF -> Bool
< :: RisingF -> RisingF -> Bool
$c< :: RisingF -> RisingF -> Bool
compare :: RisingF -> RisingF -> Ordering
$ccompare :: RisingF -> RisingF -> Ordering
$cp1Ord :: Eq RisingF
Ord,Int -> RisingF -> ShowS
[RisingF] -> ShowS
RisingF -> String
(Int -> RisingF -> ShowS)
-> (RisingF -> String) -> ([RisingF] -> ShowS) -> Show RisingF
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [RisingF] -> ShowS
$cshowList :: [RisingF] -> ShowS
show :: RisingF -> String
$cshow :: RisingF -> String
showsPrec :: Int -> RisingF -> ShowS
$cshowsPrec :: Int -> RisingF -> ShowS
Show)

-- | Falling factorial @x_(k) = x(x-1)(x-2)...(x-k+1)@
newtype FallingF = FF Int deriving (FallingF -> FallingF -> Bool
(FallingF -> FallingF -> Bool)
-> (FallingF -> FallingF -> Bool) -> Eq FallingF
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: FallingF -> FallingF -> Bool
$c/= :: FallingF -> FallingF -> Bool
== :: FallingF -> FallingF -> Bool
$c== :: FallingF -> FallingF -> Bool
Eq,Eq FallingF
Eq FallingF
-> (FallingF -> FallingF -> Ordering)
-> (FallingF -> FallingF -> Bool)
-> (FallingF -> FallingF -> Bool)
-> (FallingF -> FallingF -> Bool)
-> (FallingF -> FallingF -> Bool)
-> (FallingF -> FallingF -> FallingF)
-> (FallingF -> FallingF -> FallingF)
-> Ord FallingF
FallingF -> FallingF -> Bool
FallingF -> FallingF -> Ordering
FallingF -> FallingF -> FallingF
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 :: FallingF -> FallingF -> FallingF
$cmin :: FallingF -> FallingF -> FallingF
max :: FallingF -> FallingF -> FallingF
$cmax :: FallingF -> FallingF -> FallingF
>= :: FallingF -> FallingF -> Bool
$c>= :: FallingF -> FallingF -> Bool
> :: FallingF -> FallingF -> Bool
$c> :: FallingF -> FallingF -> Bool
<= :: FallingF -> FallingF -> Bool
$c<= :: FallingF -> FallingF -> Bool
< :: FallingF -> FallingF -> Bool
$c< :: FallingF -> FallingF -> Bool
compare :: FallingF -> FallingF -> Ordering
$ccompare :: FallingF -> FallingF -> Ordering
$cp1Ord :: Eq FallingF
Ord,Int -> FallingF -> ShowS
[FallingF] -> ShowS
FallingF -> String
(Int -> FallingF -> ShowS)
-> (FallingF -> String) -> ([FallingF] -> ShowS) -> Show FallingF
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [FallingF] -> ShowS
$cshowList :: [FallingF] -> ShowS
show :: FallingF -> String
$cshow :: FallingF -> String
showsPrec :: Int -> FallingF -> ShowS
$cshowsPrec :: Int -> FallingF -> ShowS
Show)

instance Pretty RisingF where
  pretty :: RisingF -> String
pretty (RF Int
k) = case Int
k of
    Int
0 -> String
"1"
    Int
1 -> String
"x"
    Int
_ -> String
"x^(" String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
k String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
")"

instance Pretty FallingF where
  pretty :: FallingF -> String
pretty (FF Int
k) = case Int
k of
    Int
0 -> String
"1"
    Int
1 -> String
"x"
    Int
_ -> String
"x_(" String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
k String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
")"

expandRisingFactorial :: (KnownSymbol var, Typeable c, Eq c, Num c) => RisingF -> Univariate c var
expandRisingFactorial :: RisingF -> Univariate c var
expandRisingFactorial = FreeMod c (U var) -> Univariate c var
forall coeff (var :: Symbol).
FreeMod coeff (U var) -> Univariate coeff var
Uni (FreeMod c (U var) -> Univariate c var)
-> (RisingF -> FreeMod c (U var)) -> RisingF -> Univariate c var
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ZMod (U var) -> FreeMod c (U var)
forall c b.
(Num c, Typeable c, Eq c, Num c, Ord b, Typeable b) =>
ZMod b -> FreeMod c b
ZMod.fromZMod (ZMod (U var) -> FreeMod c (U var))
-> (RisingF -> ZMod (U var)) -> RisingF -> FreeMod c (U var)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Univariate Integer var -> ZMod (U var)
forall c (v :: Symbol). Univariate c v -> FreeMod c (U v)
unUni (Univariate Integer var -> ZMod (U var))
-> (RisingF -> Univariate Integer var) -> RisingF -> ZMod (U var)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. RisingF -> Univariate Integer var
forall (var :: Symbol). RisingF -> Univariate Integer var
expandRisingFactorialZ

expandFallingFactorial ::(KnownSymbol var, Typeable c, Eq c, Num c) => FallingF -> Univariate c var
expandFallingFactorial :: FallingF -> Univariate c var
expandFallingFactorial = FreeMod c (U var) -> Univariate c var
forall coeff (var :: Symbol).
FreeMod coeff (U var) -> Univariate coeff var
Uni (FreeMod c (U var) -> Univariate c var)
-> (FallingF -> FreeMod c (U var)) -> FallingF -> Univariate c var
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ZMod (U var) -> FreeMod c (U var)
forall c b.
(Num c, Typeable c, Eq c, Num c, Ord b, Typeable b) =>
ZMod b -> FreeMod c b
ZMod.fromZMod (ZMod (U var) -> FreeMod c (U var))
-> (FallingF -> ZMod (U var)) -> FallingF -> FreeMod c (U var)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Univariate Integer var -> ZMod (U var)
forall c (v :: Symbol). Univariate c v -> FreeMod c (U v)
unUni (Univariate Integer var -> ZMod (U var))
-> (FallingF -> Univariate Integer var) -> FallingF -> ZMod (U var)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FallingF -> Univariate Integer var
forall (var :: Symbol). FallingF -> Univariate Integer var
expandFallingFactorialZ

expandRisingFactorialZ :: RisingF -> Univariate Integer var
expandRisingFactorialZ :: RisingF -> Univariate Integer var
expandRisingFactorialZ (RF Int
k) = FreeMod Integer (U var) -> Univariate Integer var
forall coeff (var :: Symbol).
FreeMod coeff (U var) -> Univariate coeff var
Uni (FreeMod Integer (U var) -> Univariate Integer var)
-> FreeMod Integer (U var) -> Univariate Integer var
forall a b. (a -> b) -> a -> b
$ [(U var, Integer)] -> FreeMod Integer (U var)
forall c b. (Eq c, Num c, Ord b) => [(b, c)] -> FreeMod c b
ZMod.fromList
  [ (Int -> U var
forall (var :: Symbol). Int -> U var
U Int
p, Integer -> Integer
forall a. Num a => a -> a
abs Integer
c) | (Int
p,Integer
c) <- Array Int Integer -> [(Int, Integer)]
forall i e. Ix i => Array i e -> [(i, e)]
assocs (Int -> Array Int Integer
forall a. Integral a => a -> Array Int Integer
signedStirling1stArray Int
k) ]

expandFallingFactorialZ :: FallingF -> Univariate Integer var
expandFallingFactorialZ :: FallingF -> Univariate Integer var
expandFallingFactorialZ (FF Int
k) = FreeMod Integer (U var) -> Univariate Integer var
forall coeff (var :: Symbol).
FreeMod coeff (U var) -> Univariate coeff var
Uni (FreeMod Integer (U var) -> Univariate Integer var)
-> FreeMod Integer (U var) -> Univariate Integer var
forall a b. (a -> b) -> a -> b
$ [(U var, Integer)] -> FreeMod Integer (U var)
forall c b. (Eq c, Num c, Ord b) => [(b, c)] -> FreeMod c b
ZMod.fromList
  [ (Int -> U var
forall (var :: Symbol). Int -> U var
U Int
p,     Integer
c) | (Int
p,Integer
c) <- Array Int Integer -> [(Int, Integer)]
forall i e. Ix i => Array i e -> [(i, e)]
assocs (Int -> Array Int Integer
forall a. Integral a => a -> Array Int Integer
signedStirling1stArray Int
k) ]

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