Modulenumeric-prelude-0.4.4Haskell98

MathObj.PartialFraction

Implementation of partial fractions. Useful e.g. for fractions of integers and fractions of polynomials.

For the considered ring the prime factorization must be unique.

1 type
28 values

Packagenumeric-prelude-0.4.4
Exports29
LanguageHaskell98
LicenceBSD-3-Clause
SourcePartialFraction.hs

Example66 expressions

>>> import qualified MathObj.PartialFraction as PartialFraction>>> import qualified MathObj.Polynomial.Core as PolyCore>>> import qualified MathObj.Polynomial as Poly>>> import qualified Algebra.PrincipalIdealDomain as PID>>> import qualified Algebra.Indexable as Indexable>>> import qualified Algebra.Laws as Laws>>> import qualified Number.Ratio as Ratio>>> import Test.NumericPrelude.Utility ((/\))>>> import qualified Test.QuickCheck as QC>>> import NumericPrelude.Numeric as NP>>> import NumericPrelude.Base as P>>> import Prelude ()>>> >>> import Control.Applicative (liftA2)>>> >>> {- |>>> Generator of irreducible elements for tests.>>> Choosing from a list of examples is a simple yet effective design.>>> If we would construct irreducible elements by a clever algorithm>>> we might obtain multiple primes only rarely.>>> -} -->>> genSmallPrime :: QC.Gen Integer>>> genSmallPrime =>>>    let primes = [2,3,5,7,11,13]>>>    in  QC.elements (primes ++ map negate primes)>>> >>> genPartialFractionInt :: QC.Gen (PartialFraction.T Integer)>>> genPartialFractionInt =>>>    liftA2 PartialFraction.fromFactoredFraction>>>       (QC.listOf genSmallPrime) QC.arbitrary>>> >>> >>> genIrreduciblePolynomial :: QC.Gen (Poly.T Rational)>>> genIrreduciblePolynomial = do>>>    QC.NonZero unit <- QC.arbitrary>>>    fmap (Poly.fromCoeffs . map (unit*)) $>>>       QC.elements [[2,3],[2,0,1],[3,0,1],[1,-3,0,1]]>>> >>> genPartialFractionPoly :: QC.Gen (PartialFraction.T (Poly.T Rational))>>> genPartialFractionPoly =>>>    liftA2 PartialFraction.fromFactoredFraction>>>       (fmap (take 3) $ QC.listOf genIrreduciblePolynomial)>>>       (fmap (Poly.fromCoeffs . PolyCore.normalize . take 5) QC.arbitrary)>>> >>> >>> fractionConv :: (PID.C a, Indexable.C a) => [a] -> a -> Bool>>> fractionConv xs y =>>>    PartialFraction.toFraction (PartialFraction.fromFactoredFraction xs y) ==>>>    y % product xs>>> >>> fractionConvAlt :: (PID.C a, Indexable.C a) => [a] -> a -> Bool>>> fractionConvAlt xs y =>>>    PartialFraction.fromFactoredFraction xs y ==>>>    PartialFraction.fromFactoredFractionAlt xs y>>> >>> scaleInt :: (PID.C a, Indexable.C a) => a -> PartialFraction.T a -> Bool>>> scaleInt k a =>>>    PartialFraction.toFraction (PartialFraction.scaleInt k a) ==>>>    Ratio.scale k (PartialFraction.toFraction a)>>> >>> add, sub, mul ::>>>    (PID.C a, Indexable.C a) =>>>>    PartialFraction.T a -> PartialFraction.T a -> Bool>>> add = Laws.homomorphism PartialFraction.toFraction (+) (+)>>> sub = Laws.homomorphism PartialFraction.toFraction (-) (-)>>> mul = Laws.homomorphism PartialFraction.toFraction (*) (*)

datadata T a

Cons z (indexMapFromList [(x0,[y00,y01]), (x1,[y10]), (x2,[y20,y21,y22])]) represents the partial fraction z + y00x0 + y01x0^2 + y10x1 + y20x2 + y21x2^2 + y22x2^3 The denominators x0, x1, x2, ... must be irreducible, but we can't check this in general. It is also not enough to have relatively prime denominators, because when adding two partial fraction representations there might concur denominators that have non-trivial common divisors.

Constructors

Cons a (Map (ToOrd a) [a])

Instances4Eq, Show, C

Eq a => Eq (T a)Defined in numeric-prelude-0.4.4 · MathObj.PartialFraction
Show a => Show (T a)Defined in numeric-prelude-0.4.4 · MathObj.PartialFraction
(C a, C a) => C (T a)Defined in numeric-prelude-0.4.4 · MathObj.PartialFraction

(C a, C a, C a) => C (T a)Defined in numeric-prelude-0.4.4 · MathObj.PartialFraction

Property

prop> genPartialFractionInt /\ \x -> genPartialFractionInt /\ \y -> add x y

Property

prop> genPartialFractionInt /\ \x -> genPartialFractionInt /\ \y -> sub x y

Property

prop> genPartialFractionPoly /\ \x -> genPartialFractionPoly /\ \y -> add x y

Property

prop> genPartialFractionPoly /\ \x -> genPartialFractionPoly /\ \y -> sub x y

valuefromFractionSum :: C a => a -> [(a, [a])] -> T a

Unchecked construction.

valuetoFractionSum :: C a => T a -> (a, [(a, [a])])

valueappPrec :: Int

valuetoFraction :: C a => T a -> T a

valuetoFactoredFraction :: C a => T a -> ([a], a)

PrincipalIdealDomain.C is not really necessary here and only due to invokation of toFraction.

valuemultiToFraction :: C a => a -> [a] -> T a

PrincipalIdealDomain.C is not really necessary here and only due to invokation of %.

valuehornerRev :: C a => a -> [a] -> a

valuefromFactoredFraction :: (C a, C a) => [a] -> a -> T a

fromFactoredFraction x y computes the partial fraction representation of y % product x, where the elements of x must be irreducible. The function transforms the factors into their standard form with respect to unit factors.

There are more direct methods for special cases like polynomials over rational numbers where the denominators are linear factors.

Property

prop> QC.listOf genSmallPrime /\ fractionConv

Property

prop> fmap (take 3) (QC.listOf genIrreduciblePolynomial) /\ fractionConv

valuefromFactoredFractionAlt :: (C a, C a) => [a] -> a -> T a

Property

prop> QC.listOf genSmallPrime /\ fractionConvAlt

Property

prop> fmap (take 3) (QC.listOf genIrreduciblePolynomial) /\ fractionConvAlt

valuemultiFromFraction :: C a => [a] -> a -> (a, [a])

The list of denominators must contain equal elements. Sorry for this hack.

valuefromValue :: a -> T a

valuereduceHeads :: C a => T a -> T a

A normalization step which separates the integer part from the leading fraction of each sub-list.

valuecarryRipple :: C a => a -> [a] -> (a, [a])

Cf. Number.Positional

valuenormalizeModulo :: C a => T a -> T a

A normalization step which reduces all elements in sub-lists modulo their denominators. Zeros might be the result, that must be remove with removeZeros.

valueremoveZeros :: (C a, C a) => T a -> T a

Remove trailing zeros in sub-lists because if lists are converted to fractions by multiToFraction we must be sure that the denominator of the (cancelled) fraction is indeed the stored power of the irreducible denominator. Otherwise mulFrac leads to wrong results.

valuezipWith :: C a => (a -> a -> a) -> ([a] -> [a] -> [a]) -> T a -> T a -> T a

valuemulFrac :: C a => T a -> T a -> (a, a)

Transforms a product of two partial fractions into a sum of two fractions. The denominators must be at least relatively prime. Since T requires irreducible denominators, these are also relatively prime.

Example: mulFrac (1%6) (1%4) fails because of the common divisor 2.

valuemulFrac' :: C a => T a -> T a -> (T a, T a)

valuemulFracStupid :: C a => T a -> T a -> ((T a, T a), T a)

Works always but simply puts the product into the last fraction.

valuemulFracOverlap :: C a => T a -> T a -> ((T a, T a), T a)

Also works if the operands share a non-trivial divisor. However the results are quite arbitrary.

valuescaleFrac :: (C a, C a) => T a -> T a -> T a

Expects an irreducible denominator as associate in standard form.

valuescaleInt :: (C a, C a) => a -> T a -> T a

Property

prop> genPartialFractionInt /\ \x k -> scaleInt k x

Property

prop> genPartialFractionPoly /\ \x k -> scaleInt k x

valuemul :: (C a, C a) => T a -> T a -> T a

valuemulFast :: (C a, C a) => T a -> T a -> T a

Property

prop> genPartialFractionInt /\ \x -> genPartialFractionInt /\ \y -> mul x y

Property

prop> genPartialFractionPoly /\ \x -> genPartialFractionPoly /\ \y -> mul x y

Helper functions for work with Maps with Indexable keys

4 declarations

valueindexMapMapWithKey :: (a -> b -> c) -> Map (ToOrd a) b -> Map (ToOrd a) c

valueindexMapToList :: Map (ToOrd a) b -> [(a, b)]

valueindexMapFromList :: C a => [(a, b)] -> Map (ToOrd a) b

valuemapApplySplit

:: Ord a
=> a
-> c -> c -> c
-> b -> c
-> Map a b -> Map a c
-> Map a b
-> Map a c

Apply a function on a specific element if it exists, and another function to the rest of the map.