Хиломорфизм

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

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

Формальное определение

Хиломорфизм $h\ : A \rightarrow C$ может быть определён в терминах его отдельных частей, представляющих анаморфизм и катаморфизм.

Анаморфная часть может быть определена в терминах унарной функции $g\ : A \rightarrow B||A$, которая определяет список и предикат $p\ : A \rightarrow Boolean$, который задаёт условие останова генерации списка.

Катаморфная часть может быть определена как комбинация начального значения $c \in C$ для свёртки и бинарного оператора $\oplus : B||C \rightarrow C$, который и используется для свёртки структуры данных.

Таким образом, хиломорфизм это: $$h\ a = \begin{cases}c & \text{если} p \, a \\b \oplus ha' & \text{иначе}\end{cases}$$

где $(b, a') = ga$ может быть определено в терминах подходящих определений $p$, $g$, $h$.

Нотация

Сокращённое обозначение хиломорфизма выглядит следующим образом: $h = [\![(c, \oplus),(g, p)]\!]$.

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

Примеры

Список

Списки являются обычными структурами данных, поскольку постоянно появляются там, где линейный процесс применяется к некоторому количеству входных данных. Иногда необходимо (или, по крайней мере, полезно) сгенерировать временный список промежуточных значений перед редукцией этого списка в окончательный результат.

Ниже приводится пример типичного хиломорфизма, являющегося канонической функцией вычисления факториала.

factorial :: Integer -> Integer
factorial n | n >= 0 = if (n == 0)
                         then 1
                         else n * factorial (n - 1)

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

factorial 5 = 5 * (factorial 4) = 120
  factorial 4 = 4 * (factorial 3) = 24
    factorial 3 = 3 * (factorial 2) = 6
      factorial 2 = 2 * (factorial 1) = 2
        factorial 1 = 1 * (factorial 0) = 1
          factorial 0 = 1

В этом примере анаморфная часть процесса вычисления является генерацией дерева вызовов, изоморфного списку [1, 1, 2, 3, 4, 5]. Катаморфизмом же является вычисление произведения всех элементов этого списка. В этом случае в нотации оригинальной статьи [1] данная функция может быть записана как $factorial = [\![(1, \times), (g, p)]\!]$ где $g \, n = (n, n - 1)$ и $p \, n = n = 0$.

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

Вместе с тем необходимо отметить, что термин «хиломорфизм» может применяться не только к функциям, работающим со структурами данных, изоморфными списку. Например, хиломорфизм также может быть определён при помощи генерации нелинейного дерева вызовов, которое позже сворачивается в единственный результат. В качестве примера такой функции можно привети функцию, которая возвращает $n$-ый элемент последовательности Фибоначчи.

fibonacci :: Integer -> Integer
fibonacci n | n >= 0 = if (n == 0)
                         then 0
                         else if (n == 1)
                                then 1
                                else fibonacci (n - 2) + fibonacci (n - 1)

Дерево вызовов этой функции при применении к произвольному валидному входному параметру выглядит нелийнейно. Следующий пример показывает такое дерево вызовов, сгенерированное на основании значения входного параметра n = 4.

                   fib 4 <- 1 + 2 = 3
                  /     \
0 + 1 = 1 -> fib 2       fib 3 <- 1 + 1 = 2
             /  \        /   \
         fib 0  fib 1 fib 1  fib 2 <- 0 + 1 = 1
           |     |    |      /\
           0     1    1     /  \
                         fib 0  fib 1
                          |      |
                          0      1

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

См. также

• Анаморфизм
• Катаморфизм
• Параморфизм

Литература

1. Erik Meijer, Maarten Fokkinga, and Ross Paterson. Functional Programming with Bananas, Lenses, Envelopes, and Barbed Wire