Defining a data type that doesn't want to be defined

Question

I have a data type Polynomial r for polynomials in Haskell and a Ring instance for it. (The class Ring r where plus :: r -> r -> r ; times :: r -> r -> r ; negative :: r -> r ; zero :: r ; one :: r -- it's just a simplified version of Num).

Now I could define a polynomial such as gauss = x^2 + 1 or eisenstein = x^2 + x + 1 and then work in "Polynomial Integer/(gauss)" for the Gaussian integers or "Polynomial Integer/(eisenstein)" for the Eisenstein integers. That's the problem, I wrote it in quotes because it's not a real data type, and I can't figure out how to define it.

I first tried to do something like data Quotient p = Quot p p and then for example we would have plus (Quot a i) (Quot b i') | i == i' = Quot (plus a b) i Of course this is pretty bad already but it's not even possible to define one and zero. So I changed it to data Quotient p = Quot p (Maybe p) and I think I have a working implementation using that but you never know for sure if plus will work (it needs at least one Just, and if there are two they must be the same).

Is there any type safe (I mean not using unsafe functions) way to program this in haskell? I am pretty stumped. Thanks!

Answer 1

Perhaps you could augment your polynomial type with an index or tag? If I understand correctly, your normal module would be something like:

data Poly r = Poly r

class Ring r where
  plus :: r -> r -> r
  times :: r -> r -> r

instance Ring (Poly Integer) where
  plus (Poly x) (Poly y) = Poly (x + y)
  times (Poly x) (Poly y) = Poly (x * y)

gauss :: Poly Integer
gauss = Poly 1

eins :: Poly Integer
eins = Poly 2

And you want to be able to safely differential between the two "sub-types" of the rings. Perhaps you could tag them as so:

newtype PolyI i r = PolyI r

instance Show r => Show (PolyI i r) where
  show (PolyI p) = show p

instance Ring (PolyI i Integer) where
  plus (PolyI x) (PolyI y) = PolyI (x + y)
  times (PolyI x) (PolyI y) = PolyI (x * y)

Our instances of the Ring now require an extra type-argument i, which we can create by having simple no-constructor types.

data Gauss
data Eins

Then we just create the specific polynomials with the index as an argument:

gaussI :: PolyI Gauss Integer
gaussI = PolyI 11

einsI :: PolyI Eins Integer
einsI = PolyI 20

With the Show instance above, we get the following output:

*Poly> plus einsI einsI
40

and then

*Poly> plus einsI gaussI

Couldn't match expected type `Eins' with actual type `Gauss'
Expected type: PolyI Eins Integer
  Actual type: PolyI Gauss Integer
In the second argument of `plus', namely `gaussI'

Is that something like what you were looking for?

Edit: after a comment to the question about newtype, I think this may also an elegant solution if you use NewtypeDeriving to ease the burden of re-implementing the Poly Integer instance. I think in the end it would be similar, if slightly more elegant than this approach.