рисуем монаду
Aug. 9th, 2013 01:56 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
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.
Конечно, преобразования это не любые, а подчиняющиеся определенным законам. Которые часто изображают в виде требования коммутирования таких вот диаграмм:
Альтернативные пути из точки А в точку Б на таких диаграммах показывают, какие стрелки и их композиции должны быть равны между собой. Например, тут говорится, что неважно, с какой стороны мы к Т добавляем η-й еще один Т, все равно применение к полученному Т2 μ дает тот же самый Т.
В данных диаграммах точки означают эндофункторы, а стрелки - естественные преобразования. Подвергнем их той же процедуре дуализации, получим струнные диаграммы:
Теперь естественные преобразования стали жирными точками, а категории - двумерным пространством. Единичный функтор, ничего не делающий, мы обозначим 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!
Для начала нарисуем что-нибудь совсем простое. Палка, палка, огуречик - получился моноид. Моноид состоит из множества (вообще-то необязательно, может быть и штука побольше чем множество), бинарной ассоциативной операции на нем и выделенного элемента, называемого единицей. Бинарная операция берет любые два элемента из этого множества и выдает какой-нибудь один элемент оттуда же.
Она должна быть ассоциативной, т.е. (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.
Конечно, преобразования это не любые, а подчиняющиеся определенным законам. Которые часто изображают в виде требования коммутирования таких вот диаграмм:
Альтернативные пути из точки А в точку Б на таких диаграммах показывают, какие стрелки и их композиции должны быть равны между собой. Например, тут говорится, что неважно, с какой стороны мы к Т добавляем η-й еще один Т, все равно применение к полученному Т2 μ дает тот же самый Т.
В данных диаграммах точки означают эндофункторы, а стрелки - естественные преобразования. Подвергнем их той же процедуре дуализации, получим струнные диаграммы:
Теперь естественные преобразования стали жирными точками, а категории - двумерным пространством. Единичный функтор, ничего не делающий, мы обозначим 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!
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2013-08-08 07:48 pm (UTC)no subject
Date: 2013-08-08 07:55 pm (UTC)no subject
Date: 2013-08-08 08:08 pm (UTC)В этот раз под пивко пошло, надо сказать, неплохо и весьма приятно, но без должной полноты.
Вообще офигенно, чё.
no subject
Date: 2013-08-08 08:19 pm (UTC)так вот какие они...
no subject
Date: 2013-08-08 10:45 pm (UTC)А про это ещё раз.
1. Монады образуют моноид (один) или монады образуют моноиды (по одному моноиду на монаду)? (ибо инглиш гласит нам, что моноидов много)
2. А умножение = композиция (произвольных эндофункторов) - это каким образом заслуга монад?
3. Тут как-то ещё не ясно, почему умножение - это композиция, если стрелками в категории эндофункторов являются эта, м...
no subject
Date: 2013-08-09 12:23 am (UTC)no subject
Date: 2013-08-09 12:51 am (UTC)картиночки здоровские
no subject
Date: 2013-08-09 02:03 am (UTC)Спасибо, пригодится, буду ссылку давать.
А вещь-то уходит в очень фундаментальное...
> двойственность Пуанкаре
Всё же, тут нужно быть аккуратнее, когда говоришь такие слова.
Но для быстрого туториала сойдёт, наверное.
Моноидальными диаграммами можно изображать как 2-категории, так и моноидальные. Для (lax monoidal) функторов или 2-функторов, уже надо третье измерение. Ну или для 3-категорий достаточно 3-х измерений, но функторы между ними уже так не изобразить. Или как-то с помощью проекции из 4-го измерения... Надо попробовать, как-нибудь, что ли...
Ещё, идеологически это рядом с понятием "распетливания" или "delooping".
Вот как моноидальную категорию представляют в виде бикатегории с одним объектом — говорят, что у нас это стрелки такие хитрые, а не объекты. Ну а обычные стрелки представляют 2-стрелками.
Ну а бикатегории уже как-то изображают ;-)
no subject
Date: 2013-08-09 03:27 am (UTC)Только без resoning'а про равенства.
То есть, можно точно, но где почитать — не знаю.
no subject
Date: 2013-08-09 03:31 am (UTC)Таким образом, каждая категория с заданным * образует конкретный "теоретико-множественный моноид" (в кавычках, потому что это не совсем точно), а если выбрать в этой категории тройку (T, u, n) получим конкретный моноид в этой категории.
Если это была категория эндофункторов, то каждый такой категорный моноид (тройка (T, u, n)) образует свою монаду (он и называется монадой, по определению).Ну а каждая монада - есть конкретный моноидл, понятное дело.
А образуют монады в целом моноид или нет - вопрос отдельный, если получится выбрать хорошую * - будут образовывать.
no subject
Date: 2013-08-09 03:40 am (UTC)Да, неправильно там написано. В роли "множества" конкретной монады-моноида выступает конкретный выбранный эндофунктор.
2. А где сказано, что это заслуга монад?
3. Ещё можно категорию Cat изобразить, как 2-категорию —
1-стрелки — функторы,
2-стрелки — естественные преобразования.
Соответственно, когда выбираешь какой-то объект и все 1-стрелки вокруг него, то получаешь, что каждую 1-эндострелку можно соединить с каждой.
Нетрудной проверкой убеждаемся, что относительно композиции этих 1-эндострелок, мы получаем строгую моноидальную категорию.
И вообще, любая бикатегория с одним объектом будет моноидальной, если мы композицию 1-стрелок предложим в качестве тензорного произведения в нашей новой моноидальной категории. Ну а 2-стрелки изначальной бикатегории в качестве 1-стрелок новой строящейся моноидальной.
no subject
Date: 2013-08-09 04:02 am (UTC)no subject
Date: 2013-08-09 04:14 am (UTC)Давно уже смотрел. Да, они могли такие аналогии приводить.
Нууу, скажем так — немало народу, кто хорошо знает про дуальность Пуанкаре, сочтёт аналогию натянутой.
При проведении некоторых доказательств, можно увидеть подобные аналогии. Но вот я лично очень не уверен, что это ключевой момент в интуиции.
Не, ну в целом-то отлично вышло!
Только немного неточностей подправить.
P.S. Маска-то на юзерпике какая-то не сварочная!
no subject
Date: 2013-08-09 08:50 am (UTC)2. ну, было написано, что "а композиция - это умножение", вот и восстало сознание, что не может такого быть - композиция и I есть всегда, а монада - нет.
3. классное объяснение. Нужно будет про 2-категории почитать ещё раз. А то вопрос какой-то был...
no subject
Date: 2013-08-09 08:58 am (UTC)можно ли сказать, что "*" - продукт в категорном смысле, а u - это проекция?
no subject
Date: 2013-08-09 09:26 am (UTC)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
no subject
Date: 2013-08-09 12:15 pm (UTC)no subject
Date: 2013-08-09 03:30 pm (UTC)no subject
Date: 2013-08-09 04:25 pm (UTC)no subject
Date: 2013-08-10 05:03 am (UTC)Из-за этого, например, групповой объект можно задать только с декартовым произведением. Правда, всегда можно задать моноид Хопфа, но это совсем другая история ;-)
Например, возьмём такую вот строгую моноидальную категорию-предпорядок —
объектами натуральные числа, для a≤b стрелка a→b, тензорным произведением сложение чисел.
Нетрудно убедиться, что это строгая моноидальная категория.
А теперь прошу мне предъявить две проекции из тензорного произведения 3+4 —
3+4→3 и 3+4→4 ;-)
Как устроены эти стрелки?
И кто за всем этим стоит? ;-)
no subject
Date: 2013-08-10 07:14 am (UTC)no subject
Date: 2013-08-10 07:17 am (UTC)Помнится, Дмитрий Павлов предлагал линейную алгебру рассказывать языком симметричных (ну и всякоразных) моноидальных категорий.
Надо бы как-то реализовать ;-)
no subject
Date: 2013-08-10 07:26 am (UTC)(Причём тут коумножение, не понял).
Насколько вижу, "интересные следствия" тут или элементарны или не относятся к именно умножению.
У меня тут интересное ассоциируется с группой Пикара.
no subject
Date: 2013-08-10 07:58 am (UTC)no subject
Date: 2013-08-10 08:07 am (UTC)Такие категории ещё называют (ко)декартовыми моноидальными.
Свойства, конечно, будут — (ко)произведение более сильное свойство, чем просто моноидальное. Но ведь не об этом речь?...
Наверное, я туплю...