Y U     NoneA 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.5The degree of a monomial is the sum of its exponents.kThe "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).Create a constant monomial.%Create the monomial xn for a given n. }Scale all the variable subscripts by a constant. Useful for operations like plethyistic substitution or Mobius inversion.  !"#$%     !"#$%None 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 MathObj.Monomial: 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.rInstances 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.&pAdd two polynomials. We assume that they are already sorted, so that addition works on infinite polynomials.Merge two sorted lists, with a flag specifying whether to keep singletons, and a combining function for elements that are equal.'"Multiply two (sorted) polynomials.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.(lWe need to be careful to make sure this is suitably lazy. For example, this works for finite polynomials: 'comp ms p = sum . map (substMon p) $ msbut not for infinite ones!This is accomplished by calling a recursive helper function taking as an extra argument a running sum containing only terms with partition degree greater than or equal to the most recently processed monomial. Plethyistically substituting a polynomial (with no constant term) into a monomial of partition degree d produces a polynomial with all terms of partition degree >= d, so when we encounter a monomial with partition degree d, we know we are done with all terms in the running sum of lesser partition degree.7Precondition: the second argument has no constant term.)9Plethyistic 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, ...)+8Split a polynomial into two pieces based on a predicate. &'()*+,-./    &'()*+,-./None The type of factored rationals.Instances are provided for Eq, Ord, Additive, Ring, ZeroTestable, Real, ToRational, Integral, RealIntegral, ToInteger, and Field.jNote 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.0zero1/prime exponents with sign bit, True = negative.2Zip two lists together with a combining function, using default values to extend the lists if one is shorter than the other.3A simple factoring method.We should probably just depend on another module with some dedicated, efficient factoring code written by someone really smart, but this simple method works OK for now.#Precondition: argument is positive.4 logRem n pR computes (k,n'), where k is the highest power of p that divides n, and n' = n 5 p^k.7Efficiently compute n! directly as a factored rational.6factorialFactors n p= computes the power of prime p in the factorization of n!."Compute Euler's totient function ( eulerPhi nt is the number of 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.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.017234689:;<=>?@ABC017234689:;<=>?@ABCD        !"#$%&'()#*+,-./01234!"567#8npext_HU6DE28GDC38Bn31lqFhWHMathObj.MonomialMathObj.MultiVarPolynomialMathObj.FactoredRationalTConscoeffpowers mkMonomialdegreepDegreeconstantxscaleMon fromMonomialslift0lift1lift2mergecompose factorialeulerPhidivisorsmuRevnegOneshowVars$fCT$fCT0$fCT1$fCT2$fCT3$fOrdRev$fOrdT$fEqT$fShowTaddmulcompsubstMon scalePoly splitPolyFQZeroFQ zipWithExtfactorlogRemnumer_1lTPOZ9qLwH0bTC8IA0JrMAlgebra.IntegralDomaindivfactorialFactorsshowPows$fCT4$fCT5$fCT6$fCT7