Hylomorphism (informatica) - Hylomorphism (computer science)

In informatica , in particolare programmazione funzionale , un hylomorphism è ricorsiva funzione, corrispondente alla composizione di un anamorfismo (che costruisce la prima di una serie di risultati, anche noto come 'dispiegamento') seguito da un catamorphism (che poi si piega questi risultati in un valore di ritorno finale ). La fusione di questi due calcoli ricorsivi in un unico modello ricorsivo evita quindi di costruire la struttura dati intermedia. Questo è un esempio di deforestazione , una strategia di ottimizzazione del programma. Un tipo correlato di funzione è un metamorfismo , che è un catamorfismo seguito da un anamorfismo.

Definizione formale

Un iomorfismo può essere definito in termini di parti separate anamorfiche e catamorfiche. ${\ displaystyle h: A \ rightarrow C}$

La parte anamorfica può essere definita in termini di una funzione unaria che definisce l'elenco di elementi in un'applicazione ripetuta ( "spiegamento" ) e un predicato che fornisce la condizione di terminazione. ${\ displaystyle g: A \ rightarrow B \ times A}$ ${\ displaystyle B}$ ${\ displaystyle p: A \ rightarrow {\ text {Boolean}}}$

La parte catamorfica può essere definita come una combinazione di un valore iniziale per la piega e un operatore binario utilizzato per eseguire la piega. ${\ displaystyle c \ in C}$ ${\ displaystyle \ oplus: B \ times C \ rightarrow C}$

Quindi un iomorfismo

{\ displaystyle h \, a = {\ begin {case} c & {\ mbox {if}} p \, a \\ b \ oplus h \, a '\, \, \, dove \, (b, a' ) = g \, a & {\ mbox {altrimenti}} \ end {case}}}

può essere definito (assumendo definizioni appropriate di & ). ${\ displaystyle p}$ ${\ displaystyle g}$

Notazione

Una notazione abbreviata per l'ilomorfismo di cui sopra è . ${\ displaystyle h = [\! [(c, \ oplus), (g, p)] \!]}$

Iomorfismi in pratica

Liste

Le liste sono strutture di dati comuni poiché riflettono naturalmente i processi computazionali lineari. Questi processi sorgono in chiamate di funzioni ripetute ( iterative ). Pertanto, a volte è necessario generare un elenco temporaneo di risultati intermedi prima di ridurre questo elenco a un unico risultato.

Un esempio di un ilomorfismo comunemente riscontrato è la funzione fattoriale canonica .

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

Nell'esempio precedente (scritto in Haskell , un linguaggio di programmazione puramente funzionale ) si può vedere che questa funzione, applicata a qualsiasi dato input valido, genererà un albero di chiamate lineare isomorfo a una lista. Ad esempio, dato n = 5 produrrà quanto segue:

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 questo esempio, la parte anamorfica del processo è la generazione dell'albero delle chiamate che è isomorfo alla lista [1, 1, 2, 3, 4, 5] . Il catamorfismo, quindi, è il calcolo del prodotto degli elementi di questa lista. Quindi, nella notazione data sopra, la funzione fattoriale può essere scritta come dove e . ${\ displaystyle {\ text {factorial}} = [\! [(1, \ times), (g, p)] \!]}$ ${\ displaystyle g \ n = (n, n-1)}$ ${\ displaystyle p \ n = (n = 0)}$

Alberi

Tuttavia, il termine "ilomorfismo" non si applica esclusivamente alle funzioni che agiscono sugli isomorfismi delle liste. Ad esempio, un iomorfismo può anche essere definito generando un albero delle chiamate non lineare che viene poi compresso. Un esempio di tale funzione a è la funzione di generare il n ^esimo termine della sequenza di Fibonacci .

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

Chiama l'albero per fibonacci 4 .

Questa funzione, ancora una volta applicata a qualsiasi input valido, genererà un albero delle chiamate non lineare. Nell'esempio a destra, l'albero delle chiamate generato applicando la fibonacci funzione all'input 4 .

Questa volta, l'anamorfismo è la generazione del call tree isomorfo all'albero con nodi fogliari 0, 1, 1, 0, 1 e il catamorfismo la sommatoria di questi nodi foglia.

Guarda anche

Morfismo
Morfismi delle F-algebre
- Da un'algebra iniziale a un'algebra: Catamorfismo
- Da una coalgebra a una coalgebra finale: l' anamorfismo
- Estensione del concetto di catamorphisms: paramorfismi
- Estensione dell'idea di anamorfismi: apomorfismo

Riferimenti

Erik Meijer; Maarten Fokkinga; Ross Paterson (1991). "Programmazione funzionale con banane, lenti, buste e filo spinato" (PDF) . pagg. 4, 5.

Languages

In other projects