尝试将类型关系 [(a,b)] 定义为类别 class 的实例时出错

Question

我正在探索 AxB 的 R 子集的一些可能实现，每个都有其限制和可能性。我还想在可能的情况下将它们定义为类别 class 或 Semigroupoid class.

的实例

我选择了对的列表，因为关于组合列表的操作，它仅将对的元素的类型置于作为 Eq class.[=12 实例的约束条件下。 =]

现在我卡在这个编译器错误消息上："No instance for (Eq a) arising from a use of ‘°’"

怎么了？

{-# LANGUAGE GADTs #-}

module RelationT where

import Data.List
import Control.Category as Cat

data RelationT a b where
  Id :: RelationT a a
  RT :: (Eq a, Eq b) => [(a,b)] -> RelationT a b

instance Category RelationT where
  id = Id
  Id . r = r
  r . Id = r
  r1 . r2 = r1 ° r2 -- error:  No instance for (Eq a) arising from a use of ‘°’

(°) :: (Eq a, Eq b, Eq t) => RelationT t b -> RelationT a t -> RelationT a b
RT r1 ° RT r2 = RT $ nub $ go r1 r2
    where
    go [] r =  []
    go r [] =  []
    go xys2 ( ((x1,y1): xys1)) =  go2 x1 y1 xys2 [] ++ go xys2  xys1
        where
        go2 x y [] acc = acc
        go2 x y ((w,z):wzs) acc
          | y == w = go2 x y wzs ((x,z):acc)
          | otherwise = go2 x y wzs acc

-- ex. RT [(1,'a'),(4,'b'),(5,'c'),(10,'d')] ° RT [(3,10),(1,5),(1,1)]
-- > RT [(3,'d'),(1,'c'),(1,'a')]

Answer 1

如果您将 Eq 约束存储在 GADT 中，则无需从签名中要求：通过 pattern-matching 在 relation-values 上，约束已经是在适用范围。所以，只需将签名更改为

(°) :: RelationT t b -> RelationT a t -> RelationT a b

(Eq a, Eq b, Eq c) 信息将仍然在函数体内可用，因为您有 pattern-matched RT r1 和 RT r2 在那里，如果成功证明所有类型都有一个 Eq 实例。

就是说：根据我的经验，当您想对您的类别做更多涉及的事情时，这种在 GADT 中存储约束的技巧很快就会遇到麻烦。问题是，标准 Category class 并不真正适合这样的关系类型，因为它只支持与 Hask 具有完全相同对象的类别– 即所有 Haskell 类型。但是您的关系类别实际上只有 equality-comparable 类型作为对象；使用额外的 Id 构造函数，您强行将其扩展为还包括 non-eq 类型之间的关系，但是只有身份关系可用...这很重要一个脆弱的黑客。

正确的出路是使用类型class，它允许类别开始时具有更受限制的对象概念。最简单的方法是 约束种类。来自我的 constrained-categories package:

{-# LANGUAGE TypeFamilies, ConstraintKinds #-}
import GHC.Exts (Constraint)

class Category k where
  type Object k o :: Constraint
  id :: Object k a => k a a
  (.) :: (Object k a, Object k b, Object k c)
         => k b c -> k a b -> k a c

然后就可以制作实例了[=23=]

data RelationT a b where
  Id :: RelationT a a
  RT :: [(a,b)] -> RelationT a b

instance Category RelationT where
  type Object RelationT o = Eq o
  id = Id
  (.) = (°)

尝试将类型关系 [(a,b)] 定义为类别 class 的实例时出错

Error trying to define type Relation [(a,b)] as an instance of Category class

haskell

category-abstractions