Гиломорфизм (информатика)
В информатике и, в частности, в функциональном программировании , гиломорфизм — это рекурсивная функция, соответствующая композиции анаморфизма ( ( который сначала строит набор результатов; также известный как «развертывание»), за которым следует катаморфизм который затем сворачивает эти результаты). в окончательное возвращаемое значение ). Объединение этих двух рекурсивных вычислений в единый рекурсивный шаблон позволяет избежать построения промежуточной структуры данных. Это пример вырубки лесов , стратегии оптимизации программы. Родственным типом функции является метаморфизм , который представляет собой катаморфизм, за которым следует анаморфизм.
Формальное определение [ править ]
Гиломорфизм может быть определена в терминах его отдельных анаморфических и катаморфических частей.
Анаморфную часть можно определить в терминах унарной функции определение списка элементов в путем многократного применения ( «разворачивания» ) и предиката обеспечивающее завершающее условие.
Катаморфическую часть можно определить как комбинацию начального значения для складки и бинарного оператора используется для выполнения сгиба.
Таким образом, гиломорфизм
могут быть определены (при условии соответствующих определений & ).
Обозначения [ править ]
Сокращенное обозначение приведенного выше гиломорфизма: .
на практике Гиломорфизмы
Списки [ править ]
Списки — это распространенные структуры данных, поскольку они естественным образом отражают линейные вычислительные процессы. Эти процессы возникают при повторных ( итеративных ) вызовах функций. Поэтому иногда необходимо сформировать временный список промежуточных результатов, прежде чем сводить этот список к одному результату.
Одним из примеров часто встречающегося гиломорфизма является каноническая функция факториала .
factorial :: Integer -> Integer
factorial n
| n == 0 = 1
| n > 0 = 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]
. собой вычисление произведения элементов этого Катаморфизм, таким образом, представляет списка. Таким образом, в приведенных выше обозначениях факториал можно записать в виде где и .
Деревья [ править ]
Однако термин «гиломорфизм» применяется не только к функциям, действующим на изоморфизмы списков. Например, гиломорфизм также можно определить путем создания нелинейного дерева вызовов, которое затем сворачивается. Примером такой функции является функция генерации n й член последовательности Фибоначчи .
fibonacci :: Integer -> Integer
fibonacci n
| n == 0 = 0
| n == 1 = 1
| n > 1 = fibonacci (n - 2) + fibonacci (n - 1)
Эта функция, снова примененная к любому допустимому вводу, сгенерирует нелинейное дерево вызовов. В примере справа дерево вызовов, созданное с помощью применения fibonacci
функция на вход 4
.
На этот раз анаморфизмом является генерация дерева вызовов, изоморфного дереву с листовыми узлами. 0, 1, 1, 0, 1
и катаморфизм - суммирование этих листовых узлов.
См. также [ править ]
- Морфизм
- Морфизмы F-алгебр.
- От исходной алгебры к алгебре: катаморфизм
- От коалгебры к финальной коалгебре: анаморфизм
- Расширение идеи катаморфизмов: параморфизм.
- Расширение идеи анаморфизмов: апоморфизм.
Ссылки [ править ]
- Эрик Мейер; Мартен Фоккинга; Росс Патерсон (1991). «Функциональное программирование с помощью бананов, линз, конвертов и колючей проволоки» (PDF) . стр. 4, 5.