Why does GHC say that these two types are different? How can I get them to be the same?

Question

I have defined a class:

class Query a where
  filter  :: a -> (b -> Bool) -> [b]
  ifilter :: a -> (b -> Bool) -> [(b, Int64)]

And I have a user defined type:

data Segment a = Segment {
  extents :: [Extent],
  array   :: [a]
} deriving(Eq, Show)

Finally, I have tried to make Segment an instance of Query:

instance Query (Segment a) where
  filter  = filterSegment
  ifilter = ifilterSegment

The functions filter and ifilter both take a (Segment a) and a function (a->Bool) and return either [a] or [(a,Int64)].

However, I get the following errors:

Couldn't match type `a' with `b'
      `a' is a rigid type variable bound by
          the instance declaration at src/Store/DataColumn.hs:19:10
      `b' is a rigid type variable bound by
          the type signature for filter :: Segment a -> (b -> Bool) -> [b]
          at src/Store/DataColumn.hs:20:3
    Expected type: Segment a -> (b -> Bool) -> [b]
      Actual type: Segment a -> (a -> Bool) -> [a]
    In the expression: filterSegment
    In an equation for `filter': filter = filterSegment
    In the instance declaration for `Query (Segment a)'

Couldn't match type `a' with `b'
      `a' is a rigid type variable bound by
          the instance declaration at src/Store/DataColumn.hs:19:10
      `b' is a rigid type variable bound by
          the type signature for
            ifilter :: Segment a -> (b -> Bool) -> [(b, Int64)]
          at src/Store/DataColumn.hs:21:3
    Expected type: Segment a -> (b -> Bool) -> [(b, Int64)]
      Actual type: Segment a -> (a -> Bool) -> [(a, Int64)]
    In the expression: ifilterSegment
    In an equation for `ifilter': ifilter = ifilterSegment
    In the instance declaration for `Query (Segment a)'

I'm not really sure what I'm missing here. I do want the 'a' from (Segment a) to be same 'a' in (a->Bool), [a], and [(a, Int64)]. However, I can't figure out how to do that. Any help would be appreciated.

Answer 1

Your definition of the type class makes no restrictions on what b can be, meaning that the user should be allowed to pick any type for b he wants. Of course your instance definition does not allow that, which is why it is rejected.

What you want to say is "a is parametrized over a type b, and that's the type b that I want to use". And here's how you say that:

class Query a where
  filter  :: a b -> (b -> Bool) -> [b]

And then you write instance Query Segment rather than instance Query (Segment t) because the a in the type class definition now just stands for Segment and the b stands for t.