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

Материал из свободной русской энциклопедии «Традиция»
Перейти к: навигация, поиск

Нача́льная а́лгебра — в математике (в первую очередь в теории категорий) начальный объект категории 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)\).

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

См. также[править]