Начальная алгебра

Нача́льная а́лгебра — в математике (в первую очередь в теории категорий) начальный объект категории F-алгебр для заданного эндофунктора F.

Пример

Пусть эндофунктор $F: \mathbf{Set} \longrightarrow \mathbf{Set}$ отображает $X$ в $1 + X$. В этом случае множество натуральных чисел $N$ совместно с функциями $[zero, succ] : 1 + N \longrightarrow N$, где $zero : 1 \longrightarrow N$ и $succ : N \longrightarrow N$ — функции, смысл которых понятен из их наименования; является начальной $F$-алгеброй. Начальность (универсальное свойство в этом случае) несложно установить — уникальный гомоморфизм в произвольную $F$-алгебру $(A, [e, f])$, для $e : 1 \longrightarrow A$ элемента $A$, и $f : A \longrightarrow A$ — функция над $A$; является функцией, отображающей натуральное число $n$ в $f^n (e)$, т. е. $f (f (\ldots(f (e))\ldots))$ — $n$-арное применение функции $f$ к аргументу $e$.

Использование в теории программирования

Различные конечные структуры данных, используемые в программировании, такие как списки и деревья, могут быть получены в виде начальных алгебр определённых эндофункторов. Поскольку может существовать несколько начальных алгебр для заданного эндофунктора, они уникальны с точностью до изоморфизма, который неформально является заметным свойством структур данных и может быть адекватно выражен при помощи определения его в виде начальной алгебры.

Для получения типа $List (A)$ — списка над элементами множества $A$, необходимо иметь следующие операции конструирования списка:

• $nil : 1 \longrightarrow List (A)$
• $cons : A \times List (A) \longrightarrow List (A)$

Преобразованные в функции они выглядят следующим образом:

• $[nil, cons] : 1 + (A \times List (A)) \longrightarrow List (A)$,

что делает эту $F$-алгебру эндофунктора $F$ отображающей $X$ в $1 + (A \times X)$. Это, фактически, и является начальной $F$-алгеброй. Первоначально основана на функции, известной как foldr в функциональном программировании в таких языках программирования как Haskell и ML.

Таким же образом бинарные деревья с элементами в листьевых вершинах могут быть получены в виде начальной алгебры.

• $[tip, join] : A + (Tree (A) \times Tree (A)) \longrightarrow Tree (A)$.

Типы данных, получаемые подобным образом, называются алгебраическими типами данных.

См. также

• Алгебраический тип данных
• Катаморфизм