Why can't ghc match these types on this Category product?

Question

I have a pretty typical definition of a category as such:

class Category (cat :: k -> k -> Type) where
  id :: cat a a
  (.) :: cat a b -> cat c a -> cat c b

Now I would like to make the Product Category so I made this GADT

data ProductCategory
  (cat1 :: a -> a -> Type)
  (cat2 :: b -> b -> Type)
  (x :: (a, b))
  (y :: (a, b))
  where
MorphismProduct :: cat1 x x -> cat2 y y -> ProductCategory cat1 cat2 '(x, y) '(x, y)

Now this compiles nicely, my issue arrives when I try to make this an instance of Category. The math here is really easy, it seems like this should be a simple instance. So here is what I come up with:

instance
  ( Category cat1
  , Category cat2
  )
    => Category (ProductCategory cat1 cat2)
  where
    id = MorphismProduct id id
    (MorphismProduct f1 f2) . (MorphismProduct g1 g2) = MorphismProduct (f1 . g1) (f2 . g2)

But this comes up with an error:

    • Couldn't match type ‘a2’ with ‘'(x0, y0)’
      ‘a2’ is a rigid type variable bound by
        the type signature for:
          id :: forall (a2 :: (a1, b1)). ProductCategory cat1 cat2 a2 a2
        at src/Galaxy/Brain/Prelude.hs:175:5-6
      Expected type: ProductCategory cat1 cat2 a2 a2
        Actual type: ProductCategory cat1 cat2 '(x0, y0) '(x0, y0)
    • In the expression: MorphismProduct id id
      In an equation for ‘id’: id = MorphismProduct id id
      In the instance declaration for
        ‘Category (ProductCategory cat1 cat2)’
    • Relevant bindings include
        id :: ProductCategory cat1 cat2 a2 a2
          (bound at src/Galaxy/Brain/Prelude.hs:175:5)
    |
175 |     id = MorphismProduct id id
    |          ^^^^^^^^^^^^^^^^^^^^^

I've spent a long while on this error and I just don't know what it is trying to communicate to me. It claims that it can't match a to '(x0, y0) but I have no idea why, it seems like it really should be able to.

What is the issue that is being encountered here? How to fix it would be nice but I would really like to know how to read this message.

Answer 1

id should have type forall a. MyCat a a but in this case you can only construct forall x y. MyCat '(x, y) '(x, y). Generalizing that further requires the assumption that all pairs a :: (t1, t2) are of the form a = '(x, y), which is not provable in Haskell.

One workaround is to not use a GADT; in particular, don't refine the type parameters in the constructor. Instead of this:

data ProductCategory cat1 cat2 a b where
  Pair :: cat1 x x' -> cat2 y y' -> ProductCategory cat1 cat2 '(x, y) '(x', y')

do this:

data ProductCategory cat1 cat2 a b where
  Pair :: cat1 (Fst a) (Fst b) -> cat2 (Snd a) (Snd b) -> ProductCategory cat1 cat2 a b

type family Fst (a :: (k1, k2)) :: k1 where Fst '(x, y) = x
type family Snd (a :: (k1, k2)) :: k2 where Snd '(x, y) = y

Note that definition of ProductCategory is equivalent to this, without GADT syntax:

data ProductCategory cat1 cat2 a b
  = ProductCategory (cat1 (Fst a) (Fst b)) (cat2 (Snd a) (Snd b))