Copyright | (c) Henning Thielemann 2007 |
---|---|

Maintainer | numericprelude@henning-thielemann.de |

Stability | provisional |

Portability | portable |

Safe Haskell | None |

Language | Haskell98 |

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.

- data T a = Cons a (Map (ToOrd a) [a])
- fromFractionSum :: C a => a -> [(a, [a])] -> T a
- toFractionSum :: C a => T a -> (a, [(a, [a])])
- appPrec :: Int
- toFraction :: C a => T a -> T a
- toFactoredFraction :: C a => T a -> ([a], a)
- multiToFraction :: C a => a -> [a] -> T a
- hornerRev :: C a => a -> [a] -> a
- fromFactoredFraction :: (C a, C a) => [a] -> a -> T a
- fromFactoredFractionAlt :: (C a, C a) => [a] -> a -> T a
- multiFromFraction :: C a => [a] -> a -> (a, [a])
- fromValue :: a -> T a
- reduceHeads :: C a => T a -> T a
- carryRipple :: C a => a -> [a] -> (a, [a])
- normalizeModulo :: C a => T a -> T a
- removeZeros :: (C a, C a) => T a -> T a
- zipWith :: C a => (a -> a -> a) -> ([a] -> [a] -> [a]) -> T a -> T a -> T a
- mulFrac :: C a => T a -> T a -> (a, a)
- mulFrac' :: C a => T a -> T a -> (T a, T a)
- mulFracStupid :: C a => T a -> T a -> ((T a, T a), T a)
- mulFracOverlap :: C a => T a -> T a -> ((T a, T a), T a)
- scaleFrac :: (C a, C a) => T a -> T a -> T a
- scaleInt :: (C a, C a) => a -> T a -> T a
- mul :: (C a, C a) => T a -> T a -> T a
- mulFast :: (C a, C a) => T a -> T a -> T a
- indexMapMapWithKey :: (a -> b -> c) -> Map (ToOrd a) b -> Map (ToOrd a) c
- indexMapToList :: Map (ToOrd a) b -> [(a, b)]
- indexMapFromList :: C a => [(a, b)] -> Map (ToOrd a) b
- mapApplySplit :: Ord a => a -> (c -> c -> c) -> (b -> c) -> (Map a b -> Map a c) -> Map a b -> Map a c

# Documentation

`Cons z (indexMapFromList [(x0,[y00,y01]), (x1,[y10]), (x2,[y20,y21,y22])])`

represents the partial fraction
`z + y00`

The denominators *x0 + y01*x0^2 + y10*x1 + y20*x2 + y21*x2^2 + y22*x2^3`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.

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

Unchecked construction.

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

toFraction :: C a => T a -> T a Source

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

`C`

is not really necessary here and
only due to invokation of `toFraction`

.

multiToFraction :: C a => a -> [a] -> T a Source

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

`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.

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

multiFromFraction :: C a => [a] -> a -> (a, [a]) Source

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

reduceHeads :: C a => T a -> T a Source

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

carryRipple :: C a => a -> [a] -> (a, [a]) Source

Cf. Number.Positional

normalizeModulo :: C a => T a -> T a Source

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

.

removeZeros :: (C a, C a) => T a -> T a Source

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.

mulFrac :: C a => T a -> T a -> (a, a) Source

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`

.

mulFracStupid :: C a => T a -> T a -> ((T a, T a), T a) Source

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

mulFracOverlap :: C a => T a -> T a -> ((T a, T a), T a) Source

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

scaleFrac :: (C a, C a) => T a -> T a -> T a Source

Expects an irreducible denominator as associate in standard form.

# Helper functions for work with Maps with Indexable keys

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

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