En programación informática, 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 una condición de terminación. El anamorfismo es la función que genera la lista de A, B, C, etc. Se puede pensar en el anamorfismo como el desarrollo del valor inicial en una secuencia.
La descripción anterior para el profano se puede formular de manera más formal en la teoría de categorías : el anamorfismo de un tipo coinductivo denota la asignación de una coálgebra a su morfismo único en la coálgebra final de un endofunctor . Estos objetos se utilizan en la programación funcional como unfolds .
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 desdoblamientos en listas coinductivas . Formalmente, los anamorfismos son funciones genéricas que pueden construir de forma recursiva un resultado de un tipo determinado y que está parametrizado por funciones que determinan el siguiente paso único 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 _en_ un tipo de datos coinductivo especificando una estructura de coalgebra a en A .
Como ejemplo, el tipo de listas potencialmente infinitas (con elementos de un tipo fijo valor ) 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 Tal vez a = Solo a | Nada datos F valor x = Tal vez ( valor , x ) Se puede comprobar fácilmente que, efectivamente, el tipo [value]es isomorfo a F value [value], y por lo tanto [value]es el punto fijo. (Obsérvese también que en Haskell, los puntos fijos mínimo y máximo de los funtores coinciden, por lo tanto, las listas inductivas son lo mismo que las listas coinductivas, potencialmente infinitas).
El anamorfismo para listas (conocido entonces como unfold ) construiría una lista (potencialmente infinita) a partir de un valor de estado. Normalmente, el unfold 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. El anamorfismo comenzaría entonces 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 -> Maybe ( Int , Int ) f actual = let oneSmaller = actual - 1 in si oneSmaller < 0 entonces Nada más Solo ( oneSmaller , oneSmaller ) Esta función decrementará un entero y lo mostrará al mismo tiempo, hasta que sea negativo, momento en el cual 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 - > O bien a ( b , a , b )) -> b -> Árbol a ana unspool x = caso unspool x de Izquierda a -> Hoja a Derecha ( l , x , r ) -> Rama ( ana unspool l ) x ( ana unspool r ) Para ver mejor la relación entre el tipo recursivo y su anamorfismo, observe que Treey Listse puede definir así:
nuevo tipo Lista a = Lista { unCons :: Maybe ( a , Lista a )} newtype Árbol a = Árbol { unNodo :: Either a ( Árbol a , a , Árbol a ))} La analogía con anaaparece al renombrar 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 { unNodo :: Either a ( Árbol a , a , Árbol a ))} anaTree :: ( árbol_a -> Either 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 Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire , [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 : as ) ( b : bs ) = if ( as == [] ) || ( 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, ana, usando una rutina recursiva simple:
zip2 = ana unsp fin donde fin ( as , bs ) = ( as == [] ) || ( bs == [] ) unsp (( a : as ), ( b : bs )) = (( a , b ),( as , bs )) iterate2 f = ana ( \ a -> ( a , f a )) ( \ x -> Falso ) En un lenguaje como Haskell, incluso las funciones abstractas fold, unfoldy anason simplemente términos definidos, como hemos visto en las definiciones dadas anteriormente.
En la 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).
Esto significa lo siguiente. Supóngase que ( A , fin ) es una F -coálgebra final para algún endofuntor F de alguna categoría en sí mismo. Por lo tanto, fin es un morfismo de A a FA , y como 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 ), es decir, un morfismo h de X a A tal que fin . h = Fh . f . Entonces, para cada una de esas f, denotamos por una f ese morfismo h especificado de forma única .
En otras palabras, tenemos la siguiente relación definitoria, dados unos F , A y fin fijos como los anteriores:
En la literatura se encuentra una notación para ana f . Los corchetes utilizados se conocen como corchetes de lente , por lo que los anamorfismos a veces se denominan lentes .
![{\estilo de visualización [\!(f)\!]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/99f892661108ecb4f29635a1f2416b724dff9f80)
{{cite journal}}: Requiere citar revista |journal=( ayuda )