Hispanopedia Wiki
Articulo de referencia

Hilemorfismo (informática)

En informática , y en particular en programación funcional , un hilemorfismo es una función recursiva que corresponde a la composición de un anamorfismo (que primero construye u...

Hispanopedia WikiContenido en espanolLectura gratuita

En informática , y en particular en programación funcional , un hilemorfismo es una función recursiva que corresponde a la composición de un anamorfismo (que primero construye un conjunto de resultados; también conocido como "desplegamiento") 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 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 el metamorfismo , que consiste en un catamorfismo seguido de un anamorfismo.

Definición formal

Un hilomorfismoh:A→do{\displaystyle h:A\rightarrow C}puede definirse 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.gramo:A→B×A{\displaystyle g:A\rightarrow B\times A}definiendo la lista de elementos enB{\displaystyle B}mediante aplicación repetida ( "desplegamiento" ) y un predicadopag:A→Booleano{\displaystyle p:A\rightarrow {\text{Booleano}}}proporcionando la condición de terminación.

La parte catamórfica puede definirse como una combinación de un valor inicial.do∈do{\displaystyle c\in C}para el pliegue y un operador binario⊕:B×do→do{\displaystyle \oplus :B\times C\rightarrow C}utilizado para realizar el pliegue.

Por lo tanto, un hilemorfismo

ha={dosi pagab⊕ha′dónde(b,a′)=gramoade lo contrario{\displaystyle h\,a={\begin{cases}c&{\mbox{si }}p\,a\\b\oplus h\,a'\,\,\,{\mbox{donde}}\,(b,a')=g\,a&{\mbox{en otro caso}}\end{cases}}}

puede definirse (suponiendo definiciones apropiadas depag{\displaystyle p}&gramo{\displaystyle g}).

Notación

Una notación abreviada para el hilemorfismo anterior esh=[[(do,⊕),(gramo,pag)]]{\displaystyle h=[\![(c,\oplus ),(g,p)]\!]}.

Hilemorfismos en la práctica

Liza

Las listas son estructuras de datos comunes, ya que reflejan de forma natural los procesos computacionales lineales. Estos procesos surgen en llamadas a funciones repetidas ( iterativas ). Por lo tanto, a veces es necesario generar una lista temporal de resultados intermedios antes de reducirla a un único resultado.

Un ejemplo de hilemorfismo común 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 observar que esta función, aplicada a cualquier entrada válida, generará un árbol de llamadas lineal isomorfo a una lista. Por ejemplo, dado n = 5, producirá lo siguiente:

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

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. Así, en la notación dada anteriormente, la función factorial se puede escribir comofactorial=[[(1,×),(gramo,pag)]]{\displaystyle {\text{factorial}}=[\![(1,\times ),(g,p)]\!]}dóndegramo norte=(norte,norte−1){\displaystyle g\ n=(n,n-1)}ypag norte=(norte=0){\displaystyle p\ n=(n=0)}.

Árboles

Sin embargo, el término «hilemorfismo» no se aplica únicamente a funciones que actúan sobre isomorfismos de listas. Por ejemplo, un hilemorfismo también puede definirse generando un árbol de llamadas no lineal que luego se colapsa. Un ejemplo de dicha función es la que genera el enésimo término de la sucesión de Fibonacci .

fibonacci :: Entero -> Entero fibonacci n | norte == 0 = 0 | norte == 1 = 1 | norte > 1 = fibonacci ( norte - 2 ) + fibonacci ( norte - 1 )
Árbol de llamadas parafibonacci 4

Esta función, aplicada nuevamente a cualquier entrada válida, generará un árbol de llamadas no lineal. En el ejemplo de la derecha, el árbol de llamadas se genera al aplicar la fibonaccifunción a la entrada 4.

En este caso, el anamorfismo es la generación del árbol de llamadas isomorfo al árbol con nodos hoja0, 1, 1, 0, 1 y el catamorfismo la suma de estos nodos hoja.

Véase también

Referencias

  • Erik Meijer; Martín Fokkinga; Ross Paterson (1991). «Programación Funcional con Plátanos, Lentes, Sobres y Alambre de Púas» (PDF) . págs.4  , 5.
  • Hilemorfismos en Haskell
  • Más hilemorfismos en Haskell