Хиломорфизм

Материал из свободной русской энциклопедии «Традиция»
Перейти к: навигация, поиск

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

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

Формальное определение[править]

Хиломорфизм \(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