F-алгебра
В теории категорий -алгебра — это алгебраическая структура, связанная с функтором . -алгебры можно использовать в программировании для представления структур данных, таких как списки и деревья.
Определение
-алгеброй эндофунктора
называется объект из вместе с морфизмом в
- .
Таким образом, -алгебра — это пара .
Гомоморфизмом из -алгебры в -алгебру называется морфизм в
- ,
для которого верно
Для любого заданного эндофунктора можно рассмотреть категорию, объектами которой являются -алгебры, а морфизмами — гомоморфизмы между -алгебрами.
Примеры
Для примера, рассмотрим эндофунктор , который отображает множество в . Здесь - категория множеств, - любое одноэлементное множество, а — операция копроизведения (дизъюнктное объединение множеств). Тогда множество N неотрицательных целых чисел вместе с функцией , которая является копроизведением функций (которая всегда возвращает 0) и (которая отображает n в n+1), является -алгеброй.
Литература
- 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.