Катаморфизм

Катаморфизм греч. κατα- «вниз» и μορφή, «форма» Понятие Примитив

Отношения с другими понятиями:

Теория:

Теория категорий

Примитив:

Катаморфизм 

Катаморфи́зм (от греч. κατα-, «вниз» и μορφή, «форма») — понятие из теории категорий, имеющее непосредственное применение в функциональном программировании. Является одним из базовых примитивов для описания рекурсивных функций (и, более общо, — рекурсивных процессов). Совместно с сопутствующими понятиями анаморфизма, хиломорфизма и параморфизма может использоваться для представления произвольных рекурсивных функций. Однако, принимая во внимание высокую степень абстракции теории категорий, понятие катаморфизма можно применять в тех областях научного знания, где имеется необходимость в применении примитивов для рекурсии. В том же функциональном программировании данное понятие можно использовать не только для функций, но и в механизме вывода типов (например, в рамках модели статической типизации Хиндли — Милнера), равно как и при кодогенерации и вычислении результатов в процессе интерпретации программ.

Катаморфизм в функциональном программировании

В функциональном программировании катаморфизм является обобщением свёртки (для списков) на произвольные алгебраические типы данных, что может быть описано при помощи начальных алгебр (понятие из теории категорий).

Одна из первых публикаций на эту тему в контексте программирования — статья «Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire» («Функциональное программирование при помощи бананов, линз, конвертов и колючей проволоки»), которая описывала катаморфизмы в стиле Squiggol.

Примеры

Наиболее просто катаморфизм можно понять при помощи примеров. Наиболее простым является катаморфизм на обыкновенных линейных списках (т. н. префиксированных списках). От простого к сложному: далее катаморфизм объясняется при помощи линейного списка и бинарных деревьев. Далее приводятся поясняющие примеры, написанные при помощи функционального языка программирования Haskell.

Список

Схематичное изображение списка, основанного на префиксации.

Пусть имеются следующие определения специального синонима для представления алгебр над списками (ListAlgebra), функции для организации свёртки списка (foldList) и нескольких примеров утилитарных функций, основанных на функции свёртки.

type ListAlgebra a r = (r, a -> r -> r)

foldList :: ListAlgebra a r -> [a] -> r
foldList (f, g) []     = f
foldList (f, g) (x:xs) = g x (foldList (f, g) xs)

listLength :: ListAlgebra a Integer
listLength = (0, \x xs -> 1 + xs)

listSum :: Num a => ListAlgebra a a
listSum = (0, \x xs -> x + xs)

В приведённом примере функция foldList (f, g) является катаморфизмом для типа [a], а функции listLength и listSum называются алгебрами.

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

Бинарное дерево

Схематичное изображение бинарного дерева.

Пусть имеются следующие определения типа для представления бинарного дерева (Tree a), специального синонима для представления алгебр над деревьями (TreeAlgebra), функции для организации свёртки дерева (foldTree) и нескольких примеров утилитарных функций, основанных на функции свёртки.

data Tree a = Leaf a
            | Branch (Tree a) (Tree a)

type TreeAlgebra a r = (a -> r, r -> r -> r)

foldTree :: TreeAlgebra a r -> Tree a -> r
foldTree (f, g) (Leaf x)     = f x
foldTree (f, g) (Branch l r) = g (foldTree (f, g) l) (foldTree (f, g) r)

treeDepth :: TreeAlgebra a Integer
treeDepth = (\x -> 1, \l r -> 1 + max l r)

treeSum :: (Num a) => TreeAlgebra a a
treeSum = (\x -> x, \l r -> l + r)

В приведённом примере функция foldTree (f, g) является катаморфизмом для типа Tree, а функции treeDepth и treeSum называются алгебрами.

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

Бинарное дерево (иной способ представления)

Схематичное изображение бинарного дерева.

Для более чёткого понимания разницы в определении катаморфизмов для разных алгебраических типов данных можно сравнить таковые определения для разных представлений бинарных деревьев. Следующий пример рассматривает бинарное дерево немного иного представления, в котором листьевые вершины заменены на «пустые деревья», а потому из любого элемента дерева может выходить 0, 1 или 2 ветви (в предыдущем способе представления — 0 или 2), при этом метки (элементы данных) могут находиться в любой вершине дерева, в то время как в предыдущем примере — только в листьевых. Типы и функции называются так же, как и в предыдущем примере.

data Tree a = Empty
            | Node a (Tree a) (Tree a)

type TreeAlgebra a r = (r, a -> r -> r -> r)

foldTree :: TreeAlgebra a r -> Tree a -> r
foldTree (f, g) Empty        = f
foldTree (f, g) (Node x l r) = g x (foldTree (f, g) l) (foldTree (f, g) r)

treeDepth :: TreeAlgebra a Integer
treeDepth = (0, \x l r -> 1 + max l r)

treeSum :: Num a => TreeAlgebra a a
treeSum = (0, \x l r -> x + l + r)

В приведённом примере функция foldTree (f, g) является катаморфизмом для типа Tree, а функции treeDepth и treeSum называются алгебрами.

Обобщённый способ применения

Понятие катаморфизма можно обобщить на произвольные алгебраические типы данных. Как известно, алгебраический тип данных является размеченным объединением декартовых произведений различных типов, в том числе и сам такой тип может включаться в своё определение рекурсивно. Каждому декартову произведению в языке Haskell соответствует один конструктор данных, после которого перечисляется 0 или более полей некоторых типов. Все конструкторы данных объединяются под единым конструктором типа.

Каждый конструктор типа может заключать в себя исходный алгебраический тип данных (такие конструкторы обозначаются — Ri, от слова «рекурсивный»), либо может не содержать (такие конструкторы обозначаются — Cj, от слова «конструктор»). Таким образом, произвольный алгебраический тип данных T определяется следующим образом:

data T a1 … an = C1 a11 … a1k
               | …
               | Cj aj1 … ajk
               | R1 a11 … (T a1 … an)11 …
               | …
               | Ri ai1 … (T a1 … an)i1 …

Для удобства к этому определению необходимо добавить синоним типа для представления алгебры. При описании такого синонима он должен содержать кортеж типов, количество которых равно общему количеству конструкторов данных типа T. В этом кортеже каждому конструктору данных Cj должен соответствовать тип функции fj, которая принимает на вход аргументы типов, которые собраны в соответствующем конструкторе Cj. Тип результата функций fj — r. Для каждого конструктора Ri в кортеже должен быть представлен тип некоторой функции gi, тип которой определяется так: для простых типов an аргумент функции должен иметь как раз этот тип, но для рекурсивных типов (T a1 … an) тип аргумента должен быть r. Возвращать функция должна также значение типа r. В итоге такой синоним определяется следующим образом:

type TAlgebra a1 … an r = (a11 -> … -> a1k -> r,
                           …,
                           a11 -> … -> a1m -> r,
                           a11 -> … -> r -> … -> r
                           …,
                           a11 -> … -> r -> … -> r)

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

foldT :: TAlgebra a1 … an r -> T a1 … an -> r

Само собой, что в контексте типа должны быть все ограничения, которые накладываются на типы a1 … an.

Эта функция foldT для каждого образца вида (Cj aj1 … ajk) возвращает значение соответствующей функции fj, а для образца вида Ri a11 … (T a1 … an)11 … — значение соответствующей функции gi. Все эти функции передаются в катаморфизм foldT в составе кортежа (первый аргумент).

Проблемы при взаимной рекурсии типов

Описанная выше технология построения катаморфизма позволяет создавать определения для произвольного типа данных. Однако эта технология даёт сбой, если имеется взаимнорекурсивные типы (два или более, объединённые транзитивной цепочкой), в рекурсивных функциях для которых необходимо обрабатывать данные всех типов. В этом случае без определения дополнительных вспомогательных функций не обойтись.

Например, пусть имеются следующие определения (пример придуман специально для демонстрации проблемы и не имеет практической целесообразности):

data Foo = FooZ | FooI Int Boo
data Boo = BooZ | BooI Int Foo

Эти «странные» определения всего лишь описывают простой префиксный список, содержащий целые числа. При попытке создать катаморфизмы и утилитарную функцию для сложения всех чисел, получится неприятная ситуация:

type FooAlgebra = (Int, Int -> Boo -> Int)
type BooAlgebra = (Int, Int -> Foo -> Int)

foldFoo :: FooAlgebra -> Foo -> Int
foldFoo (f, g) FooZ       = f
foldFoo (f, g) (FooI i v) = g i v

foldBoo :: BooAlgebra -> Boo -> Int
foldBoo (f, g) BooZ       = f
foldBoo (f, g) (BooI i v) = g i v

fooSum = foldFoo (0, \i b -> i + (foldBoo (0, \j f -> j + (foldFoo (…) f)) b))

В том месте кода, которое помечено тремя точками «…» будет происходить накрутка катаморфизмов, поэтому такое их использование не приведёт ни к чему. Поможет в этой проблеме использование комбинатора неподвижной точки (например, Y), который «спрячет» рекурсию. Одно из возможных решений:

fooSum = foldFoo ((0, 0), \i b -> let (x, y) = foldBoo ((0, 0), \i f -> let (x, y) = fooSum f
                                                                        in  (x, i + y)) b
                                  in  (i + x, y))

При этом соответствующим образом должны быть поправлены определения функций foldFoo и foldBoo — они должны возвращать пару значений.

Генерация катаморфизма для заданного типа

Все приведённые примеры наталкивают на мысль, что можно было бы создать универсальный механизм, который самостоятельно генерировал бы определения катаморфизма (а заодно и анаморфизма, хиломорфизма и параморфизма) для произвольного алебраического типа данных. Желательно, чтобы этот универсальный механизм был встроен в сам язык реализации (в рассматриваемых примерах — Haskell). Например, система классов типов могла бы в этом вопросе помочь.

Однако, к сожалению, теория определяет совершенно различные типы для катаморфизмов, которые соответствуют некоторым алгебраическим типам данных. Поэтому использование классов в языке Haskell не приведёт ни к чему. Такой механизм можно создать либо при помощи макросов языка (для Haskell — расширение Template Haskell), либо в виде внешнего препроцессора.

Окончательные замечания

Наконец, необходимо отметить, что приведённые примеры катаморфизмов для различных типов данных, а также общий способ построения катаморфизма для произвольного алгебраического типа данных — всё это лишь частная реализация теоретического механизма. Теория не ограничивает способы создания катаморфизмов, она лишь определяет, что такое катаморфизм и как его можно использовать на практике. Использование синонима типа и функций типа foldT — это один из многих способов имплементации теоретического понятия в коде функционального языка. То, каким способом определить катаморфизм для своего типа данных, разработчик программного обеспечения выбирает самостоятельно.

Катаморфизм в теории категорий

В теории категорий имеются все необходимые понятия для описания обобщённых определений для произвольных типов данных (совместно с использованием функций в функциональном программировании с морфизмами в категории Set или какой-то смежной категории). Впервые катаморфизм был описан в диссертации Г. Малькольма «Алгебраические типы и трансформация программ» и в статье «Структуры данных и трансформация программ».

Конкретизируя, к примеру, вышеприведённый исходный код для бинарного дерева первого способа представления, формальное определение катаморфизма заключается в следующем: для заданного типа a пара (r, [f, g]) является F-алгеброй, где F — функтор, отображающий r в (a + r × r).

Пара (Tree a, [Tip, Join]) также является F-алгеброй, более того — начальной F-алгеброй. Это означает, что существует уникальный гомоморфизм в любую иную F-алгебру. Этот уникальный гомоморфизм и называется катаморфизмом.

Общий случай

Если (A, in) является начальной F-алгеброй для эндофунктора F (таким образом, in является морфизмом из FA в A), и (X, f) — тоже F-алгебра, существует уникальный гомоморфизм из (A, in) в (X, f), который может быть обозначен как cata f (оставляя неявным носитель X). Здесь слово «cata» является обобщённым наименованием того, что названо идентификаторами «foldList» и «foldTree» в примерах выше.

Свойства

Пусть F задан и зафиксирован. Используя определение гомоморфизма, свойство уникальности может быть выражено как: для любой F-алгебры (X, f) и всех h из A в X два нижеследующих утверждения эквивалентны:

• h = cata f
• h º in = f º Fh

Катаморфизм является дуальным понятием к анаморфизму.

Нотация

Другой нотацией для записи cata f является $(\!|f|\!)$. Используемые круглые скобки иногда называются «банановыми скобками», поэтому катаморфизмы иногда называются «бананами».

См. также

• Анаморфизм
• Параморфизм
• Хиломорфизм

Ссылки

• Теория категорий в энциклопедии «Stanford Encyclopedia of Phylosophy».

Литература

1. Душкин Р. В. Функциональное программирование на языке Haskell. — М.: ДМК Пресс, 2006. С. 608. ISBN 5-94074-335-8
2. Bird R., de Moor O. The Algebra of Programming. — Prentice Hall PTR, 1996. P. 295. ISBN 0-13507-245-x
3. Meijer E., Fokkinga M., Paterson R.. Functional Programming with Bananas, Lenses, Envelopes, and Barbed Wire (перевод на русский язык)
4. Fokkinga M. A Gentle Introduction To Category Theory — The Calculational Approach.