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

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

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

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

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

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

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

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

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

Обозначения

Сокращенное обозначение приведенного выше гиломорфизма: $h=[\![(c,\oplus ),(g,p)]\!]$.

на

Списки

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

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

факториал   ::   Целое   ->   Целое  факториал   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]. собой вычисление произведения элементов этого Катаморфизм, таким образом, представляет списка. Таким образом, в приведенных выше обозначениях факториал можно записать в виде ${\text{factorial}}=[\![(1,\times ),(g,p)]\!]$ где $g\ n=(n,n-1)$ и $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