Хиломорфизм

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

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

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

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

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

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

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

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

НотацияПравить

Сокращённое обозначение хиломорфизма выглядит следующим образом: h = [ [ ( c , ) , ( g , p ) ] ] 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] данная функция может быть записана как f a c t o r i a l = [ [ ( 1 , × ) , ( g , p ) ] ] factorial = [\![(1, \times), (g, p)]\!] где g n = ( n , n 1 ) g \, n = (n, n - 1) и p n = n = 0 p \, n = n = 0 .

Бинарное деревоПравить

Вместе с тем необходимо отметить, что термин «хиломорфизм» может применяться не только к функциям, работающим со структурами данных, изоморфными списку. Например, хиломорфизм также может быть определён при помощи генерации нелинейного дерева вызовов, которое позже сворачивается в единственный результат. В качестве примера такой функции можно привети функцию, которая возвращает n 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