Jump to content

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

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

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

Гиломорфизм может быть определена в терминах его отдельных анаморфических и катаморфических частей.

Анаморфную часть можно определить в терминах унарной функции определение списка элементов в путем многократного применения ( «разворачивания» ) и предиката обеспечивающее завершающее условие.

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

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

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

Обозначения [ править ]

Сокращенное обозначение приведенного выше гиломорфизма: .

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

Списки [ править ]

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

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

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

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

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

См. также [ править ]

Ссылки [ править ]

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

Внешние ссылки [ править ]

Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: bbdb6d17aa4a03b48edf3237e5bdd5f8__1706044620
URL1:https://arc.ask3.ru/arc/aa/bb/f8/bbdb6d17aa4a03b48edf3237e5bdd5f8.html
Заголовок, (Title) документа по адресу, URL1:
Hylomorphism (computer science) - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)