Type class definition with functions depending on an additional type

Question

Still new to Haskell, I have hit a wall with the following:

I am trying to define some type classes to generalize a bunch of functions that use gaussian elimination to solve linear systems of equations.

Given a linear system

M x = k

the type a of the elements m(i,j) \elem M can be different from the type b of x and k. To be able to solve the system, a should be an instance of Num and b should have multiplication/addition operators with b, like in the following:

class MixedRing b where
    (.+.) :: b -> b -> b
    (.*.) :: (Num a) => b -> a -> b
    (./.) :: (Num a) => b -> a -> b

Now, even in the most trivial implementation of these operators, I'll get Could not deduce a ~ Int. a is a rigid type variable errors (Let's forget about ./. which requires Fractional)

data Wrap = W { get :: Int }
instance MixedRing Wrap where
    (.+.) w1 w2 = W $ (get w1) + (get w2)
    (.*.) w s   = W $ ((get w) * s)

I have read several tutorials on type classes but I can find no pointer to what actually goes wrong.

Answer 1

Let us have a look at the type of the implementation that you would have to provide for (.*.) to make Wrap an instance of MixedRing. Substituting Wrap for b in the type of the method yields

(.*.) :: Num a => Wrap -> a -> Wrap

As Wrap is isomorphic to Int and to not have to think about wrapping and unwrapping with Wrap and get, let us reduce our goal to finding an implementation of

(.*.) :: Num a => Int -> a -> Int

(You see that this doesn't make the challenge any easier or harder, don't you?)

Now, observe that such an implementation will need to be able to operate on all types a that happen to be in the type class Num. (This is what a type variable in such a type denotes: universal quantification.) Note: this is not the same (actually, it's the opposite) of saying that your implementation can itself choose what a to operate on); yet that is what you seem to suggest in your question: that your implementation should be allowed to pick Int as a choice for a.

Now, as you want to implement this particular (.*.) in terms of the (*) for values of type Int, we need something of the form

n .*. s = n * f s

with

f :: Num a => a -> Int

I cannot think of a function that converts from an arbitary Num-type a to Int in a meaningful way. I'd therefore say that there is no meaningful way to make Int (and, hence, Wrap) an instance of MixedRing; that is, not such that the instance behaves as you would probably expect it to do.

Answer 2

How about something like:

class (Num a) => MixedRing a b where
    (.+.) :: b -> b -> b
    (.*.) :: b -> a -> b
    (./.) :: b -> a -> b

You'll need the MultiParamTypeClasses extension.

By the way, it seems to me that the mathematical structure you're trying to model is really module, not a ring. With the type variables given above, one says that b is an a-module.

Answer 3

Your implementation is not polymorphic enough.

The rule is, if you write a in the class definition, you can't use a concrete type in the instance. Because the instance must conform to the class and the class promised to accept any a that is Num.

To put it differently: Exactly the class variable is it that must be instantiated with a concrete type in an instance definition.

Have you tried:

data Wrap a = W { get :: a }

Note that once Wrap a is an instance, you can still use it with functions that accept only Wrap Int.