úÎS]Q@      =A monomial is a map from variable indices to integer powers, @ paired with a (polymorphic) coefficient. Note that negative D integer powers are handled just fine, so monomials form a field. BInstances are provided for Eq, Ord, ZeroTestable, Additive, Ring, A Differential, and Field. Note that adding two monomials only C makes sense if they have matching variables and exponents. The A Differential instance represents partial differentiation with  respect to x1. @The Ord instance for monomials orders them first by permutation C degree, then by largest variable index (largest first), then by C 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 D of integer partitions. To make the library more general we could 3 parameterize monomials by the desired ordering. 6The degree of a monomial is the sum of its exponents. The "partition degree"* of a monomial is the sum of the products E of each variable index with its exponent. For example, x1^3 x2^2 D x4^3 has partition degree 1*3 + 2*2 + 4*3 = 19. The terminology E comes from the fact that, for example, we can view x1^3 x2^2 x4^3 E as corresponding to an integer partition of 19 (namely, 1 + 1 + 1  + 2 + 2 + 4 + 4 + 4). Create a constant monomial. &Create the monomial xn for a given n. =Scale all the variable subscripts by a constant. Useful for A operations like plethyistic substitution or Mobius inversion.    BA polynomial is just a list of monomials, construed as their sum. C We maintain the invariant that polynomials are always sorted by ( the ordering on monomials defined in MathObj.Monomial : first by B 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. 8Instances are provided for Additive, Ring, Differential ; (partial differentiation with respect to x1), and Show. (Create the polynomial xn for a given n. Create a constant polynomial. AAdd two polynomials. We assume that they are already sorted, so 0 that addition works on infinite polynomials. ?Merge two sorted lists, with a combining function for elements  that are equal. #Multiply two (sorted) polynomials. 4Plethyistic substitution: F o G = F(G(x1,x2,x3...), D G(x2,x4,x6...), G(x3,x6,x9...), ...) See Bergeron, Labelle, and  Leroux, ".Combinatorial Species and Tree-Like Structures",  p. 43. 4We need to be careful to make sure this is suitably 9 lazy. For example, this works for finite polynomials:  ) comp ms p = sum . map (substMon p) $ ms but not for infinite ones! <This is accomplished by calling a recursive helper function C taking as an extra argument a running sum containing only terms D with partition degree greater than or equal to the most recently B processed monomial. Plethyistically substituting a polynomial A (with no constant term) into a monomial of partition degree d E produces a polynomial with all terms of partition degree >= d, so D when we encounter a monomial with partition degree d, we know we B are done with all terms in the running sum of lesser partition  degree. 8Precondition: the second argument has no constant term. :Plethyistic substitution of a polynomial into a monomial.  scalePoly n Z< changes Z(x_1, x_2, x_3, ...) into Z(x_n, x_2n, x_3n, ...) 9Split a polynomial into two pieces based on a predicate.      The type of factored rationals. BInstances are provided for Eq, Ord, Additive, Ring, ZeroTestable, C Real, ToRational, Integral, RealIntegral, ToInteger, and Field. ANote that currently, addition is performed on factored rationals D by converting them to normal rationals, performing the addition, A and factoring. This could probably be made more efficient by E finding a common denominator, pulling out common factors from the E numerators, and performing the addition and factoring only on the  relatively prime parts. !0prime exponents with sign bit, True = negative. "zero #$@Zip two lists together with a combining function, using default @ values to extend the lists if one is shorter than the other. %A simple factoring method. ;We should probably just depend on another module with some A dedicated, efficient factoring code written by someone really 3 smart, but this simple method works OK for now. $Precondition: argument is positive. & logRem n p computes (k,n'%), where k is the highest power of p  that divides n, and n' = n ' p^k. 8Efficiently compute n! directly as a factored rational. (factorialFactors n p& computes the power of prime p in the  factorization of n!.  Compute Euler's totient function ( eulerPhi n is the number of D integers less than and relatively prime to n). Only makes sense  for (nonnegative) integers. ;List of the divisors of n. Only makes sense for integers. )        !"#$%&'() np-extras-0.1MathObj.MonomialMathObj.MultiVarPolynomialMathObj.FactoredRationalTConscoeffpowersdegreepDegreeconstantxscaleMon fromMonomialslift0lift1lift2compose factorialeulerPhidivisorsRevgetRevshowVarsaddmergemulcompsubstMon scalePoly splitPolyFQFQZeroshowPows zipWithExtfactorlogRemnumeric-prelude-0.1.3.4Algebra.IntegralDomaindivfactorialFactors