为什么 ghc 无法在该类别产品上匹配这些类型？

Question

我有一个非常典型的类别定义：

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

现在我想做 Product Category 所以我做了这个 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)

现在可以很好地编译了，当我尝试将其作为 Category 的实例时，我的问题来了。这里的数学真的很简单，看起来这应该是一个简单的例子。所以这就是我想出的：

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)

但这会出现错误：

    • 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
    |          ^^^^^^^^^^^^^^^^^^^^^

我在这个错误上花了很长时间，但我只是不知道它试图与我交流什么。它声称它不能匹配 a 到 '(x0, y0) 但我不知道为什么，它似乎真的应该能够匹配。

这里遇到的问题是什么？如何修复它会很好，但我真的很想知道如何阅读此消息。

Answer 1

id 应该有类型 forall a. MyCat a a 但在这种情况下你只能构造 forall x y. MyCat '(x, y) '(x, y)。推广进一步需要假设所有对 a :: (t1, t2) 都是 a = '(x, y) 的形式，这在 Haskell.

中是不可证明的

一种解决方法是不使用 GADT；特别是，不要在构造函数中细化类型参数。而不是这个：

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

这样做：

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

注意 ProductCategory 的定义等价于此，没有 GADT 语法：

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

为什么 ghc 无法在该类别产品上匹配这些类型？

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

haskell

typeclass

category-theory

gadt