Катаморфизм - Catamorphism

В теория категорий, Концепция чего-либо катаморфизм (от Греческий: κατά "вниз" и μορφή "форма, форма") обозначает уникальный гомоморфизм из начальная алгебра в какую-то другую алгебру.

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

Определение

Рассмотрим исходный F-алгебра (А, в) для некоторых эндофунктор F некоторых категория в себя. Здесь в это морфизм из FA к А. Поскольку он начальный, мы знаем, что всякий раз, когда (Икс, ж) Другой F-алгебра, т.е. морфизм ж из FX к Икс, есть уникальный гомоморфизм час из (А, в) к (Икс, ж). По определению категории F-алгебры, это час соответствует морфизму из А к Икс, условно также обозначается час, так что ${displaystyle hcirc in = fcirc Fh}$ . В контексте F-алгебры, однозначно указанный морфизм исходного объекта обозначается ката ж и, следовательно, характеризуется следующими отношениями:

${displaystyle h = mathrm {cata} f}$
${displaystyle hcirc in = fcirc Fh}$

Терминология и история

Еще одно обозначение, встречающееся в литературе: ${displaystyle (! | f |!)}$ . Используемые открытые скобки известны как банановые скобки, после чего катаморфизмы иногда называют бананы, как упоминалось в Эрик Мейер и другие.^[1] Одной из первых публикаций, вводящих понятие катаморфизма в контексте программирования, была статья «Функциональное программирование с использованием бананов, линз, конвертов и колючей проволоки». Эрик Мейер и другие.,^[1] что было в контексте Squiggol формализм. общее категоричное определение было дано Грант Малькольм.^[2]^[3]

Примеры

Мы приводим серию примеров, а затем более глобальный подход к катаморфизму в Haskell язык программирования.

Итерация

Итерационно-шаговые предписания приводят к натуральным числам в качестве исходного объекта.

Рассмотрим функтор fmaybe отображение типа данных б к типу данных fmaybe b, который содержит копию каждого термина из б а также один дополнительный срок Ничего (в Haskell это то, что Может быть делает). Это можно закодировать с помощью одного термина и одной функции. Итак, позвольте экземпляру StepAlgebra также включить функцию из fmaybe b к б, который отображает Ничего на определенный срок ноль из б, и где будут вызываться действия на скопированных условиях следующий.

тип StepAlgebra б = (б, б->б) - алгебры, которые мы кодируем парами (nil, next)данные Нат = Нуль | Succ Нат - исходная алгебра для описанного выше функтораfoldSteps :: StepAlgebra б -> (Нат -> б) - отображение катаморфизмов из Nat в bfoldSteps (ноль, следующий) Нуль       = нольfoldSteps (ноль, следующий) (Succ нац) = следующий $ foldSteps (ноль, следующий) нац

В качестве глупого примера рассмотрим алгебру строк, закодированную как ("вперед!", s -> "подождите .." ++ s), для которого Ничего отображается на "идти!" и иначе "ждать.. " добавляется. В качестве (Succ. Succ. Succ. Succ $ Zero) обозначает число четыре в Нат, следующее будет оцениваться как "подождите ... подождите ... подождите ... подождите ... иди!": foldSteps ("идти!", s -> "ждать.. " ++ s) (Succ . Succ . Succ . Succ $ Нуль). Мы можем легко изменить код на более полезную операцию, скажем, на повторяющуюся операцию алгебраической операции с числами, просто изменив F-алгебру (ноль, далее), который передается foldSteps

Свернуть список

Для фиксированного типа арассмотрим типы отображений функторов б к типу продукта этих двух типов. Кроме того, мы добавляем термин Ноль к этому результирующему типу. Теперь f-алгебра должна отображать Ноль на какой-то особый срок ноль из б или "объединить" пару (любой другой термин сконструированного типа) в термин б. Это слияние пары может быть закодировано как функция типа а -> б -> б.

тип КонтейнерАлгебра а б = (б, а -> б -> б) - f-алгебра в кодировке (nil, merge)данные Список а = Ноль | Минусы а (Список а) - которая оказывается исходной алгебройfoldrList :: КонтейнерАлгебра а б -> (Список а -> б) - карта катаморфизмов из (Список a) в bfoldrList (ноль, слияние) Ноль         = нольfoldrList (ноль, слияние) (Минусы Икс хз) = слияние Икс $ foldrList (ноль, слияние) хз

В качестве примера рассмотрим алгебру типов чисел, закодированных как (3, х-> у-> х * у), для которого число из а действует на номер из б простым умножением. Тогда следующее будет оцениваться в 3.000.000: foldrList (3, Икс-> у-> Икс*у) (Минусы 10 $ Минусы 100 $ Минусы 1000 Ноль)

Складка дерева

Для фиксированного типа арассмотрим типы отображений функторов б к типу, который содержит копию каждого термина а а также все пары б's (условия типа продукта двух экземпляров типа б). Алгебра состоит из функции б, который либо действует на а срок или два б термины. Это слияние пары можно закодировать как две функции типа а -> б соотв. б -> б -> б.

тип ДеревоАлгебра а б = (а -> б, б -> б -> б) - функция "два случая" кодируется как (f, g) данные Дерево а = Лист а | Ответвляться (Дерево а) (Дерево а) - которая оказывается исходной алгеброй foldTree :: ДеревоАлгебра а б -> (Дерево а -> б) - карта катаморфизмов из (Дерево a) в bfoldTree (ж, грамм) (Лист Икс)            = ж ИксfoldTree (ж, грамм) (Ответвляться оставили верно) = грамм (foldTree (ж, грамм) оставили) (foldTree (ж, грамм) верно)

treeDepth :: ДеревоАлгебра а Целое число - f-алгебра чисел, которая работает для любого типа вводаtreeDepth = (const 1, я j -> 1 + Максимум я j) treeSum :: (Num а) => ДеревоАлгебра а а - f-алгебра, которая работает для любого числового типа treeSum = (я бы, (+))

Общий случай

Более глубокие теоретико-категориальные исследования исходных алгебр показывают, что F-алгебра, полученная применением функтора к своей собственной исходной алгебре, изоморфна ей.

Системы сильных типов позволяют абстрактно указать начальную алгебру функтора ж как его фиксированная точка а = е а. Рекурсивно определенные катаморфизмы теперь можно закодировать в одну строку, где анализ случая (как в различных примерах выше) инкапсулируется с помощью fmap. Поскольку область последних - это объекты в образе ж, оценка катаморфизмов прыгает вперед и назад между а и е а.

тип Алгебра ж а = ж а -> а - общие f-алгебрыНовый тип Исправить ж = Исо { invIso :: ж (Исправить ж) } - дает нам исходную алгебру для функтора fката :: Функтор ж => Алгебра ж а -> (Исправить ж -> а) - катаморфизм от Fix f к aката alg = alg . fmap (ката alg) . invIso - обратите внимание, что invIso и alg отображаются в противоположных направлениях

Теперь снова первый пример, но теперь через передачу функтора Maybe в Fix. Повторное применение функтора Maybe порождает цепочку типов, которые, однако, могут быть объединены изоморфизмом из теоремы о неподвижной точке. Введем термин нуль, который возникает из Ничего и определить функцию-преемник с повторным применением Только. Так возникают натуральные числа.

тип Нат = Исправить Может бытьнуль :: Натнуль = Исо Ничего - у каждого «Может быть» есть термин «Ничто», и Iso отображает его впреемник :: Нат -> Натпреемник = Исо . Только - Просто сопоставляет a с 'Может быть', и Iso сопоставляет новый термин

пожалуйста, подождите :: Алгебра Может быть Нить - снова глупый пример f-алгебры сверхупожалуйста, подождите (Только нить) = "ждать.. " ++ нитьпожалуйста, подождите Ничего = "идти!"

Опять же, следующее будет оцениваться как "подождите ... подождите ... подождите ... подождите ... иди!": cata, пожалуйста, подождите (преемник. преемник. преемник. преемник $ ноль)

А теперь снова пример с деревом. Для этого мы должны предоставить тип данных контейнера дерева, чтобы мы могли настроить fmap (нам не нужно было делать это для Может быть функтор, как часть стандартной прелюдии).

данные Tcon а б = TconL а | TconR б бпример Функтор (Tcon а) куда    fmap ж (TconL Икс)   = TconL Икс    fmap ж (TconR у z) = TconR (ж у) (ж z)

тип Дерево а = Исправить (Tcon а) - исходная алгебраконец :: а -> Дерево аконец = Исо . TconLвстретить :: Дерево а -> Дерево а -> Дерево австретить л р = Исо $ TconR л р

treeDepth :: Алгебра (Tcon а) Целое число - снова пример treeDepth f-алгебрыtreeDepth (TconL Икс)   = 1treeDepth (TconR у z) = 1 + Максимум у z

Следующее будет оцениваться до 4: cata treeDepth $ meet (конец "X") (meet (meet (конец "YXX") (конец "YXY")) (конец "YY"))

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

Морфизм
Морфизмы F-алгебры
- От коалгебры к окончательной коалгебре: Анаморфизм
- За анаморфизмом следует катаморфизм: Гиломорфизм
- Расширение идеи катаморфизмов: Параморфизм
- Расширение идеи анаморфизмов: Апоморфизм

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

Катаморфизмы в HaskellWiki
Катаморфизмы Эдвард Кметт
Катаморфизмы в F # (Часть 1, 2, 3, 4, 5, 6, 7 ) Брайан Макнамара
Катаморфизмы в Haskell

[Meijer_et_al-1] а ^б Мейер, Эрик; Фоккинга, Маартен; Патерсон, Росс (1991), Хьюз, Джон (ред.), «Функциональное программирование с бананами, линзами, конвертами и колючей проволокой», Языки функционального программирования и архитектура компьютера, Springer Berlin Heidelberg, 523, стр. 124–144, Дои:10.1007/3540543961_7, ISBN 978-3-540-54396-1, получено 2020-05-07

[2] Малкольм, Грант Рейнольд (1990), Алгебраические типы данных и преобразование программ (PDF) (Докторская диссертация), Университет Гронингена, архив из оригинал (PDF) на 2015-06-10.

[3] Малкольм, Грант (1990), «Структуры данных и преобразование программ», Наука компьютерного программирования, 14 (2–3), стр. 255–279, Дои:10.1016/0167-6423(90)90023-7.

[1]

[2]

[3]