F-алгебра

В теории категорий $F$-алгебра — это алгебраическая структура, связанная с функтором $F$. $F$-алгебры можно использовать в программировании для представления структур данных, таких как списки и деревья.

Определение

$F$-алгеброй эндофунктора

$F:{\mathcal {C}}\longrightarrow {\mathcal {C}}$

называется объект $A$ из ${\mathcal {C}}$ вместе с морфизмом в ${\mathcal {C}}$

$\alpha :FA\longrightarrow A$.

Таким образом, $F$-алгебра — это пара $(A,\alpha )$.

Гомоморфизмом из $F$-алгебры $(A,\alpha )$ в $F$-алгебру $(B,\beta )$ называется морфизм в ${\mathcal {C}}$

$f:A\longrightarrow B$,

для которого верно

$f\circ \alpha =\beta \circ Ff:$

Для любого заданного эндофунктора $F$ можно рассмотреть категорию, объектами которой являются $F$-алгебры, а морфизмами — гомоморфизмы между $F$-алгебрами.

Примеры

Для примера, рассмотрим эндофунктор $F:Set\to Set$, который отображает множество $X$ в $1+X$. Здесь $Set$ - категория множеств, $1$ - любое одноэлементное множество, а $+$ — операция копроизведения (дизъюнктное объединение множеств). Тогда множество N неотрицательных целых чисел вместе с функцией $[\mathrm {zero} ,\mathrm {succ} ]:1+\mathbb {N} \to \mathbb {N}$, которая является копроизведением функций $\mathrm {zero} :1\to \mathbb {N}$ (которая всегда возвращает 0) и $\mathrm {succ} :\mathbb {N} \to \mathbb {N}$ (которая отображает n в n+1), является $F$-алгеброй.

Литература

• Varmo Vene, Categorical programming with inductive and coinductive types
• Philip Wadler, Recursive types for free! Университет Глазго, 1990 год, черновик.
• Pierce, Benjamin C. «F-Algebras». Basic Category Theory for Computer Scientists. ISBN 0-262-66071-7.