![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
"Functors are objects that can be treated as though they are a function or function pointer. Functors are most commonly used along with STLs"
src: "functors in C++"
src: "functors in C++"
Идея: есть джавный
И в продакшен. Мы же инженеры!
gist
Могу написать подробные комментарии, если интересно.
java.util.ArrayList, древний как доткомовский бум. А мы хочем функтор, но не можем написать ArrayList extends Functor; ну дык... дык и хер с ним; мы ж инженеры. В Скале можно. А зачем? А чтобы писать arrayList.map(someting=>something)И в продакшен. Мы же инженеры!
gist
Могу написать подробные комментарии, если интересно.
алгебры для одной специфической монады
Aug. 1st, 2012 01:36 pmВот возьмём-ка монадку
"Какая ж тут у нас монада? Монада берёт множество
Так вот, а какие ж бывают алгебры над такой монадой? Нам надо, чтобы был
Мне вот что-то сдаётся, что в условиях булевости и точечности (ну, скажем, в множествах) только проекция удовлетворяет такому условию.
Хотите попробовать порешать? По-моему, прикольная задачка. Хотелось бы найти, конечно, необходимые условия, при которых это так. Точечность на фиг не нужна, но булевость...
X2, из моего поста."Какая ж тут у нас монада? Монада берёт множество
X и сопоставляет ему X×X. Монадная единица - диагональ (η(x) = (x,x)), а монадное умножение, X×X×X×X → X×X строится, согласно картинкам из начала этой части, из ε: (Y1×Y2, Y1×Y2) →(Y1,Y2) - проектированием по первой и последней координатам. μ(x1,x2,x3,x4) = (x1,x4)."Так вот, а какие ж бывают алгебры над такой монадой? Нам надо, чтобы был
f: A×A → A, соблюдающий условия:f(a,a) == af(f(a1,a2),f(a3,a4)) == f(a1,a4)Мне вот что-то сдаётся, что в условиях булевости и точечности (ну, скажем, в множествах) только проекция удовлетворяет такому условию.
p1(a1,a2) = a1; p2(a1,a2) = a2.Хотите попробовать порешать? По-моему, прикольная задачка. Хотелось бы найти, конечно, необходимые условия, при которых это так. Точечность на фиг не нужна, но булевость...
сопряженные функторы-3
Jul. 25th, 2012 11:09 amИтак, если у нас имеются две категории, C и D, и два функтора,
Для сопряженной пары мы вывели два естественных преобразования,
Оказывается, если есть такие два естественных преобразования, для пары функторов, то они сопряжены.
Ну и правда, если есть
То же самое, по симметрии, проделывается и в другую сторону. Вообще, у меня тут половина рассуждений лишняя, потому что зеркальная симметрия ж (никаких бозонов).
Наши
Эти два чудесные свойства получаются в результате применения тех самых соответствий
У нас есть теперь всё для монады и комонады.
Монада делается путём композиции,
Единица оказывается единицей относительно монадного умножения, и умножение оказывается ассоциативно - всё это следует из описанных выше свойств сопряженных функторов.
Симметрично мы можем определить комонаду, путём композиции
Пример.
Возьмём категории C=Set и D=Set×Set - множества и пары множеств, и два функтора,
Первый функтор - диагональ, он множеству сопоставляет пару, состоящую из двух экземпляров оного, а второй паре множеств сопоставляет декартово произведение.
Эти два функтора сопряжены,
А именно, если есть
Какая ж тут у нас монада? Монада берёт множество
Кто любит симплициальные категории, увидит тут различные краюшки и рёбрушки, но это ладно, это мы лучше не будем трогать.
"Практический смысл" в программировании у этой монады вот какой: есть двоичный флаг; и наши данные от него зависят - в одном случае вызов возвращает
Вопросы?
(Завтра продолжу, хочу показать, как из монады можно построить сопряженную пару, и не одну.)
F: C → D и G: D → C, мы говорим, что эти два функтора образуют сопряженную пару, F ⊣ G если имеется взаимно-однозначное соответствиеF(X) → Y | <====> | X → G(Y) |
Для сопряженной пары мы вывели два естественных преобразования,
η: IdC → F;G и ε: G;F → IdD.Оказывается, если есть такие два естественных преобразования, для пары функторов, то они сопряжены.
Ну и правда, если есть
f: F(X) → Y, то приложим к нему G, получим G(f): G(F(X)) → G(Y), и соединим это с ηX: X → G(F(X)), получим ту самую X → G(Y).То же самое, по симметрии, проделывается и в другую сторону. Вообще, у меня тут половина рассуждений лишняя, потому что зеркальная симметрия ж (никаких бозонов).
Наши
ηX и εY обладают чудесными свойствами: |  |
Эти два чудесные свойства получаются в результате применения тех самых соответствий
α и β, что были нарисованы в первой серии - попробуйте сами.У нас есть теперь всё для монады и комонады.
Монада делается путём композиции,
T = F;G; это функтор T: C → C. В качестве монадной единицы годится уже появлявшаяся у нас η, а в качестве монадного умножения (a.k.a. flatten) возьмём μX = G(εF(X)): G(F(G(F(X)))) → G(F(X)).Единица оказывается единицей относительно монадного умножения, и умножение оказывается ассоциативно - всё это следует из описанных выше свойств сопряженных функторов.
Симметрично мы можем определить комонаду, путём композиции
U = G;F.Пример.
Возьмём категории C=Set и D=Set×Set - множества и пары множеств, и два функтора,
Δ(X) = (X,X) и Π((X,Y)) = X×Y.Первый функтор - диагональ, он множеству сопоставляет пару, состоящую из двух экземпляров оного, а второй паре множеств сопоставляет декартово произведение.
Эти два функтора сопряжены,
Δ ⊣Π.А именно, если есть
(f1,f2): (X,X) → (Y1, Y2), то это задаёт отображение X →Y1×Y2, и наоборот, отображение в декартово произведение Y1×Y2 задаёт пару отображений, по компонентам.Какая ж тут у нас монада? Монада берёт множество
X и сопоставляет ему X×X. Монадная единица - диагональ (η(x) = (x,x)), а монадное умножение, X×X×X×X → X×X строится, согласно картинкам из начала этой части, из ε: (Y1×Y2, Y1×Y2) →(Y1,Y2) - проектированием по первой и последней координатам. μ(x1,x2,x3,x4) = (x1,x4).Кто любит симплициальные категории, увидит тут различные краюшки и рёбрушки, но это ладно, это мы лучше не будем трогать.
"Практический смысл" в программировании у этой монады вот какой: есть двоичный флаг; и наши данные от него зависят - в одном случае вызов возвращает
Y1, а в другом Y2. Ну и если у нас есть функция, зависящая от того же флага, то нам надо как-то комбинировать и сплющивать; это же Reader Monad, сведённая к двоичному флагу. Ну вот эта монада и есть.Вопросы?
(Завтра продолжу, хочу показать, как из монады можно построить сопряженную пару, и не одну.)
Tags:
сопряженные функторы-2
Jul. 22nd, 2012 08:01 pmИтак, пусть есть сопряженная пара функторов,
Среди стрелок вида
Сейчас покажу некоторые свойства этой единицы.
1. Она естественна, т.е. коммутативен следующий квадрат:
Откуда эта естественность? Как доказать, что квадрат коммутативен, т.е. что композиция верхней и правой стрелок - то же самое, что композиция левой и нижней? Ну воспользуемся естественностью, определённой в прошлой серии:
Сначала разберёмся, что получается, если пройти по верхнему-правому пути в диаграмме
Нам надо понять, что за стрелка обозначена знаком вопроса.
Согласно диаграмме
- но это же просто
Теперь посмотрим, что получится от композиции вдоль левой и нижней граней диаграммы
Согласно диаграмме (c), этот треугольник, давайте нарисуем его отдельно,
эквивалентен следующему: 
Понятно, что на диагонали всё та же
Вставка. Естественное преобразование между двумя функторами F и G - это набор стрелок, делающий для всякого
коммутативным.
Аналогично для сопряженной пары функторов мы можем, по
Дальше мы узнаем, что для сопряженности функторов достаточно задать эти два преобразования, единицу и коединицу, с определёнными свойствами. Но мы ещё не увидели никаких свойств, кроме естественности.
Ну понемножку.
F ⊣ G (это обозначение такое). Повторяя из предыдущей части: стрелки F(X) → Y находятся в естественном взаимно-однозначном соотвествии со стрелками X → G(Y).Среди стрелок вида
f: F(X) → Y есть одна интересная - idF(X): F(X) → F(X); ей соответствует α(idF(X)): X → G(F(X)). Для неё есть специальное обозначение, ηX, и она называется единицей.Сейчас покажу некоторые свойства этой единицы.
1. Она естественна, т.е. коммутативен следующий квадрат:
| (a) |  |
Откуда эта естественность? Как доказать, что квадрат коммутативен, т.е. что композиция верхней и правой стрелок - то же самое, что композиция левой и нижней? Ну воспользуемся естественностью, определённой в прошлой серии:
(b) |  | <===> |  | |
(c) |  | <===> |  |
Сначала разберёмся, что получается, если пройти по верхнему-правому пути в диаграмме
(a).Нам надо понять, что за стрелка обозначена знаком вопроса.
Согласно диаграмме
(b), эта стрелка (композиция верхней и правой) является не чем иным, как α(???), где ??? есть диагональ в диаграмме - но это же просто F(f)! Так что наша искомая диагональ в квадрате (a) есть не что иное, как α(F(f)).Теперь посмотрим, что получится от композиции вдоль левой и нижней граней диаграммы
(a).Согласно диаграмме (c), этот треугольник, давайте нарисуем его отдельно,
эквивалентен следующему: Понятно, что на диагонали всё та же
F(f), так что "нижняя диагональ" равна "верхней", наш квадрат (a) коммутативен, и, следовательно, этот набор стрелок, ηX: X → G(F(X)), есть естественное преобразование.Вставка. Естественное преобразование между двумя функторами F и G - это набор стрелок, делающий для всякого
f: A →B квадрат вида коммутативным.Аналогично для сопряженной пары функторов мы можем, по
idG(X): G(X) → G(X), получить β(idG(X)): F(G(X)) → X. Она называется коединицей и обозначается εX; как и ηX, она является естественным преобразованием (из функтора G;F в функтор IdD, где D, если вы помните - категория, где функтор F принимает значения, и где задан функтор G.Дальше мы узнаем, что для сопряженности функторов достаточно задать эти два преобразования, единицу и коединицу, с определёнными свойствами. Но мы ещё не увидели никаких свойств, кроме естественности.
Ну понемножку.
спешу поделиться
Jan. 28th, 2011 04:24 pmВчера меня ![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif)
nivanych ткнул носом в прекрасное - коалгебры.
Короче, взять хоть какой функтор F, коалгебрами называются стрелки вида X -> FX с понятными морфизмами, квадратами
(btw, used my presheaf:)
Ну коалгебры и коалгебры: если взять знакомую монаду
, строящую списки в качестве свободных алгебр, то для неё свободные (инициальные) алгебры представляют собой списки (над алфавитом А), а терминальные коалгебры... что там будут за терминальные коалгебры? Бесконечные потоки символов из алфавита А? Похоже на то.
Ну это была интродукция. А теперь рондо каприччиозо.
Возьмём категорию частично-упорядоченных множеств (посетов), и определим каузальный объект как такой посет, у которого есть начало и конец (0 и 1). Почему каузальный - начало есть "причина всему", а конец есть "вывод из всего".
Определим такой функтор - последовательное присоединение каузального объекта к самому себе, началом к концу, как, э... нет, не будем вдаваться в анальные аналогии. Последовательное соединение.
Так вот, континуум есть терминальная коалгебра соединения каузальных объектов.
Как это так? А вот, если возьмём отрезок вещественных чисел (в Москве можно взять отрезок действительных чисел), то он является каузальным объектом, и является коалгеброй над таким функтором: соединение двух отрезков подряд даёт каyзальный объект. Более того, т.к. это соединение изоморфно исходному отрезку, то он является неподвижной точкой.
Почему континуум? Да потому что любой отрезок делится бесконечно пополам на изоморфные отрезки. Почему это именно алеф1, мне как-то непонятно, но т.к. тут, похоже, имеет место нефундированная теория множеств, то и на алефы как-то расчитывать не приходится.
nivanych ткнул носом в прекрасное - коалгебры.Короче, взять хоть какой функтор F, коалгебрами называются стрелки вида X -> FX с понятными морфизмами, квадратами
(btw, used my presheaf:)
Ну коалгебры и коалгебры: если взять знакомую монаду
, строящую списки в качестве свободных алгебр, то для неё свободные (инициальные) алгебры представляют собой списки (над алфавитом А), а терминальные коалгебры... что там будут за терминальные коалгебры? Бесконечные потоки символов из алфавита А? Похоже на то.Ну это была интродукция. А теперь рондо каприччиозо.
Возьмём категорию частично-упорядоченных множеств (посетов), и определим каузальный объект как такой посет, у которого есть начало и конец (0 и 1). Почему каузальный - начало есть "причина всему", а конец есть "вывод из всего".
Определим такой функтор - последовательное присоединение каузального объекта к самому себе, началом к концу, как, э... нет, не будем вдаваться в анальные аналогии. Последовательное соединение.
Так вот, континуум есть терминальная коалгебра соединения каузальных объектов.
Как это так? А вот, если возьмём отрезок вещественных чисел (в Москве можно взять отрезок действительных чисел), то он является каузальным объектом, и является коалгеброй над таким функтором: соединение двух отрезков подряд даёт каyзальный объект. Более того, т.к. это соединение изоморфно исходному отрезку, то он является неподвижной точкой.
Почему континуум? Да потому что любой отрезок делится бесконечно пополам на изоморфные отрезки. Почему это именно алеф1, мне как-то непонятно, но т.к. тут, похоже, имеет место нефундированная теория множеств, то и на алефы как-то расчитывать не приходится.
