En programación de computadoras, un anamorfismo es una función que genera una secuencia mediante la aplicación repetida de la función a su resultado anterior. Se comienza con un valor A y se le aplica una función f para obtener B. Luego se aplica f a B para obtener C, y así sucesivamente hasta que se alcanza alguna condición final. El anamorfismo es la función que genera la lista de A, B, C, etc. Puedes pensar en el anamorfismo como desplegar el valor inicial en una secuencia.
La descripción del profano anterior se puede expresar más formalmente en la teoría de categorías : el anamorfismo de un tipo coinductivo denota la asignación de una coalgebra a su morfismo único a la coalgebra final de un endofuntor . Estos objetos se utilizan en la programación funcional a medida que se desarrolla .
El dual categórico (también conocido como opuesto) del anamorfismo es el catamorfismo .
En programación funcional , un anamorfismo es una generalización del concepto de despliegues en listas coinductivas . Formalmente, los anamorfismos son funciones genéricas que pueden construir de forma correcursiva un resultado de un cierto tipo y que está parametrizado por funciones que determinan el siguiente paso de la construcción.
El tipo de datos en cuestión se define como el mayor punto fijo ν X . FX de un funtor F . Por la propiedad universal de las coalgebras finales, existe un morfismo de coalgebra único A → ν X . FX para cualquier otra F -coálgebra a: A → FA . Por lo tanto, se pueden definir funciones de un tipo A _a_ un tipo de datos coinductivo especificando una estructura de coalgebra a en A .
Como ejemplo, el tipo de listas potencialmente infinitas (con elementos de tipo fijo value ) se da como el punto fijo [valor] = ν X . valor × X + 1 , es decir, una lista consta de un valor y otra lista o está vacía. Una (pseudo) definición de Haskell podría verse así:
datos [ valor ] = ( valor : [ valor ]) | [] Es el punto fijo del funtor F value, donde:
datos Quizás a = Sólo a | Nada datos F valor x = Quizás ( valor , x ) Se puede comprobar fácilmente que, efectivamente, el tipo [value]es isomorfo a F value [value]y, por tanto, lo [value]es el punto fijo. (Tenga en cuenta también que en Haskell, los puntos fijos mínimo y mayor de los functores coinciden, por lo tanto, las listas inductivas son lo mismo que las listas coinductivas, potencialmente infinitas).
El anamorfismo para listas (entonces generalmente conocido como unfold ) construiría una lista (potencialmente infinita) a partir de un valor de estado. Normalmente, el despliegue toma un valor de estado xy una función fque produce un par de un valor y un nuevo estado, o un singleton para marcar el final de la lista. Luego, el anamorfismo comenzaría con una primera semilla, calcularía si la lista continúa o termina y, en el caso de una lista no vacía, antepondría el valor calculado a la llamada recursiva al anamorfismo.
Una definición de Haskell de un despliegue, o anamorfismo para listas, llamado ana, es la siguiente:
ana :: ( estado -> Quizás ( valor , estado )) -> estado -> [ valor ] ana f estadoAntiguo = caso f estadoAntiguo de Nada -> [] Solo ( valor , estadoNuevo ) -> valor : ana f estadoNuevo Ahora podemos implementar funciones bastante generales usando ana , por ejemplo una cuenta regresiva:
f :: Int -> Quizás ( Int , Int ) f actual = let oneSmaller = current - 1 in if oneSmaller < 0 entonces Nada más Solo ( oneSmaller , oneSmaller ) Esta función disminuirá un número entero y lo generará al mismo tiempo, hasta que sea negativo, momento en el que marcará el final de la lista. En consecuencia, ana f 3calculará la lista [2,1,0].
Se puede definir un anamorfismo para cualquier tipo recursivo, según un patrón genérico, generalizando la segunda versión de ana para listas.
Por ejemplo, el despliegue de la estructura de datos del árbol.
datos Árbol a = Hoja a | Rama ( árbol a ) a ( árbol a ) es como sigue
ana :: ( b -> Ya sea a ( b , a , b )) -> b -> Árbol a ana desenrollar x = caso desenrollar x de Izquierda a -> Hoja a Derecha ( l , x , r ) -> Rama ( ana desenrollar l ) x ( ana desenrollar r ) Para ver mejor la relación entre el tipo recursivo y su anamorfismo, tenga en cuenta que Treey Listse puede definir así:
nuevo tipo Lista a = Lista { unCons :: Quizás ( a , Lista a )} newtype Árbol a = Árbol { unNode :: Cualquiera de los dos ( Árbol a , a , Árbol a ))} La analogía con anaaparece cambiando el nombre ben su tipo:
nuevo tipo Lista a = Lista { unCons :: Quizás ( a , Lista a )} anaList :: ( lista_a -> Quizás ( a , lista_a )) -> ( lista_a -> Lista a ) newtype Árbol a = Árbol { unNode :: Ya sea a ( Árbol a , a , Árbol a ))} anaTree :: ( árbol_a -> Ya sea a ( árbol_a , a , árbol_a )) -> ( árbol_a -> Árbol a ) Con estas definiciones, el argumento del constructor del tipo tiene el mismo tipo que el tipo de retorno del primer argumento de ana, con las menciones recursivas del tipo reemplazadas por b.
Una de las primeras publicaciones en introducir la noción de anamorfismo en el contexto de la programación fue el artículo Programación funcional con plátanos, lentes, sobres y alambre de púas , [1] de Erik Meijer et al. , que estaba en el contexto del lenguaje de programación Squiggol .
Funciones como zipy iterateson ejemplos de anamorfismos. ziptoma un par de listas, digamos ['a','b','c'] y [1,2,3] y devuelve una lista de pares [('a',1),('b',2) ,('c',3)]. Iteratetoma una cosa, x, y una función, f, de tales cosas a tales cosas, y devuelve la lista infinita que proviene de la aplicación repetida de f, es decir, la lista [x, (fx), (f (fx)), ( f (f (fx))), ...].
zip ( a : como ) ( b : bs ) = si ( como == [] ) || ( bs == [] ) -- || significa 'o' entonces [( a , b )] else ( a , b ) : ( zip as bs ) iterar f x = x : ( iterar f ( f x )) Para probar esto, podemos implementar ambos usando nuestro despliegue genérico, anausando una rutina recursiva simple:
zip2 = ana unsp fin donde fin ( as , bs ) = ( as == [] ) || ( bs == [] ) sin especificar (( a : como ), ( b : bs )) = (( a , b ),( como , bs )) iterar2 f = ana ( \ a -> ( a , f a )) ( \ x -> Falso ) En un lenguaje como Haskell, incluso las funciones abstractas foldy son meros términos definidos, como hemos visto en las definiciones dadas anteriormente unfold.ana
En teoría de categorías , los anamorfismos son el dual categórico de los catamorfismos (y los catamorfismos son el dual categórico de los anamorfismos).
Eso significa lo siguiente. Supongamos que ( A , fin ) es una F -coálgebra final para algún endofunctor F de alguna categoría en sí mismo. Por lo tanto, fin es un morfismo de A a FA , y dado que se supone que es final, sabemos que siempre que ( X , f ) sea otra F -coálgebra (un morfismo f de X a FX ), habrá un homomorfismo único h de ( X , f ) a ( A , fin ), que es un morfismo h de X a A tal que fin . h = Fh . F. Luego, para cada una de estas f denotamos por ana f ese morfismo h especificado de forma única .
En otras palabras, tenemos la siguiente relación definitoria, dadas algunas F , A y fin fijas como se indicó anteriormente:
Una notación para an f que se encuentra en la literatura es . Los soportes utilizados se conocen como soportes de lentes , por lo que a los anamorfismos a veces se les denomina lentes .
![{\displaystyle [\!(f)\!]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/99f892661108ecb4f29635a1f2416b724dff9f80)
{{cite journal}}: Citar diario requiere |journal=( ayuda )