难以将关系类型定义为类别的实例 class

Question

我正在尝试将 Relation a b 定义为 Category 实例。在我看来，作曲家运算符定义明确并且遵守结合律。说到id，我找不到一个正确的定义。我做错了什么？

import Data.Map as M
import Data.Set as S
import Control.Category as Cat

newtype Relation a b = R (Map a (Set b)) deriving (Show, Eq)

-- instance Cat.Category Relation where
    -- id = 
    -- (.) = (°)

-- GHC.Base.id r1
-- > R (fromList [(10,fromList "abef"),(30,fromList "GRTXa")])

r1 = R $ M.fromList [(10,S.fromList "abfe"),(30,S.fromList "aXGRT")]
r2 = R $ M.fromList [('a',S.fromList [Just "Apple",Just "Ask"]),('b',S.fromList [Just "book",Just "brother"]),('T',S.fromList [Just "Table"]),('?',S.fromList [Just "Apple",Just "brother"])]

-- ex. r1 ° r2 = R (fromList [(10,fromList [Just "Apple",Just "Ask",Just "book",Just "brother"]),(30,fromList [Just "Apple",Just "Ask",Just "Table"])])


(°) :: (Ord a, Ord k, Ord b) => Relation a k -> Relation k b -> Relation a b   
R mp1 ° R mp2
  | M.null mp1 || M.null mp2 = R M.empty 
  | otherwise = R $ M.foldrWithKey (\k s acc -> M.insert k (S.foldr (\x acc2 -> case M.lookup x mp2 of
                                                                                  Nothing -> acc2
                                                                                  Just s2 -> S.union s2 acc2
                                                                    ) S.empty s) acc
                                   ) M.empty mp1

Answer 1

Relation 不能是 Category:

的实例

正如luqui在评论中指出的那样，Relation仅表示有限关系（当视为成对集合时），但无限集合上的恒等关系是无限的；
组合并未在所有类型上定义，仅在 Ord.

这是解决这些问题并使 Relation 成为 Category 实例的一种方法：

添加一个普通元素来表示身份关系（这与使用 Option 从半群中创建幺半群的想法相同）；
使其他 "nontrivial" 关系承载 Ord 个实例。

这可以使用 GADT 来完成。

{-# LANGUAGE GADTs #-}

data Relation a b where
  Id :: Relation a a
  R :: (Ord a, Ord b) => Map a (Set b) -> Relation a b

instance Category Relation where
  id = Id
  Id . r = r
  r . Id = r
  R r1 . R r2 = ...

难以将关系类型定义为类别的实例 class

Difficulty in defining the Relation type as an instance of the Category class

haskell

category-abstractions