En informática , y en particular en programación funcional , un hilemorfismo 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 pliega estos resultados en un valor de retorno final ). La fusión de estos dos cálculos recursivos en un único patrón recursivo evita entonces construir 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.
Un hilomorfismo 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 que define la lista de elementos por aplicación repetida ( "despliegue" ) y un predicado que proporciona 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.
Así pues, un hilemorfismo
puede definirse (asumiendo definiciones apropiadas de & ).
Una notación abreviada para el hilemorfismo anterior es .
Las listas son estructuras de datos comunes, ya que reflejan de forma natural procesos computacionales lineales. Estos procesos surgen en llamadas de funciones 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 comúnmente encontrado es la función factorial canónica .
![{\displaystyle h=[\![(c,\oplus ),(g,p)]\!]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d710f0a6a32d21958abc3f5a7d456e353a1413aa)
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 isomorfo 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 puede escribirse como donde y .
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 puede definirse generando un árbol de llamadas no lineal que luego se colapsa. Un ejemplo de una función de este tipo es la función para generar el término n de la secuencia de Fibonacci .
![{\displaystyle {\text{factorial}}=[\![(1,\times ),(g,p)]\!]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2b3955a228af7d336b7be7c9fa4baf674bc7c42b)
fibonacci :: Entero -> Entero fibonacci n | norte == 0 = 0 | norte == 1 = 1 | norte > 1 = fibonacci ( norte - 2 ) + fibonacci ( norte - 1 ) 
fibonacci 4Esta función, aplicada nuevamente 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 fibonaccifunción a la entrada 4.
Esta vez, el anamorfismo es la generación del árbol de llamadas isomorfo al árbol con nodos hoja 0, 1, 1, 0, 1 y el catamorfismo la suma de estos nodos hoja.