# 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
= P (M.singleton one one)
one P p * P q = P (M.fromListWith (+) [ (m1 * m2, coef1 * coef2)
| (m1,coef1) <- M.toList p,
<- M.toList q]) (m2,coef2)
```

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])
```