Заметки о свободных конструкциях

Речь пойдет о Free Monoid, Free functor, Free monad, Звезде Клини

Сначала пара программистских интуитивных наводок, а потом категорное веселье (спасибо Кметту[1] за него). Скорее всего в моем понимании масса ошибок и неточностей, так что это не окончательная версия.

(Free ⊣ Forgetfull),(Forgetfull ⊣ Cofree)

Free foo is such minimal foo that satisfies “foo” laws.

Свободные монады относятся к монадам так же, как списки относятся к моноидам. Иными словами, если список — простейший моноид, то свободная монада — простейшая монада.

Интересно, как происходит применение оператора (>>=). Если обычная монада сразу соединяет(сворачивает, вычисляет) 2 контекста в один, то свободная монада как бы оттягивает это процесс на потом. Монадические контексты накапливаются(вкладываются, стакаются) друг на друга, и программист только в самом конце решает, что ему с ними сделать, как вычислить получившийся список (“список функоров”?).

Если есть пара функторов F:C -> D; G:D -> C такая что

∀x ∈ Ob(C), y ∈ Ob(D): Hom(F(x), y) ≅ Hom(x, G(y))

То F ⊣ G, то есть F — левый сопряженный (adjoint) к G, G — парвый сопряженный к F, вместе они образуют сопряженную пару функторов (adjoint).

Формально, свободный функтор является левым сопряженным забывающему функтору. Косвободный функтор является соответственно правым сопряженным забывающему функтору.

Понятие забывающего функтора довольно нестрогое, здесь нужно положиться на интуицию. Забывающий функтор теряет часть структуры.

Например, отображение из категории списков в категорию множеств List -> Set является забывающим. Соответственно, Set->List является свободным функтором (у меня есть неподтвержденная идея что он как бы “цепляется” к нужной структуре, потому и является свободным).

Другой пример —категория Set, категория Mon, сопряженная пара функторов F ⊣ U:

U :: Mon -> Set
U (a, mappend, mempty) = a
F :: Set -> Mon
F a = ([a], (++), [])

Как указано в учебнике [2], звезда Клини (замыкание Клини) являеся свободным моноидом.

Пусть V - множество, 
e - пустая строка (моноидальная единица),
V[0] = {e},
V[1] = V,
V[i+1] = { wv | w ∈ V[i], v ∈ V }
A* = ⋃{i=0 to ∞} V[i]
Например, если множество символов V = {a,b} то V*  - vмножество всех возможных слов (строк) из этих символов), то
A* = {e, a, b, aa, ab, ba, bb, aaa, aab, ... }
A+ = A*\{e} - Плюс Клини А+ это звезда Клини без единицы. Выходит, что это полугруппа.

Вопрос: Если List = {C, (++), []}, Set = {C, ∪, ∅}- оба моноиды, можно ли считать пару функций (функторов) F: Set -> List, G: List -> Set:
а) Сопряженными функторами?
б) Свободным и забывающим функторами?

Show your support

Clapping shows how much you appreciated Nick Yurchenko’s story.