Hylomorfisme (informatica)

In de informatica en met name in het functioneel programmeren is een hylomorfisme een recursieve functie, die overeenkomt met de samengestelde functie van een anamorfisme (die eerst een verzameling resultaten opbouwt; ook bekend als 'unfolding') en een catamorfisme (die vervolgens deze resultaten in een finale returnwaarde vouwt). Een mix van deze twee recursieve berekeningen in een enkel recursieve patroon voorkomt dat men een tussentijdse datastructuur moet bouwen. Dit is een bijzondere vorm van de optimaliserende programma transformatie technieken, die gezamenlijk bekendstaan als ontbossing. De categorische duale van een hylomorfisme wordt een metamorfisme genoemd en bestaat uit een catamorfisme gevolgd door een anamorfisme.

Etymologie

Het woord hylomorfisme was reeds bij de oude Grieken bekend. Het is afgeleid van het Oudgriekse ὕλη ("hulē" = stof) en μορφή ("morphē" = vorm). In de leer van Aristoteles en de scholastiek betekent hylomorfisme dat 'wat bestaat en verandert' is terug te voeren op twee principes: enerzijds hetgeen 'waaruit het bestaat', ofwel de stof zelf, en anderzijds de vorm die de stof aanneemt. Omdat deze definitie zelf min of meer recursief is, is de term overgenomen in de informatica.

Formele definitie

Een hylomorfisme $h\ :A\rightarrow C$ kan worden gedefinieerd in termen van afzonderlijke anamorfe en catamorfe delen.

Het anamorfe gedeelte kan worden gedefinieerd in termen van een unaire functie $g\ :A\rightarrow B||A$ die een lijst definieert, en een predicaat $p\ :A\rightarrow Boolean$ die voorziet in de stopconditie (Engels: terminating condition).

Het catamorfe gedeelte kan worden gedefinieerd als een combinatie van een initieel gedeelte $c\ \in C$ voor de fold een binaire operatie $\oplus :B||C\rightarrow C$, die wordt gebruikt om de fold te bewerken.

Dus een hylomorfisme

$h\ a={\begin{cases}c&{\mbox{indien }}pa\\b\oplus ha'&{\mbox{anders}}\end{cases}}$

(waar $(b,\ a')=ga$) kan worden gedefinieerd (uitgaande van toepasselijke definities van p, g, h).

Notatie

Een verkorte notatiewijze voor het bovenstaande hylomorfisme is $h=[\![(c,\oplus ),(g,p)]\!]$.

Hylomorfismen in de praktijk

Lijsten

Lijsten zijn gebruikelijke datastructuren (dit aangezien zij van nature voorkomen, wanneer een lineair proces moet worden toegepast op een aantal inputs); als zodanig is het soms nodig (of verdient het in ieder geval de voorkeur) om een tijdelijke lijst van tussentijdse resultaten aan te maken alvorens een operatie uit te voeren die deze lijst terugbrengt tot het definitieve resultaat.

Een voorbeeld van een veelvoorkomend hylomorfise is de canonieke faculteit-functie.

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

In het vorige voorbeeld (geschreven in Haskell, een puur functionele programmeertaal) kan men zien dat deze functie, toegepast op een willekeurig gegeven, valide input, een lineaire aanroepboom zal genereren, die isomorf is met de lijst.

Gegeven bijvoorbeeld n = 5 zal het onderstaande resultaat worden geproduceerd:

 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

In dit voorbeeld is het anamorfe gedeelte van het proces de generatie van de aanroepboom die isomorf is aan de lijst [1, 1, 2, 3, 4, 5]. Het catamorfisme is dan de berekening van het product van de elementen van deze lijst. Zo is in de bovenstaande gegeven notatie kan de faculteit functie worden geschreven als

${\mathit {factorial}}=[\![(1,\times ),(g,p)]\!]$ waar $g\ n=(n,n-1)$ en $p\ n=(n=0)$.

Bomen

Het moet echter worden opgemerkt dat de term "hylomorfisme" niet alleen geldt voor functies die inwerken op isomorfismen van lijsten. Een hylomorfisme kan bijvoorbeeld ook worden gedefinieerd door een niet-lineaire aanroepboom te genereren die vervolgens wordt ingeklapt. Een voorbeeld van een dergelijke functie is de functie voor het genereren van n^th term van de rij van Fibonacci.

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

Deze functie, opnieuw toegepast op enige geldige input, zal een niet-lineaire aanroepboom genereren. In het onderstaande voorbeeld, ziet de aanroepboom die gegenereerd wordt door de fibonacci functie toe te passen op de input 4.

                    fib 4 ← 1 + 2 = 3
                   /     \
 0 + 1 = 1 → fib 2       fib 3 ← 1 + 1 = 2
              /  \        /   \
          fib 0  fib 1 fib 1  fib 2 ← 0 + 1 = 1
            |     |    |      /\
            0     1    1     /  \
                          fib 0  fib 1
                           |      |
                           0      1

Deze keer is het anamorfisme de generatie van de aanroepboom, die isomorf is met de boom met bladknopen 0, 1, 1, 0, 1 en het catamorfisme de sommatie van deze bladknopen.

Zie ook

• Paramorfisme

Referenties

• Erik Meijer, Maarten Fokkinga, Ross Paterson, Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire (Functioneel programmeren met bananen, lenzen, enveloppen en prikkeldraad) pagina's 4-5 (1991).