В математике начальная алгебра — это начальный объект в категории F -алгебр для заданного эндофунктора F. Эта начальность обеспечивает общую основу для индукции и рекурсии .
Рассмотрим эндофунктор F : Set → Set , отправляющий X в 1 + X , где 1 — одноточечное ( синглтонное ) множество , конечный объект в категории. Алгебра для этого эндофунктора — это множество X (называемое носителем алгебры) вместе с функцией f : (1 + X ) → X . Определение такой функции равносильно определению точки и функции X → X . Определим
и
Тогда множество N натуральных чисел вместе с функцией [zero,succ]: 1 + N → N является начальной F -алгеброй. Начальность ( универсальное свойство для этого случая) нетрудно установить; единственный гомоморфизм в произвольную F -алгебру ( A , [ e , f ]) , для e : 1 → A элемента A и f : A → A функции на A , есть функция, сопоставляющая натуральное число n с f n ( e ) , то есть f ( f (…( f ( e ))…)) , n -кратное применение f к e .
Множество натуральных чисел является носителем исходной алгебры для этого функтора: точка — ноль, а функция — функция-последователь .
В качестве второго примера рассмотрим эндофунктор 1 + N × (−) в категории множеств, где N — множество натуральных чисел. Алгебра для этого эндофунктора — это множество X вместе с функцией 1 + N × X → X . Чтобы определить такую функцию, нам нужна точка и функция N × X → X . Множество конечных списков натуральных чисел — это начальная алгебра для этого функтора. Точка — это пустой список, а функция — cons , берущая число и конечный список и возвращающая новый конечный список с числом во главе.
В категориях с бинарными копроизведениями приведенные определения эквивалентны обычным определениям объекта натурального числа и объекта списка соответственно.
Двойственно , конечная коалгебра является конечным объектом в категории F -коалгебр . Финальность обеспечивает общую структуру для коиндукции и корекурсии .
Например, используя тот же функтор 1 + (−) , что и раньше, коалгебра определяется как множество X вместе с функцией f : X → (1 + X ) . Определение такой функции равнозначно определению частичной функции f' : X ⇸ X , область определения которой образована теми, для которых f ( x ) не принадлежит 1 . Имея такую структуру, мы можем определить цепочку множеств: X 0 , являющуюся подмножеством X , на котором f ′ не определено, X 1 , элементы которого отображаются в X 0 с помощью f ′ , X 2 , элементы которого отображаются в X 1 с помощью f ′ и т. д., и X ω , содержащую оставшиеся элементы X . С этой точки зрения множество , состоящее из множества натуральных чисел, расширенного новым элементом ω , является носителем конечной коалгебры, где — функция-предшественник ( обратная функции-последователя) на положительных натуральных числах, но действует как тождество на новом элементе ω : f ( n + 1) = n , f ( ω ) = ω . Это множество , являющееся носителем конечной коалгебры 1 + (−), известно как множество конатуральных чисел.
Для второго примера рассмотрим тот же функтор 1 + N × (−) , что и раньше. В этом случае носитель конечной коалгебры состоит из всех списков натуральных чисел, как конечных, так и бесконечных . Операции — это тестовая функция, проверяющая, является ли список пустым, и функция деконструкции, определенная для непустых списков, возвращающая пару, состоящую из головы и хвоста входного списка.
Различные конечные структуры данных , используемые в программировании , такие как списки и деревья , могут быть получены как начальные алгебры конкретных эндофункторов. Хотя для данного эндофунктора может быть несколько начальных алгебр, они являются уникальными с точностью до изоморфизма , что неформально означает, что «наблюдаемые» свойства структуры данных могут быть адекватно зафиксированы путем определения ее как начальной алгебры.
Чтобы получить тип List( A ) списков, элементы которых являются членами множества A , учтите, что операции формирования списка следующие:
Объединенные в одну функцию, они дают:
что делает это F -алгеброй для эндофунктора F, отправляющего X в 1 + ( A × X ) . Это, по сути, начальная F -алгебра. Начальность устанавливается функцией, известной как foldr в функциональных языках программирования, таких как Haskell и ML .
Аналогично, бинарные деревья с элементами на листьях могут быть получены как исходная алгебра
Типы, полученные таким образом, известны как алгебраические типы данных .
Типы, определенные с использованием конструкции наименьшей неподвижной точки с функтором F, можно рассматривать как исходную F -алгебру, при условии, что для типа выполняется параметричность . [1]
В двойственном смысле, подобная связь существует между понятиями наибольшей неподвижной точки и терминальной F -коалгебры, с приложениями к коиндуктивным типам. Они могут быть использованы для разрешения потенциально бесконечных объектов при сохранении сильного свойства нормализации . [1] В сильно нормализующем (каждая программа завершается) языке программирования Charity коиндуктивные типы данных могут быть использованы для достижения удивительных результатов, например, определения конструкций поиска для реализации таких «сильных» функций, как функция Аккермана . [2]
![{\ displaystyle [\ mathrm {nil}, \ mathrm {cons} ] \ двоеточие (1 + A \ times \ mathrm {List} (A)) \ to \ mathrm {List} (A),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c88fe5652580556557888fe3bb5c0a9d9d8dcba3)
![{\displaystyle [\mathrm {tip},\mathrm {join} ]\colon A+(\mathrm {Tree} (A)\times \mathrm {Tree} (A))\to \mathrm {Tree} (A). }](https://wikimedia.org/api/rest_v1/media/math/render/svg/e54894a9844f76e201e367fc02c331427ca250a2)