Copyright | Anders Claesson 2015 |
---|---|
Maintainer | Anders Claesson <anders.claesson@gmail.com> |
Safe Haskell | None |
Language | Haskell98 |
License : BSD-3
Truncated power series with rational coefficients.
When writing this module I benefited from ideas and inspiration from the following sources:
- J. Merrill "Truncated Power Series for Julia", https://github.com/jwmerrill/PowerSeries.jl.
- M. D. McIlroy "Power serious: power series in ten one-liners", http://www1.cs.dartmouth.edu/~doug/powser.html.
- D. Piponi (sigfpe) "A Small Combinatorial Library", http://blog.sigfpe.com/2007/11/small-combinatorial-library.html.
- module HOPS.GF.Rat
- newtype Series n = Series (Vector Rat)
- polynomial :: KnownNat n => Proxy n -> [Rat] -> Series n
- series :: KnownNat n => Proxy n -> [Rat] -> Series n
- xpow :: KnownNat n => Int -> Series n
- nil :: KnownNat n => Series n
- infty :: KnownNat n => Series n
- precision :: Series n -> Int
- coeffVector :: Series n -> Vector Rat
- coeffList :: Series n -> [Rat]
- constant :: Series n -> Rat
- leadingCoeff :: Series n -> Rat
- rationalPrefix :: Series n -> [Rational]
- integerPrefix :: Series n -> [Integer]
- intPrefix :: Series n -> [Int]
- eval :: Series n -> Rat -> Rat
- (.*) :: Series n -> Series n -> Series n
- (./) :: Series n -> Series n -> Series n
- (!^!) :: Rat -> Rat -> Rat
- (^!) :: KnownNat n => Series n -> Rat -> Series n
- (?) :: KnownNat n => Series n -> Series n -> Series n
- o :: Series n -> Series n -> Series n
- blackDiamond :: Series n -> Series n -> Series n
- derivative :: Series n -> Series n
- integral :: Series n -> Series n
- revert :: Series n -> Series n
- sec :: KnownNat n => Series n -> Series n
- fac :: KnownNat n => Series n -> Series n
- rseq :: Series n -> Series n
- rseq' :: Series n -> Series n
Documentation
module HOPS.GF.Rat
A truncated power series is represented as a (dense) vector of coefficients. The precision (maximum number of coefficients) is statically checked. For instance, adding two series of different precision would result in a type error.
Constructions
polynomial :: KnownNat n => Proxy n -> [Rat] -> Series n Source #
Create a polynomial with the given list of coefficients. E.g.
>>>
(polynomial (Proxy :: Proxy 4) [1,1])^2
series (Proxy :: Proxy 4) [Val (1 % 1),Val (2 % 1),Val (1 % 1),Val (0 % 1)]
series :: KnownNat n => Proxy n -> [Rat] -> Series n Source #
Create a power series with the given list of initial coefficients. E.g.
>>>
(series (Proxy :: Proxy 4) [1,1])^2
series (Proxy :: Proxy 4) [Val (1 % 1),Val (2 % 1),Indet,Indet]
Accessors
coeffVector :: Series n -> Vector Rat Source #
The underlying vector of coefficients. E.g.
>>>
coeffVector $ polynomial (Proxy :: Proxy 3) [1,2]
fromList [Val (1 % 1),Val (2 % 1),Val (0 % 1)]
coeffList :: Series n -> [Rat] Source #
The list of coefficients of the given series. E.g.
>>>
coeffList $ series (Proxy :: Proxy 3) [9]
[Val (9 % 1),Indet,Indet]
leadingCoeff :: Series n -> Rat Source #
The first nonzero coefficient when read from smaller to larger powers of x. If no such coefficient exists then return 0.
rationalPrefix :: Series n -> [Rational] Source #
integerPrefix :: Series n -> [Integer] Source #
The longest initial segment of coefficients that are integral
eval :: Series n -> Rat -> Rat Source #
Evaluate the polynomial p
at x
using Horner's method.
>>>
let x = polynomial (Proxy :: Proxy 5) [0,1]
>>>
eval (1-x+x^2) 2
Val (3 % 1)
Operations
(.*) :: Series n -> Series n -> Series n Source #
Coefficient wise multiplication of two power series. Also called the Hadamard product.
(^!) :: KnownNat n => Series n -> Rat -> Series n Source #
A power series raised to a rational power.
>>>
series (Proxy :: Proxy 4) [1,2,3,4] ^! (1/2)
series (Proxy :: Proxy 4) [Val (1 % 1),Val (1 % 1),Val (1 % 1),Val (1 % 1)]
(?) :: KnownNat n => Series n -> Series n -> Series n infixr 7 Source #
Select certain coefficients of the first series, based on indices from the second series, returning the selection as a series. Elements of the second series that are not nonnegative integers or not less than the precision are ignored; trailing zeros are also ignored.
o :: Series n -> Series n -> Series n infixr 7 Source #
The composition of two power series.
>>>
let x = polynomial (Proxy :: Proxy 4) [0,1]
>>>
(1/(1-x)) `o` (2*x)
series (Proxy :: Proxy 4) [Val (1 % 1),Val (2 % 1),Val (4 % 1),Val (8 % 1)]
derivative :: Series n -> Series n Source #
The (formal) derivative of a power series.
revert :: Series n -> Series n Source #
Reversion (compositional inverse) of a power series. Unless the constant of the power series is zero the result is indeterminate.
>>>
revert $ series (Proxy :: Proxy 4) [0,1,2,3]
series (Proxy :: Proxy 4) [Val (0 % 1),Val (1 % 1),Val ((-2) % 1),Val (5 % 1)]
>>>
revert $ series (Proxy :: Proxy 4) [1,1,1,1]
series (Proxy :: Proxy 4) [Indet,Indet,Indet,Indet]
fac :: KnownNat n => Series n -> Series n Source #
The factorial of a constant power series. If the the power series
isn't constant, then the result is indeterminate (represented using
Indet
).
>>>
fac (polynomial (Proxy :: Proxy 4) [3])
series (Proxy :: Proxy 4) [Val (6 % 1),Val (0 % 1),Val (0 % 1),Val (0 % 1)]
rseq :: Series n -> Series n Source #
Construct a series that has coefficient 1 for each term whose power is some coefficient of the input series and 0 elsewhere. Elements of the input series that are not nonnegative integers or not less than the precision are ignored; trailing zeros are also ignored.
>>>
rseq $ series (Proxy :: Proxy 4) [1,3]
series (Proxy :: Proxy 4) [Val (0 % 1),Val (1 % 1),Val (0 % 1),Val (1 % 1)]