how do you do recursion with type classes and data type in Haskell?

Question

I am working on a type class for fraction, vector, and matrix arithmetic (ie add, sub, mul) but can't quite get the vector instance because I don't know how to work with the recursive nature of the function.

here's the code:

class MathObject a where
    add :: a -> a -> a
    sub :: a -> a -> a
    mul :: a -> a -> a


type Vector = [Int]


data Vec = Vec Vector deriving (Show, Eq)


instance MathObject Vec where 
    add (Vec v1) (Vec v2) = addVecs (Vec v1) (Vec v2)
    sub (Vec v1) (Vec v2) = subVecs (Vec v1) (Vec v2)
    mul (Vec v1) (Vec v2) = mulVecs (Vec v1) (Vec v2)

addVecs :: Vec -> Vec -> [Int]
addVecs (Vec []) (Vec vec2)= (Vec [])
addVecs (Vec vec) (Vec []) = (Vec [])
addVecs (Vec (x:xs)) (Vec (y:ys)) = e1+e2:rest where
  e1 = x
  e2 = y
  rest = addVecs (Vec xs) (Vec ys)

subVecs :: Vec -> Vec -> [Int]
subVecs (Vec []) (Vec v2) = (Vec [])
subVecs (Vec (x:xs)) (Vec (y:ys)) = x-y:rest where
  rest = subVecs (Vec xs) (Vec ys)

mulVecs :: Vec -> Vec -> [Vec]
mulVecs (Vec []) (Vec vec2) = (Vec [])
mulVecs (Vec (x:xs)) (Vec (y:ys)) = e1 * e2:rest where
  e1 = x
  e2 = y
  rest = mulVecs (Vec xs) (Vec ys)

I made the fraction instance and it works so I have some basic understanding of how type classes work but I just don't know how to deal with a recursive type.

Answer 1

I would say, first, you have confused yourself with too many different things named something that sounds like "vector". Why does the Vec type have a constructor named Vec and fields of type Vector? What's the difference really between a Vec and a Vector? If Vector is an alias for [Int], why do you use ordinary [Int] to represent vectors sometimes? You don't include the compiler errors you get, but I can see clearly that at least some of them will arise due to type mismatches between these names.

So the first thing to do is simplify it: just have one Vector type, which is a newtype (or data if you haven't gotten to newtypes yet) wrapper around [Int]:

newtype Vector = Vector [Int]

Now you always know whether you're working with a Vector or an [Int], and can convert between the two using the Vector constructor.

My next observation would be that addVecs and friends clearly have the wrong type: why do they take two Vector inputs and return an [Int]? They should stick with one type, preferably Vector. This is the cause of one of your type errors: add needs to be of type a -> a -> a, but you've defined add to be addVecs, which has type Vec -> Vec -> [Int] - that doesn't fit! So let's instead write

addVecs :: Vector -> Vector -> Vector
-- ...

Now, the implementation is right given the poor type you chose for it. But to work for the better type, we'd have to add a Vector wrapper around a+b before consing it to the result. I won't show that implementation, though, because there's a much better one available. Instead of doing the recursion yourself, use one of Haskell's many flexible tools for working with lists: zipWith.

addVecs (Vector v1) (Vector v2) = Vector $ zipWith (+) v1 v2

This does exactly the same thing as your implementation, but all the tedious wrapping and unwrapping is done only once, and recursive list processing is completely abstracted away by zipWith.

You could do the same thing for subVecs and mulVecs, but you would quickly notice there's some duplication here. It would be better to extract that out into a function, so that those three functions can all share the common code:

pointwise :: (Int -> Int -> Int) -> (Vector -> Vector -> Vector)
pointwise f (Vector v1) (Vector v2) = Vector $ zipWith f v1 v2

addVecs = pointwise (+)
subVecs = pointwise (-)
mulVecs = pointwise (*)

At this point you don't even really need definitions for addVecs and friends - you could easily inline them into the MathObject instance:

instance MathObject Vector where
  add = pointwise (+)
  sub = pointwise (-)
  mul = pointwise (*)