F-алгебра

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

Определение

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

$F:𝒞⟶𝒞$

называется объект $A$ из $𝒞$ вместе с морфизмом в $𝒞$

$\alpha :FA⟶A$.

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

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

$f:A⟶B$,

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

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

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

Примеры

Для примера, рассмотрим эндофунктор $F:Set\to Set$, который отображает множество $X$ в $1+X$. Здесь $Set$ - категория множеств, $1$ - любое одноэлементное множество, а $+$ — операция копроизведения (дизъюнктное объединение множеств). Тогда множество N неотрицательных целых чисел вместе с функцией $[\mathrm{z}\mathrm{e}\mathrm{r}\mathrm{o},\mathrm{s}\mathrm{u}\mathrm{c}\mathrm{c}]:1+\mathbb{N}\to \mathbb{N}$, которая является копроизведением функций $\mathrm{z}\mathrm{e}\mathrm{r}\mathrm{o}:1\to \mathbb{N}$ (которая всегда возвращает 0) и $\mathrm{s}\mathrm{u}\mathrm{c}\mathrm{c}:\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.