Русская Википедия:F-алгебра

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

Определение

<math>F</math>-алгеброй эндофунктора

<math>F : \mathcal{C}\longrightarrow \mathcal{C}</math>

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

<math>\alpha : FA \longrightarrow A</math>.

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

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

<math>f : A \longrightarrow B</math>,

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

<math>f \circ \alpha = \beta \circ Ff:</math>

Файл:Commutative diagram defining F-algebra.png

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

Примеры

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