рисуем монаду

[thedeemon]

Сегодня в нашем кружке "теоркат для самых маленьких" урок рисования. Будем рисовать монаду. (А то весной кое-кто писал "если монаду нельзя нарисовать, то её нет".)

Для начала нарисуем что-нибудь совсем простое. Палка, палка, огуречик - получился моноид. Моноид состоит из множества (вообще-то необязательно, может быть и штука побольше чем множество), бинарной ассоциативной операции на нем и выделенного элемента, называемого единицей. Бинарная операция берет любые два элемента из этого множества и выдает какой-нибудь один элемент оттуда же.

Она должна быть ассоциативной, т.е. (a*b)*c = a*(b*c):

Тут мы используем нечто вроде фейнмановских диаграмм, где время на рисунке идет снизу-вверх. В самом низу - что было, в самом верху - что получилось, в середине всякие превращения.
Единица моноида - это такой элемент, на который если умножать что угодно слева или справа, получится то, что умножали:

Примеры моноидов: (целые числа, умножение, 1), (целые числа, сложение, 0), (строки, конкатенация, ""), (натуральные числа, максимум, 0) и т.д.

Категория состоит из набора объектов и набора стрелок между ними, функтор отображает одну категорию в другую, сохраняя рисунок стрелок. Если функторы F и G оба отображают категорию C в категорию D, бывает, что можно построить отображение функтора F в функтор G, тоже сохраняющее структуру, такое отображение h называется естественным преобразованием:


Давайте возьмем этот рисунок и применим двойственность Пуанкаре, где k-мерные штуки превращаются в (n-k)-мерные. Возьмем n=2. Категории C и D были нульмерными точками, станут двумерными фигурами. Функторы были одномерными линиями, такими и останутся. Естественное преобразование было двумерной полосой, станет нульмерной точкой. Получим такой вот рисунок, называемый струнной диаграммой:

В такой диаграмме используется вся площадь рисунка. Функторы теперь изображаются не стрелками, а линиями, по разные стороны от которых находятся заливающие пространство рисунка категории, которые этот функтор отображает одну в другую. Что во что отображается определяется направлением. В данном случае слева-направо, в последующих картинках будет справа-налево. Естественное преобразование из одного функтора в другое стало точкой, их соединяющей. Опять же, что во что отображается показано направлением: снизу-вверх.

Что такое монада? Это, во-первых, эндофунктор, т.е. функтор из одной категории в нее же. Назовем его Т. Во-вторых, это пара естественных преобразований μ (от слова мюльтипликейшн) и эта, как ее, в общем, η. Первое превращает Т*Т в Т, второе 1 (identity functor, отображающий категорию саму в себя вообще без изменений) в Т.

Во всяких хаскелях вместо μ (он же join) используют bind (он же >>=), они друг через друга легко выражаются. η в хаскелях известно под именем return.
Конечно, преобразования это не любые, а подчиняющиеся определенным законам. Которые часто изображают в виде требования коммутирования таких вот диаграмм:

Альтернативные пути из точки А в точку Б на таких диаграммах показывают, какие стрелки и их композиции должны быть равны между собой. Например, тут говорится, что неважно, с какой стороны мы к Т добавляем η-й еще один Т, все равно применение к полученному Т² μ дает тот же самый Т.
В данных диаграммах точки означают эндофункторы, а стрелки - естественные преобразования. Подвергнем их той же процедуре дуализации, получим струнные диаграммы:

Теперь естественные преобразования стали жирными точками, а категории - двумерным пространством. Единичный функтор, ничего не делающий, мы обозначим 1, но линию проводить не будем. А теперь сравните эти рисунки с рисунками про законы моноида. Это абсолютно те же самые рисунки, просто с другими обозначениями! Ибо воистину, монады образуют моноид, у которого "множество" - это "множество" эндофункторов в некоторой категории, умножение - их композиция, а единица - единичный функтор (Identity). (Upd: тут я несколько наврал, см. исправления в комментариях.) Классическая цитата "monads are monoids in the category of endofunctors" имеет довольно простой смысл.

Монаду нарисовали, до перемены еще есть время, давайте нарисуем сопряженные функторы. Пусть у нас есть категории C и D и функторы G : C -> D и F : D -> C (теперь это не обязательно эндофункторы, C и D могут быть реально разными категориями).

При определенных условиях эти два функтора называются сопряженными. Условия эти могут быть сформулированы по-разному, например так. Должны существовать естественные преобразования
ε : FG -> 1,
η : 1 -> GF,
называемые counit и unit, такие, что поочередное их применение в разном порядке эквивалентно identity transformation, т.е. композиция F -> FGF -> F равна id, и G -> GFG -> G тоже. Нарисуем ε и η в виде струнных диаграмм:

и изобразим требования к их композиции в виде равенства диаграмм:


Из этих кирпичиков мы можем сложить рисунок побольше:

Тут GFGF применением ε к средней паре превращается в GF. Если мы обозначим композицию GF как Т, то получим преобразование TT -> T, аналогичное монадному μ.
Теперь построим еще больше картинку, и применим interchange rule, позволяющее двигать части картинки туда-сюда, не нарушая ее структуры. Потянув левую точку слияния вверх, а правую вниз, мы получим картинку, где порядок применения преобразований поменялся, но результат остался тем же.

Фактически, мы получили правило ассоциативности μ для T=GF, в точности как на левой картинке про монадные законы и на картинке про ассоциативность бинарной операции в моноиде.

Теперь построим картинку с использованием η и ε.

Cогласно законам сопряженных функторов, левую загогулину GFG можно выпрямить в одну линию G, тогда получим просто композицию GF, т.е. Т. Аналогично, в симметричной картинке можно выпрямить правую загогулину FGF до просто F, чтобы в итоге получилась та же T = GF. Так мы получили картинку, аналогичную правой части картинки про монадные законы, т.е. выполнение свойств единицы, 1 * Т = Т = Т * 1. Таким образом, композиция GF сопряженных функторов дает нам не просто эндофунктор T, а самую настоящую монаду.

При желании струнные диаграммы расширяются в третье измерение, получаются всякие такие доказательства:



Но об этом я вам не расскажу.

На этом все, всем успехов на приближающемся ICFPC!

Comments

[sassa-nf.livejournal.com]

"Ибо воистину, монады образуют моноид, у которого "множество" - это "множество" эндофункторов в некоторой категории, умножение - их композиция, а единица - единичный функтор (Identity). Классическая цитата "monads are monoids in the category of endofunctors" имеет довольно простой смысл."

А про это ещё раз.

1. Монады образуют моноид (один) или монады образуют моноиды (по одному моноиду на монаду)? (ибо инглиш гласит нам, что моноидов много)

2. А умножение = композиция (произвольных эндофункторов) - это каким образом заслуга монад?

3. Тут как-то ещё не ясно, почему умножение - это композиция, если стрелками в категории эндофункторов являются эта, м...

[valentin budaev (from livejournal.com)]

Автор допустил неточность. В категорных моноидах есть два умножения, первое - это *, в случае множеств это обычное декартово произведение множеств, в случае эндофункторов - композиция эндофункторов. А u - это стрелка u: T*T -> T. если * - декартово произведение, то u - обычная математическая бинарная операция, если * - композиция функторов, то u - конкретное естественное преобразование. При этом требуется, чтобы категория относительно * была аналогом обычного теоретико-множественного моноида, то есть сама * ассоциативна и имеет единицу (множество-синглтон либо тождественный функтор для рассматриваемых случаев), такие категории называются моноидальными (если моноидные законы выполняются с точностью до изоморфизма) и строго моноидальными (если законы выполняются точно).

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

Если это была категория эндофункторов, то каждый такой категорный моноид (тройка (T, u, n)) образует свою монаду (он и называется монадой, по определению).Ну а каждая монада - есть конкретный моноидл, понятное дело.

А образуют монады в целом моноид или нет - вопрос отдельный, если получится выбрать хорошую * - будут образовывать.

[sassa-nf.livejournal.com]

спасибо.

можно ли сказать, что "*" - продукт в категорном смысле, а u - это проекция?

[valentin budaev (from livejournal.com)]

Нет, нельзя. Из A*B вообще может не быть стрелки в A (проекции). И уж точно никто не требует от * универсальности.

[nivanych.livejournal.com]

Это чуть не основная `идеологическая` особенность моноидального произведения общего вида, по сравнению с декартовым — как правило, там нет ничего, похожего проекцию (и правильно выше товарищ напомнил — универсальности тоже нет). Диагональный морфизм A→A⊗A есть, разве что.
Из-за этого, например, групповой объект можно задать только с декартовым произведением. Правда, всегда можно задать моноид Хопфа, но это совсем другая история ;-)

Например, возьмём такую вот строгую моноидальную категорию-предпорядок —
объектами натуральные числа, для a≤b стрелка a→b, тензорным произведением сложение чисел.
Нетрудно убедиться, что это строгая моноидальная категория.
А теперь прошу мне предъявить две проекции из тензорного произведения 3+4 —
3+4→3 и 3+4→4 ;-)
Как устроены эти стрелки?
И кто за всем этим стоит? ;-)

[nivanych.livejournal.com]

Формулировка алгебры языком моноидальных категорий, имхо, это очень красиво.
Помнится, Дмитрий Павлов предлагал линейную алгебру рассказывать языком симметричных (ну и всякоразных) моноидальных категорий.
Надо бы как-то реализовать ;-)

[valentin budaev (from livejournal.com)]

Кстати, а вообще кто-то рассматривал конкретно моноидальные категории с (ко)произведением в качестве _*_? Неужели нету никаких интересных следствий для такого случая?

[nivanych.livejournal.com]

Умножением чисел тоже задаётся моноидальная категория.
(Причём тут коумножение, не понял).
Насколько вижу, "интересные следствия" тут или элементарны или не относятся к именно умножению.
У меня тут интересное ассоциируется с группой Пикара.

[valentin budaev (from livejournal.com)]

Я имел ввиду не числа, а категорное произведение. То есть берем категорию с (ко)произведением и ко(единицей), она естественным образом получается моноидальной, но будут ли какие-то интересные свойства выводиться из того факта, что тензорное произведение = категорному?

[sassa-nf.livejournal.com]

о, классно. за сложением, конечно, коалгебра стоит, если A⊗A является объектом этой же категории. ну и она не инициальная, так что, сумму на проекции не разложить, да.

[nivanych.livejournal.com]

>> И кто за всем этим стоит?
> за сложением, конечно, коалгебра стоит

Я так и знал! Это заговор!! ;-)
Да нет там никакой коалгебры.
Точнее, вполне может быть какая-нибудь
Скажем, диагональная
A → A⊗A := A+A
Но интересного там ничего нет.

[sassa-nf.livejournal.com]

когда говорят "тензорным произведением сложение чисел", имеют ли в виду, что в категории существует объект, представляющий это самое тензорное произведение? А то про бифункторы написано, что он должен быть из product category, а вы пишете о сложении 3+4→7 - дык, 3+4 тоже тут?

[nivanych.livejournal.com]

Тоже тут. И он равен 7.
У нас строгая категория, так что, ассоциатор с левыми-правыми единицами должны быть единичными стрелками.
Мы из чисел 'генерируем' категорию, а не наоборот! ;-)

[sassa-nf.livejournal.com]

Гм. Я чё хочу сказать. Если у нас есть объект 3+4, то тогда есть и стрелка в 7. А раз они равны, то тогда должна быть и стрелка обратно в 3+4 (ибо предпорядок). А если 3+4 - это и есть 7, то что за вопрос про стрелку A⊗A→A? В этой категории вы каждое число отдельным объектом или как? Если все числа - один объект, то тогда A⊗A→A - это id. А если каждое число отдельный объект - то композиция всех ≤ от 6 до 3, допустим.

[nivanych.livejournal.com]

1. В каждой моноидальной категории может быть много моноидов. Это ж стрелка A⊗A→A с ассоциативностью и единицей. Соответственно, в (строгой) моноидальной категории эндофункторов (где в качестве ⊗ выступает композиция функторов) может быть много моноидов. То есть, монада=моноид, правда, в определённой моноидальной категории.
Да, неправильно там написано. В роли "множества" конкретной монады-моноида выступает конкретный выбранный эндофунктор.

2. А где сказано, что это заслуга монад?

3. Ещё можно категорию Cat изобразить, как 2-категорию —
1-стрелки — функторы,
2-стрелки — естественные преобразования.
Соответственно, когда выбираешь какой-то объект и все 1-стрелки вокруг него, то получаешь, что каждую 1-эндострелку можно соединить с каждой.
Нетрудной проверкой убеждаемся, что относительно композиции этих 1-эндострелок, мы получаем строгую моноидальную категорию.
И вообще, любая бикатегория с одним объектом будет моноидальной, если мы композицию 1-стрелок предложим в качестве тензорного произведения в нашей новой моноидальной категории. Ну а 2-стрелки изначальной бикатегории в качестве 1-стрелок новой строящейся моноидальной.

[sassa-nf.livejournal.com]

спасибо. я про μ: AxA→A и η: I→A как моноид читал, и даже кажется понял, а тут - нате; решил уточнить на случай если высказанное автором тоже верно, а я не догоняю.

2. ну, было написано, что "а композиция - это умножение", вот и восстало сознание, что не может такого быть - композиция и I есть всегда, а монада - нет.

3. классное объяснение. Нужно будет про 2-категории почитать ещё раз. А то вопрос какой-то был...

[nivanych.livejournal.com]

Для голову поломать, а потом починить —
For endofunctors of varieties preserving intersections, a new description of the final coalgebra and the initial algebra is presented: the former consists of all well-pointed coalgebras.
These are the pointed coalgebras having no proper subobject and no proper quotient.
The initial algebra consists of all well-pointed coalgebras that are well-founded in the sense of Osius and Taylor.
And initial algebras are precisely the final well-founded coalgebras.
Finally, the initial iterative algebra consists of all finite well-pointed coalgebras.
Numerous examples are discussed e.g. automata, graphs, and labeled transition systems.
http://arxiv.org/abs/1305.0576

[nivanych.livejournal.com]

Нувот кстатте.
Предлагаю немного подумать над тем, почему в моноидальной категории абелевых групп, просто любой морфизм A⊗A→A — это кольцо.
Ну а моноид в этой моноидальной категории, это ассоциативное кольцо с единицей.

[valentin budaev (from livejournal.com)]

> Предлагаю немного подумать над тем, почему в моноидальной категории абелевых групп, просто любой морфизм A⊗A→A — это кольцо.

Потому что забывающий функтор имеет сопряженный, и, соответственно, любая A⊗A→A имеет семантику бинарной операции, согласованной с порождающей категорию структурой?

Собственно, подобное утверждение должно выполняться для всех категорий, которые имеют сохраняющий пределы функтор в некоторую декартово замкнутую категорию. В этом случае мы можем "каррировать" A⊗B→C во внутреннем языке категории, в которую ведет функтор.

[nivanych.livejournal.com]

> забывающий функтор

Из колец в абелевы группы, что ли??
Ну допустим, имеет левый сопряжённый и мы можем сделать своеобразное "свободное кольцо", но как их этого следует то, что _любой_ морфизм A⊗A→A задаёт структуру кольца?

Я предлагал просто рассмотреть тензорное произведение и убедиться, что в данном случае мы получаем, во-первых, бинарную операцию умножения, и во-вторых, она дистрибутивна.

Какие утверждения "подобные", я не понял.
Например, что моноид в моноидальной категории R-модулей задаёт R-алгебру, это подобное утверждение или не очень? ;-)

А про "каррировать", то это ближе к рассуждениям около определения модуля над моноидом в моноидальной категории.

[valentin budaev (from livejournal.com)]

> Из колец в абелевы группы, что ли??

из групп в Set. Нам же каррировать A*A -> A надо.

> но как их этого следует то, что _любой_ морфизм A⊗A→A задаёт структуру кольца?

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

> Я предлагал просто рассмотреть тензорное произведение и убедиться, что в данном случае мы получаем, во-первых, бинарную операцию умножения, и во-вторых, она дистрибутивна.

Ну да. И это все верно для любой категории из которой можно построить нужный функтор.

> Какие утверждения "подобные", я не понял.

Например, в случае топологического пространства любой морфизм A*A -> A будет "непрерывным группоидом" :)

> Например, что моноид в моноидальной категории R-модулей задаёт R-алгебру, это подобное утверждение или не очень?

Ну, видимо, да. Любой морфизм A*A->A тут задает билинейное отображение, то есть делает модуль алгеброй над кольцом.

> А про "каррировать", то это ближе к рассуждениям около определения модуля над моноидом в моноидальной категории.

каррирование требуется, чтобы морфизм имел семантику операции от двух аргументов. Если оно не "каррируется" (хотя бы потенциально, через функтор), то у нас что-то сломается. Грубо говоря такое "потенциальное каррирование" говорит нам, что считать A*B->С функцией от двух элементов осмысленно. И даже предоставляет некоторый конструктивный способ это делать :)

[nivanych.livejournal.com]

В ходе одного обсуждения, родилась задачка с имхо красивыми построениями, уходящими корнями к Бурбакам.
Возьмём категорию магм (множества с любыми бинарными операциями). Рассмотрим забывающий функтор во множества. Какой к нему левый сопряжённый? И что это получается за монадка? И что за алгебры над ней?
Далее, возьмём
data BinTree a = Leaf a | Node (BinTree a) (BinTree a)
Сделаем монадку путём return x = Leaf x, сделать join тоже несложно.
Что будет алгебрами над ней?

[sassa-nf.livejournal.com]

левый сопряжённый должен быть в какую-то свободную магму. Возможно, так мы получаем двоичное дерево. А что за алгебры - ну, можно проекции веток, а можно всё дерево как Fix Point. Но это алгебры эндофунктора. Алгебры над монадой ещё изучить нужно.

[nivanych.livejournal.com]

> свободную магму

Я достаю из широких штанин,
Раскрыта моя диафрагма —
«Смотрите-завидуйте все —
 Это
    свободная
             магма!»

data FreeMagma a = Leaf a | Node (FreeMagma a) (FreeMagma a)

Свободная магма на множестве, это тупо все деревья с листиками из этого множества. Операция умножения — сделать новое дерево из двух, подаваемых на вход.
Она даже не ассоциативна. Хотя и пробовать добавлять к этой операции свойства чуток поучительно. Например, коммутативность означает возможность вращать поддеревья, как угодно. Ассоциативность неинтересна, ибо тогда оно `вырождается` в свободный моноид ;-)
Функтор очевиден. И он ЧСХ левый сопряжённый!
Монадка тоже очевидна — получить такое дерево из дерева деревьев, это стандартная вещь.
Так вот, алгебры над этой монадкой, что не вполне очевидно, это любые бинарные операции. Только какбе "unbiased-способом" ;-) заданные.
То есть, с ходу, не очень очевидно, что алгебры над этой монадкой порождаются любыми бинарными операциями и наоборот.
Рекомендую рассмотреть эти алгебры и подумать над тем, что они из себя представляют.