Monomials in a countably infinite set of variables x1, x2, x3, ...
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.
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).