Введение

В математике, в частности в теории категорий, коалгебра — это структура, определяемая согласно функтору, с определенными свойствами, как указано ниже. Для алгебр и коалгебр функтор является удобным и общим способом организации сигнатуры. Это находит применение в информатике: примеры коалгебр включают ленивые вычисления, бесконечные структуры данных, такие как потоки, а также системы переходов. Коалгебры двойственны алгебрам. Подобно тому, как класс всех алгебр для данной сигнатуры и теории уравнений образует вариацию, класс всех коалгебр, удовлетворяющих данной теории уравнений, образует ковариацию, где сигнатура задается .

Примеры

Рассмотрим эндофунктор, который отображает множество в его дизъюнктное объединение с одноэлементным множеством. Коалгебра этого эндофунктора задается выражением , где – так называемые конатуральные числа, состоящие из неотрицательных целых чисел и бесконечности, а функция задается как , для и . Фактически, это терминальная коалгебра этого эндофунктора. В более общем случае, зафиксируем некоторое множество , и рассмотрим функтор, который отображает в . Тогда -коалгебра – это конечный или бесконечный поток над алфавитом , где – множество состояний, а – функция перехода между состояниями. Применение функции перехода к состоянию может дать два возможных результата: либо элемент вместе со следующим состоянием потока, либо элемент одноэлементного множества, определяющий отдельное "конечное состояние", указывающее на отсутствие дальнейших значений в потоке. Во многих практических приложениях функция перехода состояния такой коалгебры может иметь вид , которая легко факторизуется на множество "селекторов", "наблюдателей", "методов". Особые случаи, представляющие практический интерес, включают наблюдателей, возвращающих значения атрибутов, и методы-мутаторы вида , принимающие дополнительные параметры и возвращающие состояния. Это разложение является двойственным к разложению начальных алгебр на суммы "конструкторов". Пусть P – построение множества мощностей на категории множеств, рассматриваемое как ковариантный функтор. P-коалгебры находятся в биективном соответствии с множествами, снабженными бинарным отношением. Теперь зафиксируем другое множество, A. Тогда коалгебры для эндофунктора P(A×( )) находятся в биективном соответствии с помеченными системами переходов, а гомоморфизмы между коалгебрами соответствуют функциональным бисимуляциям между помеченными системами переходов.

Приложения

В информатике, коалгебра стала удобным и достаточно общим способом спецификации поведения систем и структур данных, которые потенциально бесконечны, например, классы в объектно-ориентированном программировании, потоки и системы переходов. В то время как алгебраическая спецификация описывает функциональное поведение, обычно используя индуктивные типы данных, генерируемые конструкторами, коалгебраическая спецификация занимается поведением, моделируемым коиндуктивными типами процессов, которые наблюдаются посредством селекторов, во многом в духе теории автоматов. Важную роль здесь играют финальные коалгебры, представляющие собой полные множества, возможно, бесконечных поведений, таких как потоки. Естественной логикой для выражения свойств таких систем является коалгебраическая модальная логика.