haskell - 为什么 ghc 不能在这个 Category 产品上匹配这些类型？

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))