Observations

Итак, если у нас имеются две категории, C и D, и два функтора, F: C → D и G: D → C, мы говорим, что эти два функтора образуют сопряженную пару, F ⊣ G если имеется взаимно-однозначное соответствие

F(X) → Y

<====>

X → G(Y)

Для сопряженной пары мы вывели два естественных преобразования, η: Id_C → F;G и ε: G;F → Id_D.

Оказывается, если есть такие два естественных преобразования, для пары функторов, то они сопряжены.
Ну и правда, если есть 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, сведённая к двоичному флагу. Ну вот эта монада и есть.

Вопросы?

(Завтра продолжу, хочу показать, как из монады можно построить сопряженную пару, и не одну.)

Got it eventually. Thanks to huzhepidarasa and "Applicative programming with effects" by McBride and Paterson.

So, let's see.

In Haskell, in Scala, and I don't know... in PHP? every monad is an applicative functor, with the help of lift2. But I could not figure out where does it come from?

Say we have a category C that has products a × b and power objects, b^a; an endofunctor T is called applicative if it is supplied with two natural transformations,
pure: a → T(a) and (*): T(ba) → T(b)T(a) that have obvious properties.

The statement is that every monad is an applicative functor.

Turned out not every monad, but a strong one.

A strong monad is a monad that has a natural transformation ta,b: a × T(b) → T(a×b) with a bunch of good properties that could be found on wikipedia (are they called coherence? something like that - MacLane studied them eons ago).

Anyway, a strong monad is an applicative functor.

We already have pure; have to define (*).

The trick is this.

Given a binary operation f: a×b → c then we will lift this binary operation (since we deal with a function of two parameters, the operation is called lift2) to T(a)×T(b) → T(c)

Namely, we have

tT(a),b: T(a)×T(b) → T(T(a)×b)
T(flipT(a),b): T(T(a)×b) → T(b×T(a))
T(tb,T(a)): T(b×T(a)) → T(T(b×a))
T(T(flipb,a)): T(T(b×a)) → T(T(a×b))
T(T(f)):T(T(a×b)) → T(T(c))
mc: T(T(c)) → T(c)

Composing them, we will have the lift2 we were looking for.

Now take evala,b: a × ba → b, and apply lift2

We will have T(a) × T(ba) → T(b); currying it, we get (*): T(ba) → T(b)T(a)

This may be obvious from the fp point of view, but I am a categorist, not a functional programmer (although you should have seen the rich loops I've been writing lately in Scala), so I needed a sound proof, not just a sound of a proof.

Thank you.

Questions and remarks greatly welcome.