В теории категорий , понятие катаморфизма (от древнегреческого : κατά «вниз» и μορφή «форма, форма») обозначает уникальный гомоморфизм из исходной алгебры в какую - либо другую алгебру.
В функциональном программировании , катаморфизм обеспечивает обобщение складок в списках произвольных алгебраических типов данных , которые могут быть описаны как начальные алгебры . Двойственное понятие - это анаморфизм, который разворачивает обобщение . Гилеморфизм представляет собой композицию из анаморфизма с последующим катаморфизмом.
Определение
Рассмотрим начальную -алгебра для какого-то эндофунктора какой-то категории в себя. Здесьэто морфизм из к . Поскольку он начальный, мы знаем, что всякий раз, когда Другой -алгебра, т.е. морфизм из к , существует единственный гомоморфизм из к . По определению категории-алгебра, это соответствует морфизму из к , условно также обозначается , так что . В контексте-алгебра, однозначно заданный морфизм исходного объекта обозначается через и, следовательно, характеризуется следующими отношениями:
Терминология и история
Еще одно обозначение, встречающееся в литературе: . Используемые открытые скобки известны как скобки для бананов , после чего катаморфизмы иногда называют бананами , как упоминалось в Erik Meijer et al . [1] Одной из первых публикаций, вводящих понятие катаморфизма в контексте программирования, была статья Эрика Мейера и др. «Функциональное программирование с бананами, линзами, конвертами и колючей проволокой» . , [1] что было в контексте формализма Сквиггола . Общее категориальное определение дал Грант Малкольм . [2] [3]
Примеры
Мы даем серию примеров, а затем более глобальный подход к катаморфизму на языке программирования Haskell .
Итерация
Итерационно-шаговые предписания приводят к натуральным числам в качестве исходного объекта.
Рассмотрим функтор, fmaybe
отображающий тип данных в тип b
данных fmaybe b
, который содержит копию каждого термина из, b
а также один дополнительный термин Nothing
(в Haskell это то, что Maybe
делает). Это можно закодировать с помощью одного термина и одной функции. Так пусть экземпляр StepAlgebra также включает в себя функцию от fmaybe b
к b
, которая отображает Nothing
на определенный срок nil
от b
, и где действий на скопированных условиях будут называться next
.
type StepAlgebra b = ( b , b -> b ) - алгебры, которые мы кодируем парами (nil, next)данные Nat = Zero | Succ Nat - начальная алгебра для описанного выше функтораfoldSteps :: StepAlgebra b -> ( Nat -> b ) - отображение катаморфизмов из Nat в b foldSteps ( nil , next ) Zero = nil foldSteps ( nil , next ) ( Succ nat ) = next $ foldSteps ( nil , next ) нац
В качестве глупого примера рассмотрим алгебру строк, закодированных как ("go!", \s -> "wait.. " ++ s)
, для которых Nothing
отображается, "go!"
а в противном случае "wait.. "
добавляется. Как (Succ . Succ . Succ . Succ $ Zero)
обозначает число четыре в Nat
следующем будут вычисляться «ожидание .. ожидание .. ожидание .. ожидание .. идти!»: . Мы можем легко изменить код на более полезную операцию, скажем, на повторяющуюся операцию алгебраической операции над числами, просто изменив F-алгебру , которая передается вfoldSteps ("go!", \s -> "wait.. " ++ s) (Succ . Succ . Succ . Succ $ Zero)
(nil, next)
foldSteps
Свернуть список
Для фиксированного типа a
рассмотрите типы отображения функтора b
на тип продукта этих двух типов. Более того, мы также добавляем термин Nil
к этому результирующему типу. Е-алгебра сейчас и карта Nil
в какой - то специальный термин nil
из b
или «слияния» пары (любой другой член построенного типа) в срок b
. Это слияние пары может быть закодировано как функция типа a -> b -> b
.
type ContainerAlgebra a b = ( b , a -> b -> b ) - f-алгебра в кодировке (nil, merge) список данных a = Nil | Минусы a ( Список a ) - который оказывается исходной алгебройfoldrList :: ContainerAlgebra a b -> ( List a -> b ) - отображение катаморфизмов из (List a) в b foldrList ( nil , merge ) Nil = nil foldrList ( nil , merge ) ( Cons x xs ) = merge x $ foldrList ( ноль , объединить ) xs
В качестве примера рассмотрим алгебру типов чисел, закодированных как (3, \x-> \y-> x*y)
, для которых число from a
действует на число from b
простым умножением. Тогда следующее будет оцениваться в 3.000.000:foldrList (3, \x-> \y-> x*y) (Cons 10 $ Cons 100 $ Cons 1000 Nil)
Складка дерева
Для фиксированного типа a
рассмотрим типы отображения функтора b
в тип, который содержит копию каждого члена, a
а также всех пар b
(термины типа продукта двух экземпляров типа b
). Алгебра состоит из функции b
, которая действует либо на a
члене, либо на двух b
членах. Это слияние пары может быть закодировано как две функции типа a -> b
соотв. b -> b -> b
.
type TreeAlgebra a b = ( a -> b , b -> b -> b ) - функция "два случая" кодируется как (f, g) дерево данных a = Leaf a | Branch ( Tree a ) ( Tree a ) - которая оказывается исходной алгеброй foldTree :: TreeAlgebra a b -> ( Tree a -> b ) - отображение катаморфизмов из (Tree a) в b foldTree ( f , g ) ( Leaf x ) = f x foldTree ( f , g ) ( Branch left right ) = g ( foldTree ( f , g ) left ) ( foldTree ( f , g ) right )
treeDepth :: TreeAlgebra a Integer - f-алгебра чисел, которая работает для любого типа ввода treeDepth = ( const 1 , \ i j -> 1 + max i j ) treeSum :: ( Num a ) => TreeAlgebra a a - f-алгебра, которая работает для любого числового типа treeSum = ( id , ( + ))
Общий случай
Более глубокие теоретико-категориальные исследования исходных алгебр показывают, что F-алгебра, полученная в результате применения функтора к своей собственной исходной алгебре, изоморфна ей.
Системы сильных типов позволяют абстрактно указать исходную алгебру функтора f
как его неподвижную точку a = fa . Рекурсивно определенные катаморфизмы теперь можно закодировать в одну строку, где анализ случая (как в различных примерах выше) инкапсулируется с помощью fmap. Поскольку область последних - это объекты в изображении f
, оценка катаморфизмов прыгает вперед и назад между a
и f a
.
type Algebra f a = f a -> a - общие f-алгебрыnewtype Fix f = Iso { invIso :: f ( Fix f ) } - дает нам начальную алгебру для функтора fcata :: Functor f => Algebra f a -> ( Fix f -> a ) - катаморфизм от Fix f к cata alg = alg . fmap ( cata alg ) . invIso - обратите внимание, что invIso и alg отображаются в противоположных направлениях
Теперь снова первый пример, но теперь через передачу функтора Maybe в Fix. Повторное применение функтора Maybe порождает цепочку типов, которые, однако, могут быть объединены изоморфизмом из теоремы о неподвижной точке. Мы вводим термин zero
, который происходит от Maybes, Nothing
и определяем функцию-преемницу с повторным применением Just
. Так возникают натуральные числа.
type Nat = Fix Maybe zero :: Nat zero = Iso Nothing - каждое 'Maybe a' имеет термин Nothing, и Iso отображает его в преемника :: Nat -> Nat преемник = Iso . Просто - просто сопоставляет a с «Может быть, а», а ISO сопоставляет с новым термином.
pleaseWait :: Algebra Может быть String - снова глупый пример f-алгебры, приведенный выше, pleaseWait ( Just string ) = "wait .." ++ string pleaseWait Nothing = "go!"
Опять же, следующее будет оцениваться как "подождите ... подождите ... подождите ... подождите ... иди!": cata pleaseWait (successor.successor.successor.successor $ zero)
А теперь снова пример с деревом. Для этого мы должны предоставить тип данных контейнера дерева, чтобы мы могли настроить fmap
(нам не нужно было делать это для Maybe
функтора, поскольку это часть стандартной прелюдии).
данные Tcon a b = TconL a | TconR b b instance Functor ( Tcon a ) где fmap f ( TconL x ) = TconL x fmap f ( TconR y z ) = TconR ( f y ) ( f z )
type Tree a = Fix ( Tcon a ) - исходная алгебра end :: a -> Tree a end = Iso . TconL meet :: Tree a -> Tree a -> Tree a meet l r = Iso $ TconR l r
treeDepth :: Algebra ( Tcon a ) Integer - опять же, пример treeDepth f-алгебры treeDepth ( TconL x ) = 1 treeDepth ( TconR y z ) = 1 + max y z
Следующее будет оцениваться до 4: cata treeDepth $ meet (end "X") (meet (meet (end "YXX") (end "YXY")) (end "YY"))
Смотрите также
- Морфизм
- Морфизмы F-алгебр
- От коалгебры к финальной коалгебре: анаморфизм
- За анаморфизмом следует катаморфизм: гиломорфизм
- Расширение идеи катаморфизмов: параморфизм
- Расширение идеи анаморфизмов: апоморфизм
Рекомендации
- ^ a b Мейер, Эрик; Фоккинга, Маартен; Патерсон, Росс (1991), Хьюз, Джон (редактор), «Функциональное программирование с помощью бананов, линз, конвертов и колючей проволоки» , Языки функционального программирования и компьютерная архитектура , Springer Berlin Heidelberg, 523 , стр. 124–144, doi : 10.1007 / 3540543961_7 , ISBN 978-3-540-54396-1, дата обращения 07.05.2020
- ^ Малкольм, Грант Рейнольд (1990), Алгебраические типы данных и преобразование программ (PDF) (докторская диссертация), Университет Гронингена, заархивировано из оригинала (PDF) 10 июня 2015 г..
- ^ Малькольм Грант (1990), "Структуры данных и преобразование программ", Наука компьютерного программирования , 14 (2-3), стр 255-279,. Дои : 10.1016 / 0167-6423 (90) 90023-7.
дальнейшее чтение
- Ки Юнг Ан; Шеард, Тим (2011). «Иерархия комбинаторов рекурсии в стиле Мендлера: укрощение индуктивных типов данных с отрицательными вхождениями» . Материалы 16-й международной конференции ACM SIGPLAN по функциональному программированию . ICFP '11.
Внешние ссылки
- Катаморфизмы в HaskellWiki
- Катаморфизмы Эдварда Кметта
- Катаморфизмы в F # (Часть 1 , 2 , 3 , 4 , 5 , 6 , 7 ) Брайана Макнамара
- Катаморфизмы в Haskell