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