Гилеморфизм (информатика)

Рекурсивная функция

В информатике , и в частности в функциональном программировании , гилеморфизм — это рекурсивная функция, соответствующая композиции анаморфизма ( который сначала строит набор результатов; также известный как «развертывание»), за которым следует катаморфизм (который затем сворачивает эти результаты в конечное возвращаемое значение ). Объединение этих двух рекурсивных вычислений в один рекурсивный шаблон позволяет избежать построения промежуточной структуры данных. Это пример обезлесения , стратегии оптимизации программы. Связанным типом функции является метаморфизм , который представляет собой катаморфизм, за которым следует анаморфизм.

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

Гилеморфизм можно определить через его отдельные анаморфную и катаморфную части. ${\displaystyle h:A\rightarrow C}$

Анаморфную часть можно определить в терминах унарной функции, определяющей список элементов в результате повторного применения ( «развертывания» ), и предиката, обеспечивающего условие завершения. ${\displaystyle g:A\rightarrow B\times A}$ ${\displaystyle B}$ ${\displaystyle p:A\rightarrow {\text{Boolean}}}$

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

Таким образом, гилеморфизм

${\displaystyle h\,a={\begin{cases}c&{\mbox{if }}p\,a\\b\oplus h\,a'\,\,\,where\,(b,a')=g\,a&{\mbox{otherwise}}\end{cases}}}$

может быть определен (при условии соответствующих определений & ). ${\displaystyle p}$ ${\displaystyle g}$

Обозначение

Сокращенная запись для вышеуказанного гилеморфизма — . ${\displaystyle h=[\![(c,\oplus ),(g,p)]\!]}$

Гилеморфизмы на практике

Списки

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

Одним из примеров часто встречающегося гилеморфизма является каноническая факториальная функция.

факториал :: Целое число -> Целое число факториал n | n == 0 = 1 | n > 0 = n * факториал ( n - 1 )                      

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

факториал 5 = 5 * (факториал 4) = 120факториал 4 = 4 * (факториал 3) = 24факториал 3 = 3 * (факториал 2) = 6факториал 2 = 2 * (факториал 1) = 2факториал 1 = 1 * (факториал 0) = 1факториал 0 = 1

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

Деревья

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

 фибоначчи :: Целое -> Целое фибоначчи n | п == 0 = 0 | п == 1 = 1 | n > 1 = Фибоначчи ( n - 2 ) + Фибоначчи ( n - 1 )                                

Дерево вызова дляfibonacci 4

Эта функция, снова примененная к любому допустимому входу, сгенерирует дерево вызовов, которое является нелинейным. В примере справа дерево вызовов, сгенерированное путем применения fibonacciфункции к входу 4.

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

Смотрите также

• Морфизм
• Морфизмы F-алгебр
  • От начальной алгебры к алгебре: катаморфизм
  • От коалгебры к конечной коалгебре: анаморфизм
  • Расширение идеи катаморфизмов: параморфизм
  • Расширение идеи анаморфизмов: апоморфизм

Ссылки

• Эрик Мейер; Маартен Фоккинга; Росс Патерсон (1991). «Функциональное программирование с помощью бананов, линз, конвертов и колючей проволоки» (PDF) . стр. 4, 5.

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

• Гилеморфизмы в Haskell
• Больше гилеморфизмов в Haskell