F-алгебра

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

Определение

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

[math]\displaystyle{ F : \mathcal{C}\longrightarrow \mathcal{C} }[/math]

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

[math]\displaystyle{ \alpha : FA \longrightarrow A }[/math].

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

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

[math]\displaystyle{ f : A \longrightarrow B }[/math],

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

[math]\displaystyle{ f \circ \alpha = \beta \circ Ff: }[/math]

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

Примеры

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

Литература

• 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.