Safe Haskell	None
Language	Haskell2010

Data.Polynomial

Contents

Formal polynomials with natural-number (ℕ) coefficients
Type-level formal polynomials

Synopsis

data Poly
- = U
- | S Poly
- | T Poly
data Poly₀
- = Z
- | NZ Poly
class Zero a where
- zero :: a
class Plus a where
- plus :: a -> a -> a
class One a where
- one :: a
class Times a where
- times :: a -> a -> a
evalPoly :: (Plus a, One a, Times a) => Poly -> a -> a
evalPoly₀ :: (Zero a, Plus a, One a, Times a) => Poly₀ -> a -> a
countSummands :: Poly₀ -> Int
polynomialOrder :: Poly -> Int
class SZero k where
- type TZero k :: k
- sZero :: Sing (TZero k)
class SPlus k where
- type (x :: k) + (y :: k) :: k
- (%+) :: forall (x :: k) (y :: k). Sing x -> Sing y -> Sing (x + y)
class SOne k where
- type TOne k :: k
- sOne :: Sing (TOne k)
class STimes k where
- type (x :: k) * (y :: k) :: k
- (%*) :: forall (x :: k) (y :: k). Sing x -> Sing y -> Sing (x * y)
class SId k where
- type TId k :: k
- sId :: Sing (TId k)
class SCompose k where
- type (x :: k) << (y :: k) :: k
- (%<<) :: forall (x :: k) (y :: k). Sing x -> Sing y -> Sing (x << y)
data SPoly (a :: Poly) where
- SingU :: SPoly 'U
- SingS :: forall (p :: Poly). SPoly p -> SPoly ('S p)
- SingT :: forall (p :: Poly). SPoly p -> SPoly ('T p)
data SPoly₀ (a :: Poly₀) where
- SingZ :: SPoly₀ 'Z
- SingNZ :: forall (p :: Poly). SPoly p -> SPoly₀ ('NZ p)
type family EvalPoly (x :: Poly) k (arg :: k) :: k where ...
sEvalPoly :: forall k (x :: Poly) (arg :: k). (SOne k, SPlus k, STimes k) => SPoly x -> Sing arg -> Sing (EvalPoly x k arg)
type family EvalPoly₀ (x :: Poly₀) k (arg :: k) :: k where ...
sEvalPoly₀ :: forall k (x :: Poly₀) (arg :: k). (SZero k, SOne k, SPlus k, STimes k) => SPoly₀ x -> Sing arg -> Sing (EvalPoly₀ x k arg)

Formal polynomials with natural-number (ℕ) coefficients

data Poly Source #

A nonzero formal polynomial with natural-number coefficient. If we write {p} for the meaning of p :: Poly as a polynomial, the following holds:

{U}(x) = 1
{S p}(x) = 1 + {p}(x)
{T p}(x) = x * {p}(x)

In other words:

U :: Poly represents a constant polynomial {U}(x) = 1
S p :: Poly represents 1 plus the polynomial {p}.
T p :: Poly represents {p} multiplied by the parameter of the polynomial.

Any nonzero polynomial with coefficients in ℕ can be represented using Poly. In fact, they are uniquely represented as a Poly value. For example, 1 + x^2 + x^3 is uniquely represented as S (T (T (S (T U)))).

{S (T (T (S (T U))))}(x)
  = 1 + {T (T (S (T U)))}(x)
  = 1 + x * {T (S (T U))}(x)
  = 1 + x * x * {S (T U)}(x)
  = 1 + x * x * (1 + {T U}(x))
  = 1 + x * x * (1 + x * {U}(x))
  = 1 + x * x * (1 + x * 1)
  = 1 + x^2 + x^3

Constructors

U
S Poly
T Poly

Instances

Instances details

Show Poly Source #

Instance details

Zero Poly₀ Source #
Instance details Defined in Data.Polynomial Methods zero :: Poly₀ Source #
Zero Natural Source #
Instance details Defined in Data.Polynomial Methods zero :: Natural Source #
Zero Int Source #
Instance details Defined in Data.Polynomial Methods zero :: Int Source #
(Bounded a, Ord a) => Zero (Max a) Source #
Instance details Defined in Data.Polynomial Methods zero :: Max a Source #

Plus Poly Source #
Instance details Defined in Data.Polynomial Methods plus :: Poly -> Poly -> Poly Source #
Plus Poly₀ Source #
Instance details Defined in Data.Polynomial Methods plus :: Poly₀ -> Poly₀ -> Poly₀ Source #
Plus Natural Source #
Instance details Defined in Data.Polynomial Methods plus :: Natural -> Natural -> Natural Source #
Plus Int Source #
Instance details Defined in Data.Polynomial Methods plus :: Int -> Int -> Int Source #
Ord a => Plus (Max a) Source #	max-plus algebra (assuming addition in `Num` preserves order)
Instance details Defined in Data.Polynomial Methods plus :: Max a -> Max a -> Max a Source #

One Poly Source #
Instance details Defined in Data.Polynomial Methods one :: Poly Source #
One Poly₀ Source #
Instance details Defined in Data.Polynomial Methods one :: Poly₀ Source #
One Natural Source #
Instance details Defined in Data.Polynomial Methods one :: Natural Source #
One Int Source #
Instance details Defined in Data.Polynomial Methods one :: Int Source #
(Ord a, Num a) => One (Max a) Source #	max-plus algebra (assuming addition in `Num` preserves order)
Instance details Defined in Data.Polynomial Methods one :: Max a Source #

Times Poly Source #
Instance details Defined in Data.Polynomial Methods times :: Poly -> Poly -> Poly Source #
Times Poly₀ Source #
Instance details Defined in Data.Polynomial Methods times :: Poly₀ -> Poly₀ -> Poly₀ Source #
Times Natural Source #
Instance details Defined in Data.Polynomial Methods times :: Natural -> Natural -> Natural Source #
Times Int Source #
Instance details Defined in Data.Polynomial Methods times :: Int -> Int -> Int Source #
(Ord a, Num a) => Times (Max a) Source #	max-plus algebra
Instance details Defined in Data.Polynomial Methods times :: Max a -> Max a -> Max a Source #

SingU :: SPoly 'U
SingS :: forall (p :: Poly). SPoly p -> SPoly ('S p)
SingT :: forall (p :: Poly). SPoly p -> SPoly ('T p)

Show (SPoly p) Source #
Instance details Defined in Data.Polynomial Methods showsPrec :: Int -> SPoly p -> ShowS # show :: SPoly p -> String # showList :: [SPoly p] -> ShowS #

SingZ :: SPoly₀ 'Z
SingNZ :: forall (p :: Poly). SPoly p -> SPoly₀ ('NZ p)

Show (SPoly₀ p) Source #
Instance details Defined in Data.Polynomial Methods showsPrec :: Int -> SPoly₀ p -> ShowS # show :: SPoly₀ p -> String # showList :: [SPoly₀ p] -> ShowS #

EvalPoly 'U k (_1 :: k) = TOne k
EvalPoly ('S p) k (arg :: k) = TOne k + EvalPoly p k arg
EvalPoly ('T p) k (arg :: k) = arg * EvalPoly p k arg

EvalPoly₀ 'Z k (_1 :: k) = TZero k
EvalPoly₀ ('NZ p) k (arg :: k) = EvalPoly p k arg

Formal polynomials with natural-number (ℕ) coefficients

Instances

Instances

Instances

Instances

Instances

Instances

Type-level formal polynomials

Instances

Instances

Instances

Instances

Instances

Instances

Instances

Instances