-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | NumericPrelude extras
--   
--   Various extras to extend the NumericPrelude, including multivariate
--   polynomials and factored rationals.
@package np-extras
@version 0.2


-- | Monomials in a countably infinite set of variables x1, x2, x3, ...
module MathObj.Monomial

-- | A monomial is a map from variable indices to integer powers, paired
--   with a (polymorphic) coefficient. Note that negative integer powers
--   are handled just fine, so monomials form a field.
--   
--   Instances are provided for Eq, Ord, ZeroTestable, Additive, Ring,
--   Differential, and Field. Note that adding two monomials only makes
--   sense if they have matching variables and exponents. The Differential
--   instance represents partial differentiation with respect to x1.
--   
--   The Ord instance for monomials orders them first by permutation
--   degree, then by largest variable index (largest first), then by
--   exponent (largest first). This may seem a bit odd, but in fact
--   reflects the use of these monomials to implement cycle index series,
--   where this ordering corresponds nicely to generation of integer
--   partitions. To make the library more general we could parameterize
--   monomials by the desired ordering.
data T a
Cons :: a -> Map Integer Integer -> T a
coeff :: T a -> a
powers :: T a -> Map Integer Integer
mkMonomial :: a -> [(Integer, Integer)] -> T a

-- | Create a constant monomial.
constant :: a -> T a

-- | Create the monomial xn for a given n.
x :: (C a) => Integer -> T a

-- | The degree of a monomial is the sum of its exponents.
degree :: T a -> Integer

-- | The "partition degree" of a monomial is the sum of the products of
--   each variable index with its exponent. For example, x1^3 x2^2 x4^3 has
--   partition degree 1*3 + 2*2 + 4*3 = 19. The terminology comes from the
--   fact that, for example, we can view x1^3 x2^2 x4^3 as corresponding to
--   an integer partition of 19 (namely, 1 + 1 + 1 + 2 + 2 + 4 + 4 + 4).
pDegree :: T a -> Integer

-- | Scale all the variable subscripts by a constant. Useful for operations
--   like plethyistic substitution or Mobius inversion.
scaleMon :: Integer -> T a -> T a
instance (Eq a) => Eq (Rev a)
instance (C a, C a, Eq a) => C (T a)
instance (C a, C a) => C (T a)
instance (C a, C a) => C (T a)
instance (C a, C a) => C (T a)
instance (C a) => C (T a)
instance (Ord a) => Ord (Rev a)
instance Ord (T a)
instance Eq (T a)
instance (C a, C a, Eq a, Show a) => Show (T a)


-- | Polynomials in a countably infinite set of variables x1, x2, x3, ...
module MathObj.MultiVarPolynomial

-- | A polynomial is just a list of monomials, construed as their sum. We
--   maintain the invariant that polynomials are always sorted by the
--   ordering on monomials defined in <a>MathObj.Monomial</a>: first by
--   partition degree, then by largest variable index (decreasing), then by
--   exponent of the highest-index variable (decreasing). This works out
--   nicely for operations on cycle index series.
--   
--   Instances are provided for Additive, Ring, Differential (partial
--   differentiation with respect to x1), and Show.
newtype T a
Cons :: [T a] -> T a
fromMonomials :: [T a] -> T a
lift0 :: [T a] -> T a
lift1 :: ([T a] -> [T a]) -> (T a -> T a)
lift2 :: ([T a] -> [T a] -> [T a]) -> (T a -> T a -> T a)

-- | Create the polynomial xn for a given n.
x :: (C a) => Integer -> T a

-- | Create a constant polynomial.
constant :: a -> T a

-- | Plethyistic substitution: F o G = F(G(x1,x2,x3...), G(x2,x4,x6...),
--   G(x3,x6,x9...), ...) See Bergeron, Labelle, and Leroux, "Combinatorial
--   Species and Tree-Like Structures", p. 43.
compose :: (C a, C a) => T a -> T a -> T a

-- | Merge two sorted lists, with a flag specifying whether to keep
--   singletons, and a combining function for elements that are equal.
merge :: (Ord a) => Bool -> (a -> a -> a) -> [a] -> [a] -> [a]
instance (C a, C a) => C (T a)
instance (C a, C a) => C (T a)
instance (C a, C a) => C (T a)
instance (C a, C a, Ord a, Show a) => Show (T a)


-- | A representation of rational numbers as lists of prime powers,
--   allowing efficient representation, multiplication and division of
--   large numbers, especially of the sort occurring in combinatorial
--   computations.
--   
--   The module also includes a method for generating factorials in
--   factored form directly, and for generating all divisors of factored
--   integers, or computing Euler's totient (phi) function and the Mbius
--   (mu) function.
module MathObj.FactoredRational

-- | The type of factored rationals.
--   
--   Instances are provided for Eq, Ord, Additive, Ring, ZeroTestable,
--   Real, ToRational, Integral, RealIntegral, ToInteger, and Field.
--   
--   Note that currently, addition is performed on factored rationals by
--   converting them to normal rationals, performing the addition, and
--   factoring. This could probably be made more efficient by finding a
--   common denominator, pulling out common factors from the numerators,
--   and performing the addition and factoring only on the relatively prime
--   parts.
data T

-- | Efficiently compute n! directly as a factored rational.
factorial :: Integer -> T

-- | Compute Euler's totient function (<tt>eulerPhi n</tt> is the number of
--   integers less than and relatively prime to n). Only makes sense for
--   (nonnegative) integers.
eulerPhi :: T -> Integer

-- | List of the divisors of n. Only makes sense for integers.
divisors :: T -> [T]

-- | Mbius (mu) function of a positive integer: mu(n) = 0 if one or more
--   repeated prime factors, 1 if n = 1, and (-1)^k if n is a product of k
--   distinct primes.
mu :: T -> Integer
instance C T
instance C T
instance C T
instance C T
instance C T
instance C T
instance Ord T
instance Eq T
instance C T
instance C T
instance C T
instance Show T