Как соотносятся ункарри и фанин в теории категорий?

В библиотеке, которую я пишу, мне показалось элегантным написать класс, похожий (но немного более общий), чем следующий, который сочетает в себе как обычные uncurry над продуктами, так и функцию fanin (из здесь или здесь, если хотите):

{-# LANGUAGE TypeOperators, TypeFamilies,MultiParamTypeClasses, FlexibleInstances #-}
import Prelude hiding(uncurry)
import qualified Prelude 

class Uncurry t r where
    type t :->-> r
    uncurry :: (t :->-> r) -> t -> r

instance Uncurry () r where
    type () :->-> r = r
    uncurry = const

instance Uncurry (a,b) r where
    type (a,b) :->-> r = a -> b -> r
    uncurry = Prelude.uncurry

instance (Uncurry b c, Uncurry a c)=> Uncurry (Either a b) c where
    type Either a b :->-> c = (a :->-> c, b :->-> c)
    uncurry (f,g) = either (uncurry f) (uncurry g)

Обычно я просматриваю пакет categories Эдварда Кметта (ссылка выше), чтобы разобраться в подобных вещах, но в этом пакете fanin и uncurry разделены на классы CoCartesian и CCC соответственно.

Я немного читал о BiCCC, но еще не совсем в них разобрался.

Мои вопросы

  1. Оправдана ли приведенная выше абстракция каким-то образом косым взглядом на теорию категорий?

  2. Если да, то каким будет правильный язык, основанный на CT, для разговора о классе и его экземплярах?


EDIT: если это поможет, а приведенное выше упрощение искажает вещи: в моем реальном приложении я работаю с вложенными продуктами и сопутствующими продуктами, например. (1,(2,(3,()))). Вот реальный код (хотя по скучным причинам последний экземпляр упрощен и не работает сам по себе, как написано)

instance Uncurry () r where
    type () :->-> r = r
    uncurry = const

instance (Uncurry bs r)=> Uncurry (a,bs) r where
    type (a,bs) :->-> r = a -> bs :->-> r
    uncurry f = Prelude.uncurry (uncurry . f)

-- Not quite correct
instance (Uncurry bs c, Uncurry a c)=> Uncurry (Either a bs) c where
    type Either a bs :->-> c = (a :->-> c, bs :->-> c)
    uncurry (f,fs) = either (uncurry f) (uncurry fs) -- or as Sassa NF points out:
                                                     -- uncurry (|||)

Таким образом, экземпляр const для экземпляра () появился естественным образом как рекурсивный базовый случай для экземпляра n-арного кортежа uncurry, но наблюдение всех трех вместе выглядело как... что-то непроизвольное.


Обновить

Я обнаружил, что мышление с точки зрения алгебраических операций, а.ля Крис Тейлор types/" rel="nofollow noreferrer">блоги об "алгебре АТД". Это прояснило, что мой класс и методы на самом деле были просто законами экспоненты (и причиной, по которой мой последний экземпляр был неправильным).

Вы можете увидеть результат в моем пакете shapely-data, в Exponent и Base; см. также исходный код для заметок и ненавязчивой разметки документа.


person jberryman    schedule 09.10.2013    source источник


Ответы (1)


Ваш последний экземпляр Uncurry - это именно uncurry (|||), поэтому в нем нет ничего "более общего".

Карри находит для любой стрелки f: ABC стрелку curryf: ACB, такую, что единственная стрелка eval: CBBC коммутирует. Вы можете просмотреть eval как ($). Выражение «CCC» является сокращением для «в этой категории у нас есть все продукты, все экспоненты и терминальный объект» — другими словами, каррирование работает для любой пары типов и любой функции в Haskell. Одним из важных следствий CCC является то, что A=1A=A1 (или a изоморфен (a,()) и изоморфен ((),a)).

Uncurry в haskell — это противоположное обозначение одного и того же процесса. Начнем со стрелки f=uncurryg. Каждая пара имеет две проекции, поэтому сочетание proj1 и curryf=g дает CB. Поскольку мы говорим о составе и продуктах, отмена каррирования в CCC определяет уникальный uncurryg для любого g: ACB. В CCC у нас есть все продукты, поэтому у нас есть CBB, который можно оценить до C.

В частности, вспомним A=A1. Это означает, что любая функция AB также является функцией A1B. Вы также можете рассматривать это как «для любой функции AB существует функция A1B», доказанную тривиальным uncurrying, из которых ваш первый экземпляр делает только половину (доказывает это только для id).

Я бы не назвал последний экземпляр «некарри» в том же смысле, что и каррирование. Последний пример — это конструкция определения копроизведения — для любой пары стрелок f: AC и g: BC существует единственная стрелка [f,g]: (A+B)C. В этом смысле это выглядит как злоупотребление интерфейсом - это обобщение значения от "uncurry" до "учитывая что-то, дайте мне что-то" или "истинное соответствие между :->-> и функциями haskell". Возможно, вы могли бы переименовать класс в Arrow.

person Sassa NF    schedule 09.10.2013
comment
Большое спасибо. В моем реальном приложении я имею дело с вложенными кортежами и продуктами, например. (1,(2,(3,()))), откуда берется экземпляр () (и это то, что я имел в виду, когда говорил более общее). Я собираюсь отредактировать свой ответ, добавив в него реальную проблему, и мне бы очень хотелось, чтобы вы взглянули и узнали, есть ли у вас какие-либо дополнительные сведения. - person jberryman; 09.10.2013
comment
@jberryman Ваше редактирование выглядит так, как будто оно нуждается в хаке. haskell.org/package/recursion-schemes-2.0/docs/. data PP a b = PP a b deriving (Functor); type P a = Fix (PP a) - теперь P a является вложенным кортежем. Я не уверен, как заставить это работать с (,) вместо PP. - person Sassa NF; 09.10.2013
comment
@jberryman, тогда ваши два экземпляра определяют алгебру для функтора F(X)=1+AX - путем определения 1->X и AX->X - person Sassa NF; 09.10.2013
comment
Спасибо, похоже, что пакет recursion-schemes мне будет полезно понять. Что я на самом деле делаю, так это определяю тип одноэлементного попутного продукта, который используется в качестве базового случая для рекурсивных вложенных экземпляров Both. - person jberryman; 09.10.2013
comment
Также я думаю, что интересно, что с моей рекурсивной версией (из EDIT) мы получаем: (a -> r) -> ((a,()) -> r) - person jberryman; 09.10.2013
comment
@jberryman type RecursiveNestedEither a = Fix (Either a) - полезно для совместной рекурсии. - person Sassa NF; 09.10.2013