F-алгебра

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

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

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

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

${\displaystyle \alpha :FA\longrightarrow A}$.

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

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

${\displaystyle f:A\longrightarrow B}$,

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

${\displaystyle f\circ \alpha =\beta \circ Ff:}$

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

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