En informática , y en particular en programación funcional , un hilomorfismo es una función recursiva , correspondiente a la composición de un anamorfismo (que primero construye un conjunto de resultados; también conocido como 'desdoblamiento') seguido de un catamorfismo (que luego dobla estos resultados en un valor de retorno final ). La fusión de estos dos cálculos recursivos en un solo patrón recursivo evita la construcción de la estructura de datos intermedia. Este es un ejemplo de deforestación , una estrategia de optimización de programas. Un tipo de función relacionada es un metamorfismo., que es un catamorfismo seguido de un anamorfismo.
Definicion formal
Un hylomorfismo se puede definir en términos de sus partes anamórficas y catamórficas separadas.
La parte anamórfica se puede definir en términos de una función unaria definir la lista de elementos en por aplicación repetida ( "despliegue" ), y un predicado proporcionando la condición de terminación.
La parte catamórfica se puede definir como una combinación de un valor inicial para el pliegue y un operador binario utilizado para realizar el pliegue.
Por lo tanto, un hylomorfismo
puede definirse (asumiendo definiciones apropiadas de Y ).
Notación
Una notación abreviada para el hylomorfismo anterior es .
Hylomorfismos en la práctica
Liza
Las listas son estructuras de datos comunes, ya que reflejan de forma natural procesos computacionales lineales. Estos procesos surgen en llamadas de función repetidas ( iterativas ). Por lo tanto, a veces es necesario generar una lista temporal de resultados intermedios antes de reducir esta lista a un solo resultado.
Un ejemplo de un hilomorfismo que se encuentra comúnmente es la función factorial canónica .
factorial :: Entero -> Entero factorial n | n == 0 = 1 | n > 0 = n * factorial ( n - 1 )
En el ejemplo anterior (escrito en Haskell , un lenguaje de programación puramente funcional ) se puede ver que esta función, aplicada a cualquier entrada válida dada, generará un árbol de llamadas lineal isomorfo a una lista. Por ejemplo, dado n = 5 producirá lo siguiente:
factorial 5 = 5 * (factorial 4) = 120factorial 4 = 4 * (factorial 3) = 24factorial 3 = 3 * (factorial 2) = 6factorial 2 = 2 * (factorial 1) = 2factorial 1 = 1 * (factorial 0) = 1factorial 0 = 1
En este ejemplo, la parte anamórfica del proceso es la generación del árbol de llamadas que es isomórfico a la lista [1, 1, 2, 3, 4, 5]
. El catamorfismo, entonces, es el cálculo del producto de los elementos de esta lista. Por lo tanto, en la notación dada anteriormente, la función factorial se puede escribir como dónde y .
Árboles
Sin embargo, el término 'hilomorfismo' no se aplica únicamente a funciones que actúan sobre isomorfismos de listas. Por ejemplo, un hilomorfismo también se puede definir generando un árbol de llamadas no lineal que luego se colapsa. Un ejemplo de tal función a es la función para generar el n º término de la secuencia de Fibonacci .
fibonacci :: Entero -> Entero fibonacci n | n == 0 = 0 | n == 1 = 1 | n > 1 = fibonacci ( n - 2 ) + fibonacci ( n - 1 )
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/5/5b/Fib_4.png/300px-Fib_4.png)
fibonacci 4
. Esta función, nuevamente aplicada a cualquier entrada válida, generará un árbol de llamadas que no es lineal. En el ejemplo de la derecha, el árbol de llamadas generado al aplicar la fibonacci
función a la entrada 4
.
Esta vez, el anamorfismo es la generación del árbol llamado isomorfo al árbol con nodos foliares 0, 1, 1, 0, 1
y el catamorfismo es la suma de estos nodos foliares.
Ver también
- Morfismo
- Morfismos de F-álgebras
- De un álgebra inicial a un álgebra: catamorfismo
- De una coalgebra a una coalgebra final: anamorfismo
- Extensión de la idea de catamorfismos: paramorfismo
- Extensión de la idea de anamorfismos: apomorfismo
Referencias
- Erik Meijer; Maarten Fokkinga; Ross Paterson (1991). "Programación funcional con plátanos, lentes, sobres y alambre de púas" (PDF) . págs. 4, 5.