How do I give a concrete value to a Haskell instance?

Question

I'm trying to learn Haskell and I'm a bit confused by this infamous "rigid type variable" error.

Here's the relevant part of my code:

class Ord v => Vector v where
  distance :: v -> v -> Double

-- with FlexibleInstances
instance Vector (Double, Double) where
  distance (a,b) (c,d) = -- function definition omitted

data KMeansState v = KMeansState { centroids :: [v] }

test :: [(Double,Double)]
test = [(0,0),(1,1)] :: [(Double,Double)]

initializeState :: Vector v => Int -> KMeansState v
initializeState n = KMeansState test

The specific complaint that the compiler is giving me:

• Couldn't match type ‘v’ with ‘(Double, Double)’
      ‘v’ is a rigid type variable bound by
        the type signature for:
          initializeState :: forall v.
                             Vector v =>
                             Int -> Double -> KMeansState v
        at Chapter06.hs:32:1-61
      Expected type: KMeansState v
        Actual type: KMeansState (Double, Double)

My understanding is that the compiler is saying my initializeState function needs to be able to return (or whatever the right word is in Haskell) a KMeansState whose type parameter is any type that's an instance of Vector, while the actual implementation of my function will only return one type, namely a KMeansState (Double, Double).

What I'm not clear on is how to get a "concrete" value out of this initializeState function. At some point in the program, I need to give the KMeansState constructor an actual value which will have an actual type, and it seems like the compiler is saying that I can't do that.

I'm further confused by why the code compiles if I hard code the value of the test function into initializeState. That is, this successfully type-checks, even though the value being passed to the KMeansState function should be functionally the same.

class Ord v => Vector v where
  distance :: v -> v -> Double

-- with FlexibleInstances
instance Vector (Double, Double) where
  distance (a,b) (c,d) = -- function definition omitted

data KMeansState v = KMeansState { centroids :: [v] }

-- test :: [(Double,Double)]
-- test = [(0,0),(1,1)] :: [(Double,Double)]

initializeState :: Vector v => Int -> KMeansState v
initializeState n = KMeansState [(0,0),(1,1)]::[(Double,Double)]

Can someone please clarify what's going on here and how I get this to compile? Thanks!

user_745903 · Answer

This is a common, fundamental misunderstanding about what Haskell typeclasses are / how they work. Concretely, a Haskell class is not like a class in OO languages. It is in some ways like an interface / abstract class, but that too not really.

In particular, you can't have “concrete values of a class”. Classes don't have values, they have instances – but those are types, not values. (These types then may or may not have values – in fact, strictly speaking they don't need to be types at all, just type-level entities.)

What you intend to say with your signature to the initializeState function is “the result is a value of type KMeansState v, where v is some type that is an instance of the Vector class but I don't want to tell you which”. What it actually says is, “for any type v that you pick, provided it is an instance of the Vector class, initializeState is a function that yields a KMeansState v value”. Because of the “for any”, aka “forall” or ∀, we call this a universally quantified type.

The intended type meanwhile is existentially quantified. It's a bit weird why this would be called so; it's a bit more understandable if I phrase it as “the result is a value r for which there exists a type v that has a Vector instance, such that r has the type KMeansState v”.

While Haskell has always had universally quantified types, it doesn't really have existential ones. What you can do is wrap an existential in a custom type:

{-# LANGUAGE GADTs #-}

data SomeVectorMeanState where
  SomeVectorMeanState :: Vector v => KMeansState v -> SomeVectorMeanState

initializeState :: Int -> SomeVectorMeanState
initializeState n = SomeVectorMeanState $ KMeansState test

But this doesn't really accomplish anything useful. In fact, you won't be able to use the vector values in any way whatsoever, because the concrete type isn't known. See https://lukepalmer.wordpress.com/2010/01/24/haskell-antipattern-existential-typeclass/

Instead, as Willem Van Onsem commented, you should probably just use

initializeState :: Int -> KMeansState (Double,Double)

or, if you don't want to make it so obvious that the vector type is (Double,Double), you can wrap it in a type or newtype.

How do I give a concrete value to a Haskell instance?

1 Answers