Representation of Polynomials using 'gasp'

A normal form representation of polynomials of many variables is defined like so:

type Mono = Exponential (Map String Int)
newtype Poly a = P (Map Mono a) deriving (Additive,Group,AbelianAdditive)

Monomials are maps from variables to their exponents (which we take here to be integers). So x²y is represented as x ↦ 2, y ↦ 1. Such a map automatically comes with an additive instance (because integers are themselves additive). This instance does what we need, considering that non-present keys are mapped to zero. But, adding exponents corresponds to multiplying monomials. So, we wrap this map in an Exponential newtype, given by gasp, which gives a multiplicative interface to this additive structure. So, in a single line, we have a full monomial representation, together with the structure we need.

Polynomials follow a similar principle: monomials are mapped to their coefficients. Each monomial,coeffecient pair corresponds to a term in the polynomials. Adding two polynomials correspond to adding the coefficients associated with each monomial, and this is what the Map instance does. Unfortunately, we’re still missing the additive structure.

Fortunately it’s a 3-liner:

instance (Eq a, Ord a,Ring a) => Multiplicative (Poly a) where
  one = P (M.singleton one one)
  P p * P q = P (M.fromListWith (+) [ (m1 * m2, coef1 * coef2)
                                    | (m1,coef1) <- M.toList p,
                                      (m2,coef2) <- M.toList q])

The unit maps the monomial 1 with the coefficient 1. Multiplication of monomials corresponds to multipliying all pairs of monomials in the inputs. The associated coefficients are multiplied in the same way. Then, we reconstruct the map from monomials to coefficients— ensuring that monomials which are found several times get their coefficients added.

For good measure, we can provide module, ring and show instances:

instance  (Eq c, Ord c,Ring c, Ord e,Additive e) => Module (Poly c e) (Poly c e) where
  (*^) = (*)
instance (Eq c, Ord c,Ring c,Ord e,Additive e) => Ring (Poly c e) where
instance Show e => Show (Mono e) where
  show (Exponential xs) = concat ([m <> "^" <> show coef  | (m,coef) <- M.toList xs]) 
instance (Show c, Show e) => Show (Poly c e) where
  show (P xs) = intercalate "+" ([show coef <> show m  | (m,coef) <- M.toList xs])