Начальная алгебра - Initial algebra

Определение

В математика, начальная алгебра является исходный объект в категория из ${displaystyle F}$ -алгебры для данного эндофунктор ${displaystyle F}$ . Это начальное значение обеспечивает общую основу для индукция и рекурсия.

Примеры

Функтор ${displaystyle 1 + X}$

Рассмотрим эндофунктор ${displaystyle F: mathbf {Set} или mathbf {Set}}$ отправка ${displaystyle X}$ к ${displaystyle 1 + X}$ , куда ${displaystyle 1}$ одноточечный (одиночка ) набор, то конечный объект в категории. Алгебра для этого эндофунктора - это множество ${displaystyle X}$ (называется перевозчик алгебры) вместе с функция ${displaystyle f: (1 + X) o X}$ . Определение такой функции равносильно определению точки ${displaystyle xin X}$ и функция ${displaystyle X o X}$ .Определять

{displaystyle {egin {выравнивается} имя оператора {ноль} двоеточие 1 & longrightarrow mathbf {N} * & longmapsto 0end {выравнивается}}}

и

{displaystyle {egin {выровнено} имя оператора {succ} двоеточие mathbf {N} и longrightarrow mathbf {N} n & longmapsto n + 1.end {выровнено}}}

Тогда набор ${displaystyle mathbf {N}}$ натуральных чисел вместе с функцией ${displaystyle [имя оператора {ноль}, имя оператора {succ}] двоеточие 1 + mathbf {N} или mathbf {N}}$ это начальный ${displaystyle F}$ -алгебра. Первоначальность ( универсальная собственность в данном случае) установить несложно; уникальный гомоморфизм произвольному ${displaystyle F}$ -алгебра ${displaystyle (A, [e, f])}$ , за ${displaystyle ecolon 1 o A}$ элемент ${displaystyle A}$ и ${displaystyle fcolon A o A}$ функция на ${displaystyle A}$ , это функция, отправляющая натуральное число ${displaystyle n}$ к ${displaystyle f ^ {n} (e)}$ , то есть, ${displaystyle f (f (dots (f (e)) dots))}$ , то ${displaystyle n}$ -кратное применение ${displaystyle f}$ к ${displaystyle e}$ .

Набор натуральные числа является носителем исходной алгебры для этого функтора: точка равна нулю, а функция является функция преемника.

Функтор ${displaystyle 1 + mathbf {N} imes (-)}$

В качестве второго примера рассмотрим эндофунктор ${displaystyle 1 + mathbf {N} imes (-)}$ на категории множеств, где ${displaystyle mathbf {N}}$ - множество натуральных чисел. Алгебра для этого эндофунктора - это множество ${displaystyle X}$ вместе с функцией ${displaystyle (1 + mathbf {N} imes X) o X}$ . Чтобы определить такую функцию, нам понадобится точка ${displaystyle xin X}$ и функция ${displaystyle mathbf {N} imes X o X}$ . Множество конечных списки натуральных чисел является начальной алгеброй для этого функтора. Дело в пустом списке, а функция минусы, беря число и конечный список и возвращая новый конечный список с числом во главе.

В категориях с бинарными побочные продукты, только что данные определения эквивалентны обычным определениям объект натурального числа и список объектов, соответственно.

Заключительная коалгебра

Вдвойне, а последняя коалгебра это конечный объект в категории ${displaystyle F}$ -коалгебры. Окончательность обеспечивает общую основу для коиндукция и Corecursion.

Например, используя тот же функтор ${displaystyle 1 + (-)}$ как и раньше, коалгебра определяется как множество ${displaystyle X}$ вместе с функцией ${displaystyle f: X o (1 + X)}$ . Определение такой функции сводится к определению частичная функция $f ' : Икс ⇸ Y$ чей домен формируется теми ${displaystyle xin X}$ для которого ${displaystyle f (x)}$ принадлежит ${displaystyle 1}$ . Такую структуру можно рассматривать как цепочку множеств, ${displaystyle X_ {0}}$ на котором ${displaystyle f '}$ не определено, ${displaystyle X_ {1}}$ какие элементы отображаются в ${displaystyle X_ {0}}$ к ${displaystyle f '}$ , ${displaystyle X_ {2}}$ какие элементы отображаются в ${displaystyle X_ {1}}$ к ${displaystyle f '}$ и т. д., и ${displaystyle X_ {omega}}$ содержащий остальные элементы ${displaystyle X}$ . С учетом этого набор ${displaystyle mathbf {N} чашка {omega}}$ состоящий из множества натуральных чисел, расширенных новым элементом ${displaystyle omega}$ является носителем финальной коалгебры в категории, где ${displaystyle f '}$ - функция-предшественник ( обратный функции-преемника) на положительные натуральные числа, но действует как личность на новом элементе ${displaystyle omega}$ : ${displaystyle f (n + 1) = n}$ , ${displaystyle f (omega) = omega}$ . Этот набор ${displaystyle mathbf {N} чашка {omega}}$ то есть носитель последней коалгебры ${displaystyle 1 + (-)}$ известен как набор естественных чисел.

В качестве второго примера рассмотрим тот же функтор ${displaystyle 1 + mathbf {N} imes ({mathord {-}})}$ как прежде. В этом случае носитель окончательной коалгебры состоит из всех списков натуральных чисел, как конечных, так и бесконечный. Операции - это тестовая функция, проверяющая, является ли список пустым, и функция деконструкции, определенная для непустых списков, возвращающая пару, состоящую из головы и хвоста входного списка.

Теоремы

Исходные алгебры минимальны (т.е. не имеют собственной подалгебры).
Конечные коалгебры просто (т. е. не иметь собственных частных).

Использование в информатике

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

Чтобы получить тип ${displaystyle mathrm {Список} (A)}$ списков, элементы которых являются членами множества ${displaystyle A}$ , учтите, что операции по формированию списков:

${displaystyle mathrm {nil} двоеточие 1 o mathrm {List} (A)}$
${displaystyle mathrm {cons} двоеточие A imes mathrm {List} (A) o mathrm {List} (A)}$

Объединенные в одну функцию, они дают:

${displaystyle [mathrm {nil}, mathrm {cons}] двоеточие (1 + A imes mathrm {List} (A)) o mathrm {List} (A)}$ ,

что делает это ${displaystyle F}$ -алгебра для эндофунктора ${displaystyle F}$ отправка ${displaystyle X}$ к ${displaystyle 1+ (A imes X)}$ . На самом деле это то исходный ${displaystyle F}$ -алгебра. Первоначальность устанавливается функцией, известной как складной в функциональный языки программирования Такие как Haskell и ML.

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

${displaystyle [mathrm {tip}, mathrm {join}] двоеточие A + (mathrm {Tree} (A) imes mathrm {Tree} (A)) o mathrm {Tree} (A)}$ .

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

Типы, определенные с помощью наименьшая фиксированная точка построить с функтором ${displaystyle F}$ можно рассматривать как начальный ${displaystyle F}$ -алгебра при условии, что параметричность выполняется для типа.^[1]

В двойном смысле аналогичная связь существует между понятиями наибольшая фиксированная точка и терминал ${displaystyle F}$ -коалгебра, с приложениями к коиндуктивный типы. Их можно использовать для разрешения потенциально бесконечный объекты при сохранении свойство сильной нормализации.^[1] В строго нормализующем (каждая программа завершается) языке программирования Charity коиндуктивные типы данных могут использоваться для достижения удивительных результатов, например определение искать конструкции для реализации таких "сильный" функционирует как Функция Аккермана.^[2]

Смотрите также

Примечания

^ ^а ^б Филип Вадлер: Рекурсивные типы бесплатно! Университет Глазго, июль 1998 г. Проект.
^ Робин Кокетт: Мысли о благотворительности (ps.gz )

внешняя ссылка

Категориальное программирование с индуктивным и коиндуктивным типами от Вармо Вене
Рекурсивные типы бесплатно! Филип Вадлер, Университет Глазго, 1990-2014.
Начальная алгебра и финальная семантика коалгебры для параллелизма автор: J.J.M.M. Руттен и Д. Тури
Первоначальность и окончательность из CLiki
Типизированные окончательные интерпретаторы без тегов Олег Киселев

[free-rectypes-1] а ^б Филип Вадлер: Рекурсивные типы бесплатно! Университет Глазго, июль 1998 г. Проект.

[2] Робин Кокетт: Мысли о благотворительности (ps.gz )

[1]

[2]