Катаморфизм

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

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

Определение

Рассмотрим начальную -алгебру для некоторого эндофунктора некоторой категории в себя. Вот морфизм из в . Поскольку он является начальным, мы знаем, что всякий раз, когда есть другая -алгебра, т.е. морфизм из в , существует единственный гомоморфизм из в . По определению категории -алгебры это соответствует морфизму из в , традиционно также обозначаемому , такому, что . В контексте -алгебры однозначно заданный морфизм из начального объекта обозначается и, следовательно, характеризуется следующим соотношением: ${\displaystyle F}$ ${\displaystyle (A,in)}$ ${\displaystyle F}$ ${\displaystyle in}$ ${\displaystyle FA}$ ${\displaystyle A}$ ${\displaystyle (X,f)}$ ${\displaystyle F}$ ${\displaystyle f}$ ${\displaystyle FX}$ ${\displaystyle X}$ ${\displaystyle h}$ ${\displaystyle (A,in)}$ ${\displaystyle (X,f)}$ ${\displaystyle F}$ ${\displaystyle h}$ ${\displaystyle A}$ ${\displaystyle X}$ ${\displaystyle h}$ ${\displaystyle h\circ in=f\circ Fh}$ ${\displaystyle F}$ ${\displaystyle \mathrm {cata} \ f}$

• ${\displaystyle h=\mathrm {cata} \ f}$
• ${\displaystyle h\circ in=f\circ Fh}$

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

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

Примеры

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

Катаморфизм для Maybe-алгебры

Рассмотрим функтор, Maybeопределенный в приведенном ниже коде Haskell:

данные Может быть = Ничего | Просто -- Может быть тип        класс Functor f где -- класс для функторов fmap :: ( a -> b ) -> ( f a -> f b ) -- действие функтора на морфизмы                экземпляр Functor Maybe где -- превратить Maybe в функтор fmap g Nothing = Nothing fmap g ( Just x ) = Just ( g x )                 

Начальным объектом Maybe-алгебры является множество всех объектов натурального числового типа Natвместе с морфизмом, iniопределенным ниже: ^{[4] [5]}

data Nat = Zero | Succ Nat -- тип натурального числа       ini :: Maybe Nat -> Nat — начальный объект Maybe-алгебры (с небольшим искажением обозначений) ini Nothing = Zero ini ( Just n ) = Succ n              

Карту cataможно определить следующим образом: ^[5]

cata :: ( Maybe b -> b ) -> ( Nat -> b ) cata g Zero = g ( fmap ( cata g ) Nothing ) -- Примечание: fmap (cata g) Nothing = g Nothing и Zero = ini(Nothing) cata g ( Succ n ) = g ( fmap ( cata g ) ( Just n )) -- Примечание: fmap (cata g) ( Just n) = Just (cata gn) и Succ n = ini( Just n)                            

В качестве примера рассмотрим следующий морфизм:

g :: Может быть String -> String g Ничего = "go!" g ( Просто str ) = "wait..." ++ str               

Затем cata g ((Succ. Succ . Succ) Zero)будет оценено как «подожди... подожди... подожди... поехали!».

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

Для фиксированного типа aрассмотрим функтор, MaybeProd aопределенный следующим образом:

data MaybeProd a b = Nothing | Just ( a , b ) -- (a,b) — тип произведения a и b          класс Functor f где -- класс для функторов fmap :: ( a -> b ) -> ( f a -> f b ) -- действие функтора на морфизмы                экземпляр Functor ( MaybeProd a ) где -- превращаем MaybeProd a в функтор, функториальность только во второй переменной типа fmap g Nothing = Nothing fmap g ( Just ( x , y )) = Just ( x , g y )                   

Исходная алгебра MaybeProd aзадается списками элементов с типом aвместе с морфизмом, iniопределенным ниже: ^[6]

Список данных a = EmptyList | Cons a ( Список a )         ini :: MaybeProd a ( List a ) -> List a -- начальная алгебра MaybeProd a ini Nothing = EmptyList ini ( Just ( n , l )) = Cons n l                  

Карту cataможно определить следующим образом:

cata :: ( MaybeProd a b -> b ) -> ( List a -> b ) cata g EmptyList = g ( fmap ( cata g ) Nothing ) -- Примечание: ini Nothing = EmptyList cata g ( Cons s l ) = g ( fmap ( cata g ) ( Just ( s , l ))) -- Примечание: Cons sl = ini ( Just (s,l))                               

Обратите внимание также, что cata g (Cons s l) = g (Just (s, cata g l)). В качестве примера рассмотрим следующий морфизм:

g :: MaybeProd Int Int -> Int g Ничего = 3 g ( Просто ( x , y )) = x * y             

cata g (Cons 10 EmptyList)оценивается как 30. Это можно увидеть, развернув cata g (Cons 10 EmptyList)=g (Just (10,cata g EmptyList)) = 10* cata g EmptyList=10* g Nothing=10*3.

Таким же образом можно показать, что это cata g (Cons 10 (Cons 100 (Cons 1000 EmptyList)))будет равно 10*(100*(1000*3))=3.000.000.

Карта cataтесно связана с правой складкой (см. Складка (функция высшего порядка) ) списков foldrList. Морфизм lift, определяемый

поднять :: ( a -> b -> b ) -> b -> ( MaybeProd a b -> b ) поднять g b0 Ничего = b0 поднять g b0 ( Просто ( x , y )) = g x y                           

относится cataк правой части foldrListсписков через:

foldrList :: ( a -> b -> b ) -> b -> Список a -> b foldrList fun b0 = cata ( поднять fun b0 )                   

Определение cataподразумевает, что foldrListэто правая складка, а не левая. Например: foldrList (+) 1 (Cons 10 ( Cons 100 ( Cons 1000 EmptyList)))будет оцениваться как 1111 и foldrList (*) 3 (Cons 10 ( Cons 100 ( Cons 1000 EmptyList)))как 3.000.000.

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

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

type TreeAlgebra a b = ( a -> b , b -> b -> b ) -- функция "два случая" кодируется как (f, g) data Tree 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.

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

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

type Nat = Fix Maybe zero :: Nat zero = Iso Nothing -- каждый 'Maybe a' имеет термин Nothing, и Iso отображает его в последующий элемент :: Nat -> Nat successor = Iso . Just -- Just отображает a в 'Maybe a', а Iso отображает обратно в новый термин                   

pleaseWait :: Algebra Maybe 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 экземпляр Функтор ( Tcon a ) где fmap f ( TconL x ) = TconL x fmap f ( TconR y z ) = TconR ( f y ) ( f z )                                

тип Дерево a = Fix ( Tcon a ) -- начальная алгебра end :: a -> Дерево a end = Iso . TconL встреча :: Дерево a -> Дерево a -> Дерево a встреча l r = Iso $ TconR l r                                 

treeDepth :: Algebra ( Tcon a ) Integer -- снова пример f-алгебры treeDepth 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-алгебр
  • От коалгебры к конечной коалгебре: анаморфизм
  • Анаморфизм, за которым следует катаморфизм: гилеморфизм
  • Расширение идеи катаморфизмов: параморфизм
  • Расширение идеи анаморфизмов: апоморфизм

Ссылки

1. Meijer, Erik; Fokkinga, Maarten; Paterson, Ross (1991), Hughes, John (ред.), "Функциональное программирование с бананами, линзами, конвертами и колючей проволокой", Functional Programming Languages ​​and Computer Architecture , т. 523, Springer Berlin Heidelberg, стр. 124–144, doi :10.1007/3540543961_7, ISBN 978-3-540-54396-1, S2CID  11666139 , получено 2020-05-07
2. Малкольм, Грант Рейнольд (1990), Алгебраические типы данных и преобразование программ (PDF) (диссертация на степень доктора философии), Университет Гронингена, архивировано из оригинала (PDF) 2015-06-10.
3. Малкольм, Грант (1990), «Структуры данных и преобразование программ», Science of Computer Programming , т. 14, № 2–3, стр. 255–279, doi : 10.1016/0167-6423(90)90023-7.
4. «Начальная алгебра эндофунктора в nLab».
5. "Натуральное число в nLab".
6. «Начальная алгебра эндофунктора в nLab».

Дальнейшее чтение

• Ки Юнг Ан; Шеард, Тим (2011). «Иерархия рекурсивных комбинаторов в стиле Мендлера: укрощение индуктивных типов данных с отрицательными вхождениями». Труды 16-й международной конференции ACM SIGPLAN по функциональному программированию . ICFP '11.

Внешние ссылки

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