Я пытаюсь определить отношение a b как экземпляр категории. Мне кажется, что оператор композитора хорошо определен и соблюдает закон ассоциативности. Когда дело доходит до идентификатора, я не могу найти правильное определение. Что я делаю неправильно?
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
Несвязанный вопрос: зачем импортировать GHC.Base
?
@Li-yaoXia В других определениях экземпляров категории я видел такое определение идентификатора. Кроме того, очевидно, что он работает сам по себе; то есть GHC.Base.id R mp == R mp, что, на мой взгляд, показывает, что отношение идентичности существует на R.
@luqui Итак, вы думаете, что я должен определить R как простой набор (a, b)? Итак, как следует определять «id» в этом случае? (Композиция отношения как множества пар кажется мне простой.)
@AlbertoCapitani Нет, Set (a,b)
все еще должен быть конечным. На самом деле я бы выбрал что-то вроде a -> Set b
(«локально конечное») или, может быть, даже a -> b -> Bool
@luqio Может быть, как характеристическая функция над отношением, которое составляется с другим, если первое дает true, а второй аргумент находится в домене второй функции?
Я не понимаю объяснения по поводу GHC.Base. Насколько я могу судить, это внутренняя библиотека, которая не предназначена для использования. Это определенно не имеет ничего общего с пользовательскими экземплярами Category
.
@Li-yaoXia Это было лишь предварительное решение. Теперь, после ваших объяснений, кажется мало смысла.
Relation
не может быть экземпляром Category
:
как Луки указывает в комментариях, Relation
представляет только конечные отношения (если рассматривать их как наборы пар), но отношение тождества на бесконечном множестве бесконечно;
композиция определена не для всех типов, а только для экземпляров Ord
.
Вот один из способов решить эти проблемы и сделать Relation
экземпляром Category
:
Option
);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 = ...
Я должен быть
{ (a,a) | a in A }
. Поскольку ваша модель отношения является конечной картой, вы можете сделать это только в том случае, если A конечно.