Сложность определения типа Relation как экземпляра класса Category

Я пытаюсь определить отношение 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

Я должен быть { (a,a) | a in A }. Поскольку ваша модель отношения является конечной картой, вы можете сделать это только в том случае, если A конечно.

luqui 20.05.2019 20:43

Несвязанный вопрос: зачем импортировать GHC.Base?

Li-yao Xia 20.05.2019 20:51

@Li-yaoXia В других определениях экземпляров категории я видел такое определение идентификатора. Кроме того, очевидно, что он работает сам по себе; то есть GHC.Base.id R mp == R mp, что, на мой взгляд, показывает, что отношение идентичности существует на R.

Alberto Capitani 20.05.2019 20:55

@luqui Итак, вы думаете, что я должен определить R как простой набор (a, b)? Итак, как следует определять «id» в этом случае? (Композиция отношения как множества пар кажется мне простой.)

Alberto Capitani 20.05.2019 20:58

@AlbertoCapitani Нет, Set (a,b) все еще должен быть конечным. На самом деле я бы выбрал что-то вроде a -> Set b («локально конечное») или, может быть, даже a -> b -> Bool

luqui 20.05.2019 21:02

@luqio Может быть, как характеристическая функция над отношением, которое составляется с другим, если первое дает true, а второй аргумент находится в домене второй функции?

Alberto Capitani 20.05.2019 21:10

Я не понимаю объяснения по поводу GHC.Base. Насколько я могу судить, это внутренняя библиотека, которая не предназначена для использования. Это определенно не имеет ничего общего с пользовательскими экземплярами Category.

Li-yao Xia 20.05.2019 21:13

@Li-yaoXia Это было лишь предварительное решение. Теперь, после ваших объяснений, кажется мало смысла.

Alberto Capitani 20.05.2019 21:15
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
3
8
109
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Relation не может быть экземпляром Category:

  1. как Луки указывает в комментариях, Relation представляет только конечные отношения (если рассматривать их как наборы пар), но отношение тождества на бесконечном множестве бесконечно;

  2. композиция определена не для всех типов, а только для экземпляров Ord.

Вот один из способов решить эти проблемы и сделать Relation экземпляром Category:

  1. добавить тривиальный элемент для представления отношения тождества (это та же идея, что и при создании моноида из полугруппы с помощью Option);
  2. заставить другие «нетривиальные» отношения нести экземпляры 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 = ...

Другие вопросы по теме