Generic Functions in Haskell... I don't get it :(

Question

I think my problem is that I'm confounding my very limited knowledge of Haskell's polymorphism with things like overloading and templating, from other languages. After my previous question, I thought I had a better grasp on the concepts, but having tried again, I guess not!

Anyway, I am trying to implement a generic distance function. That was straightforward enough:

euclidean :: Integral a => [a] -> [a] -> Double
euclidean a b = sqrt . sum $ zipWith (\u v -> (u - v)^2) x y
                where x = map fromIntegral a
                      y = map fromIntegral b

Now I want to apply this to two vector types (which, for the sake of argument, cannot be redefined):

type Vector1 = Integer
data Vector2 = Vector2 Integer Integer

After reading the answers to my previous question, I figured I would go with pattern matching:

d :: a -> a -> Double
d (Vector2 x1 y1) (Vector2 x2 y2) = euclidean [x1, y1] [x2, y2]
d a b = euclidean [a] [b]

This fails:

Couldn't match expected type `a' with actual type `Vector2'
  `a' is a rigid type variable bound by
      the type signature for d :: a -> a -> Double at test.hs:11:6
In the pattern: Vector2 x1 y1
In an equation for `d':
    d (Vector2 x1 y1) (Vector2 x2 y2) = euclidean [x1, y1] [x2, y2]

So I figure I'll throw caution to the wind and try type classes again:

{-# LANGUAGE FlexibleInstances #-}

class Metric a where
  d :: a -> a -> Double

instance Metric Vector1 where
  d a b = euclidean [a] [b]

instance Metric Vector2 where
  d (Vector2 x1 y1) (Vector2 x2 y2) = euclidean [x1, y1] [x2, y2]

This compiles and works when the type you're feeding into d is known in advance. However, in my case, I have written another function, which calls d, where the type could be either (it's determined at runtime). This fails:

No instance for (Metric a) arising from a use of `d'
Possible fix:
  add (Metric a) to the context of
    the type signature for someFunction :: [a] -> [a] -> [a]
In the expression: d c x
In the expression: (x, d c x)
In the first argument of `map', namely `(\ x -> (x, d c x))'

From my limited understanding of the answers to my previous question, I believe the reason for this is because my type class has holes in it, which leads the type inferencer into an indeterminable state.

At this point, I'm at a bit of a loss: neither parametric nor ad hoc polymorphism has solved my problem. As such, my solution was this mess:

someFunction1 :: [Vector1] -> [Vector1] -> [Vector1]
-- Lots of code
where d a b = euclidean [a] [b]

someFunction2 :: [Vector2] -> [Vector2] -> [Vector2]
-- Exactly the same code
where d (Vector2 x1 y1) (Vector2 x2 y2) = euclidean [x1, y1] [x2, y2]

This doesn't seem right. What am I missing?

Answer 1

In the first case, you have

d :: a -> a -> Double

which means the function can be called with any type, for example

d "blah" "blah"

but you are assuming it is of type Vector2 in the implementation. So the compiler complains.

The second error is essentially the same thing. You have

someFunction :: [a] -> [a] -> [a]

which again assumes a can take any type, but the implementation requires that it is of type Metric because you are calling the typeclass function. This is what the compiler is suggesting in the error message. So you want to use:

someFunction :: (Metric a) => [a] -> [a] -> [a]

Answer 2

compiller is telling you that you should restrict a in someFunction. you are using d but type signature states that its valid for any a, but it should be valid only for a that has an instance of Metric.

The solution is to restrict a to be of class Metric:

someFunction :: (Metric a) => [a] -> [a] -> [a]