Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 16
Прочитав эту статью я перестал понимать теорию категорий, спасибо.
по каждому морфизму f однозначно определяются такие X, Y ∈ Ob(C), что множества Homc(X, Y) не пересекаются. То есть между элементами X и Y существует единственная связь f
Чего чего!? Что это за такое странное условие? Это в учебнике Ершова так написано?
До фразы "То есть..." взято из учебника, да. Кстати заметила, действительно, начиная с "То есть.." фраза звучит кривовато, это уберу.
В таком случае вы наверное уже понимаете, что пример 2 решен вами неправильно. Ответ правильный, но ход решения нет.
Решение должно быть такое: по определению композиции для любой композиции стрелок существует какая то стрелка равная этой самой композиции. Т.е. существует стрелка g°f из A в A. Согласно рисунку единственная стрелка из A в A это idA значит g°f=idA. Те же рассуждения верны и для f°h=idB. Рассмотрим композицию трёх стрелок g°f°h=g°(f°h)=(g°f)°h т.к. композиция ассоциативна. Значит g°idB=idA°h откуда следует что g=h т.е. это не 2 разные, а одна и та же стрелка.
Ну да, про f и g неверно, но условие про тождественный морфизм - есть аксиома, что он определяется однозначно - все еще имеет смысл. Спасибо за замечание, помогло развеять мое неверное представление)
есть аксиома, что он определяется однозначно
Полагаю, речь о том, что id(A) единственен.
Возьмите такой моноид (категорию с единственным объектом): объект, - конечное множество, морфизмы - все перестановки его элементов. Id - тождественная перестановка, получается композицией любой перестановки с обратной к ней.
На самом деле, прекрасно вас понимаю, теоркат он такой, провоцирует на неправильное прочтение с далеко идущими последствиями.
Спасибо. Ничо не понятно
Покажите, пожалуйста, пример, как с помощью теории категорий можно что-то вычислить. Например, с помощью теории групп можно вычислить очень много полезного. Например, группы Ли применяются в прикладной физике. Ну и уж куда там, матрицы и AI из них, топологические аргументы там же и т.д. SQL это тоже своего рода вполне алгебра. Криптография так же пользуется именно теорией групп! Про теорию категорий пытаюсь смотреть лет 15 и не видел ни разу примера, где бы она давала какой-то вычислительный инструмент. Только самомозерцание её собой я вижу. Подскажете примеры?
Теория категорий действительно ничего не дает науке в плане новых результатов. Однако она показывает общую картину обобщения: будь то категория групп, алгебр или топологий. В общем для понимания единого и прекрасного ))
По моему опыту ТК хорошо показывает себя в программировании в двух основных случаях:
(исследование) когда надо хорошо отработанную концептуальную систему перенести на другую область. Скажем, представления групп является частный случаем общего категорного метода, который подобные приёмы позволяет штамповать массово.
В частности, это позволяет оперировать известными понятиями и аналогиями (пространство, отображение, подпространство, произведение) без уточнения конкретики. Например,
в физике мы можем долго говорить о периодичной волновой функции и порождаемом ей расслоении на зоне Бриллюэна без уточнения, считаем ли мы её гладкой или дважды гладкой: в каждом случае мы просто говорим, что все упомянутые в рассуждении функции будут такими, какими мы хотим. Рассуждения становятся короткими, вся математическая лабуда про гладкость не упоминается, а выкладки не перестают быть формальными. При этом по рассуждениям чётко видно, какие минимальные требования на гладкость накладываются.
В программировании ТК позволяет нам корректно говорить о тех функциях, которыми мы программируем. Ведь если говорить по-честному, то, что мы привыкли называть функциями в программировании, имеет мало что общего с функциями в классической математике: 1) первые могут зацикливаться, а вторые всегда что-то возвращают; 2) первые с необходимостью задают алгоритм вычисления (даже в декларативных языках), вторые — нет; 3) первые имеют нефункциональные характеристики (затраты по времени и памяти), вторые — нет; 4) недетерминизм, работа с состоянием и прочие прелести во всех ЯП, кроме чистых функциональных.
Тем не менее на практике мы склонные отождествлять эти понятия в одних случаях, и различать только тогда, когда вышеприведённые особенности проявляются. ТК легализует подобную (якобы) демагогию, переводя в статус аккуратно формализованной теории.
(обучение) когда надо спроектировать API, чтобы он воспринимался как естественный интерфейс. SQL тем хорош, что основывается на реляционном исчислении и реляционной алгебре: первое даёт метод решения широкого класса задач, выражаемых на языке первого порядка; второй позволяет быстро оценить, какие запросы эквивалентны. Обычно интерфейс, основанный на алгебраической системе, ощущается как более простой и обоснованный по сравнению с тем, который делает по велению левой пятки. ТК позволяет обобщить это на тот класс систем, API к которым в принципе не может выражаться простой алгебраической системой. В частности, ТК формализует рад полезных понятий:
функтор («структура данных», …)
естественное преобразование
терминальный и инициальный объекты (обычно имеют свои названия в разных предметных областях, вроде «атомарный X» или «пустой X»)
произведение и сумма
изоморфизм («равный с точностью до того, что нам не интересно»)
подобъект (подпространство, под-что-угодно)
универсальность (свободный функтор, сопряжения и т.п.)
Если проектируешь API и сумел достичь того, что большинство структур данных — функторы; большинство функций являются естественными преобразованиями; большинство объектов, с которыми пользователь будет работать, можно собрать из произведений, сумм, терминальных и инициальных объектов; все или почти все функции «уважают» изоморфизмы; все требования состоят в коммутативности некоторых диаграмм, — если всё это есть, то, вероятно, это прекрасный API, который не подложит свинью в неожиданный момент. Пользователь будет воспринимать этот интерфейс как естественный и, в идеале, как единственно возможный и обоснованный.
Я написал «по-маркетологски», но идея тут простая: API должен быть простым и обоснованным. Алгебры — это просто и обоснованно. Категории — это (для пользователя) просто и обоснованно. Для разработчика категории сложнее, ибо теория серьёзнее, но универсальнее.
А чисто посчитать что-то категории не нужны. Подобно типизации и тестированию, ТК не нужен, чтобы собственно считать, но занимают определённое место в проектировании и сопровождении программного продукта.
Ладно вычисления. С ними понятно, что ТК неприменима. НО хоть какой-то ПРАКТИЧЕСКИЙ пример можно же? С теми же ранее упомянутыми @youngmysteriouslight API. Чтоб пример был необязательно архитектурно сложным, но демонстративным. Ну нет у меня абстрактного мышления. И даже не понятно с чего начинать его развивать. Вот "на спичках" - по мне так самое оно.
Практических примеров навалом даже здесь на Хабре. Только они конкретные, без лишних абстракций, а потому, прочитав их, можно не узнать ТК.
Умозрительный пример. Допустим, мы разрабатываем собственную систему прав для авторизованного доступа пользователей к ресурсам. Мы решаем, что у каждого пользователя есть какая-то назначенная метаинформация о его правах (тип U), и у каждого ресурса есть то же самое (тип R). С точки зрения ресурса все пользователи делятся на две группы (кто имеет право или нет).
На U можно ввести порядок: для некоторых u1, u2 можно сказать, что всё, что разрешено u1, разрешено и u2. Это категория. Возникают автоматически два крайних режима: «всё запрещено» и «всё разрешено» — инициальный и терминальный объекты. Возникают автоматически операции над правами: если u и v — два возможных набора прав, то u×v — их пересечение (можно только то, что позволяют u и v одновременно), и u+v — объединение (можно то, что позволяет u, и то, что позволяет v).
А потом мы решаем учесть, что права пользователя не навсегда дают доступ, но к некоторым ресурсам требуется дополнительно ввести пароль, а к некоторым — код из СМС. Меняем категорию: теперь морфизмы несут информацию о дополнительных действиях, факт осуществления которых на время изменяет права. Кстати, процедура авторизации может быть представлена морфизмом из инициального объекта («всё запрещено») в получаемые права u. Теперь в категории между двумя объектами может быть несколько морфизмов (напр., повышение прав за счёт ввода пароль или кода из СМС). Композицию тоже можно сделать нетривиальной, чтобы отразить логику работы с паролями. Теперь прямое произведение u×v не только гарантирует, что разрешено только то, что u и v разрешают одновременно, но и гарантируется, что обретение таких прав требует «разумного» (с точки зрения выбранной категории) сочетания действий, необходимых для обретения прав u и v.
Спасибо, но все-равно не понятно. В конкретике: теория начинается с опредленеия категории, а также класса и функтора. Хочется провести красивые соответствия, а их не получается как-раз.
Имеено об этом разрыве я и написал. Т.е. есть стройная теория. И есть практика, в которой все решаю, используя два метода: "вроде можно назвать категорией" и "выступающие части допиливаем по месту". А хотелось бы, когда есть теоретическая часть, например (руководствуясь Вашим примером о правах):
Определим катеогрию "право", которая содержит класс "пользователи" и класс "программы", определим соответсвующие права через функторы... Далее определим категорию "система", содержащую классы "программы" с фукторами "разрешения". Пересечение категорий "право". Рассмотрим взаимоотношение категорий через взаимоотношение их элеменов...
На этом все, уже запутался. Я вот о каком способе изложения написал. Потому как практика применения тех же групп прав большая, но (еесли честно) большая часть на интуиции и не формализуется. В ТК я увидел способ это формализовать. И это касается не только прав, как в Вашем примере.
В целом, сложно будет из-за разрыва в степени абстракции. Но давайте такой пример рассмотрим. Сразу предупреждаю, что в нём категория будет работать как обычное отношение порядка.
Пусть R — множество всех ресурсов (имён файлов, node id и т.п.), которые потенциально могут существовать. Построим категорию порядка Ord(R), где объекты A — это какие-то множества каких-то ресурсов из R (A — подмножество R), морфизм f: A → A' — это пара (A,A'), в которой A — подмножество A'. Композиция тривиальная. Исследуем эту категорию:
терминальный объект — это R,
инициальный — пустое множество,
произведение — это пересечение,
сумма — объединение.
Теперь пусть G — множество всех групп, к которым может принадлежать ресурс. Построим такую же категорию Ord(G), в которой объекты U — это множества некоторых групп, морфизмы — это (U,U'), что U < U'. Композиция тривиальна. Рассмотрим любой функтор F: Ord(G) → Ord(R). Функториальность гласит: если множество групп U входит во множество групп U', то соответствующее ей множество ресурсов F(U) будет входить как подмножество в F(U'), что полностью соответствует нашей интуиции: чем больше групп пользователю даны, тем больше ресурсов ему доступно. В общем случае не следует считать, что F(U + U') = F(U) + F(U'), но всегда F(U + U') включает в себя F(U) + F(U'), это доказывается непосредственно по определению суммы F(U) + F(U').
Итак, мы рассмотрели две категории порядка, одна из которых формализует «множество доступных ресурсов», а другая — «множество групп, на которые абстрактный пользователь имеет права», рассмотрели простейшие пределы в этих категориях. Любой функтор между ними устанавливает соответствие — интерпретацию групп и их сочетаний как множество ресурсов. Функториальность интерпретируется как требование, чтобы реализуемая политика доступа увеличивала (не уменьшала) множество доступных ресурсов при увеличении прав.
Пример понятен?
вроде можно назвать категорией
Понятие категории настолько пермиссивное, что всегда (с точностью до погрешности) слово «вроде» можно убрать: если что-то похоже на категорию, то оно является категорией. Другой вопрос — какие там морфизмы и композиция, они самые важные, в них проявляются все категорные свойства.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Теория категорий для самых маленьких. Введение