Hylomorfizm (informatyka) - Hylomorphism (computer science)

W informatyce , a zwłaszcza programowania funkcjonalnego , A Hylemorfizm jest rekurencyjne funkcja odpowiadająca kompozycja wystąpienia anamorphism (która najpierw tworzy się zbiór wyników, znanych również jako „rozwijanie”), a następnie catamorphism (które następnie składa tych wyników do końcowej wartości zwracanej ). Połączenie tych dwóch obliczeń rekurencyjnych w jeden wzorzec rekurencyjny pozwala uniknąć tworzenia pośredniej struktury danych. To jest przykład wylesiania , strategii optymalizacji programu. Podobnym rodzajem funkcji jest metamorfizm , czyli katamorfizm, po którym następuje anamorfizm.

Definicja formalna

Hylomorfizm można zdefiniować w kategoriach jego oddzielnych części anamorficznych i katamorficznych. ${\ displaystyle h: A \ rightarrow C}$

Część anamorficzną można zdefiniować w kategoriach jednoargumentowej funkcji definiującej listę elementów poprzez wielokrotne zastosowanie ( „rozwijanie” ) oraz predykat określający warunek zakończenia. ${\ displaystyle g: A \ rightarrow B \ razy A}$ ${\ displaystyle B}$ ${\ displaystyle p: A \ rightarrow {\ text {Boolean}}}$

Część katamorficzną można zdefiniować jako kombinację wartości początkowej zagięcia i operatora binarnego używanego do składania. ${\ displaystyle c \ w C}$ ${\ Displaystyle \ oplus: B \ razy C \ rightarrow C}$

Stąd hylomorfizm

{\ Displaystyle h \, a = {\ rozpocząć {przypadków} c & {\ mbox {if}} p \, a \\ b \ oplus h \, a '\, \, \, gdzie \, (b, a' ) = g \, a & {\ mbox {inaczej}} \ end {sprawy}}}

można zdefiniować (przy założeniu odpowiednich definicji & ). ${\ displaystyle p}$ ${\ displaystyle g}$

Notacja

Skrócona notacja dla powyższego hylomorfizmu to . ${\ Displaystyle h = [\! [(c, \ oplus), (g, p)] \!]}$

Hylomorfizmy w praktyce

Listy

Listy są typowymi strukturami danych, ponieważ w naturalny sposób odzwierciedlają liniowe procesy obliczeniowe. Procesy te pojawiają się w powtarzanych ( iteracyjnych ) wywołaniach funkcji. Dlatego czasami konieczne jest wygenerowanie tymczasowej listy wyników pośrednich przed zredukowaniem tej listy do pojedynczego wyniku.

Jednym z przykładów powszechnie spotykanego hylomorfizmu jest silnia kanoniczna .

factorial :: Integer -> Integer
factorial n
  | n == 0 = 1
  | n > 0 = n * factorial (n - 1)

W poprzednim przykładzie (napisanym w Haskell , czysto funkcjonalnym języku programowania ) widać, że ta funkcja, zastosowana do dowolnego danego prawidłowego wejścia, wygeneruje liniowe drzewo wywołań izomorficzne do listy. Na przykład, przyjmując n = 5, da to co następuje:

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

W tym przykładzie anamorficzną częścią procesu jest generowanie drzewa wywołań, które jest izomorficzne z listą [1, 1, 2, 3, 4, 5] . Catamorphism więc jest obliczenie produktu z elementów tej listy. Zatem w zapisie podanym powyżej funkcja silnia może być zapisana jako gdzie i . ${\ Displaystyle {\ tekst {silnia}} = [\! [(1, \ razy), (g, p)] \!]}$ ${\ Displaystyle g \ n = (n, n-1)}$ ${\ Displaystyle p \ n = (n = 0)}$

Drzewa

Jednak termin „hylomorfizm” nie dotyczy wyłącznie funkcji działających na izomorfizmy list. Na przykład hylomorfizm można również zdefiniować przez wygenerowanie nieliniowego drzewa wywołań, które jest następnie zwijane. Przykładem takiej czynności jest funkcja celu wytworzenia n ^th określenie w ciągu Fibonacciego .

 fibonacci :: Integer -> Integer
 fibonacci n
   | n == 0 = 0
   | n == 1 = 1
   | n > 1 = fibonacci (n - 2) + fibonacci (n - 1)

Drzewo wywołań dla fibonacci 4 .

Ta funkcja, ponownie zastosowana do każdego prawidłowego wejścia, wygeneruje drzewo wywołań, które jest nieliniowe. W przykładzie po prawej stronie drzewo wywołań wygenerowane przez zastosowanie fibonacci funkcji do wejścia 4 .

Tym razem anamorfizm jest generacją drzewa wywoławczego izomorficznego z drzewem z węzłami liści, 0, 1, 1, 0, 1 a katamorfizm jest sumą tych węzłów liści.

Zobacz też

Morfizm
Morfizmy F-algebr
- Od algebry początkowej do algebry: katamorfizm
- Od koalgebry do ostatecznej koalgebry: anamorfizm
- Rozszerzenie idei catamorphisms: Paramorphism
- Rozszerzenie idei anamorfizmów: apomorfizm

Bibliografia

Erik Meijer; Maarten Fokkinga; Ross Paterson (1991). „Programowanie funkcjonalne z bananami, soczewkami, kopertami i drutem kolczastym” (PDF) . s. 4, 5.

Languages

In other projects