Anamorfismo

En programación, un anamorfismo es una función que genera una secuencia mediante la aplicación repetida de la misma a su resultado anterior. Se parte de 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 cumple 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 despliegue del valor inicial en una secuencia.

La descripción anterior para el laico se puede expresar 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 único morfismo a la coálgebra final de un endofunctor . Estos objetos se utilizan en la programación funcional como despliegues .

El dual categórico (la función que más naturalmente se considera el "opuesto") del anamorfismo es el catamorfismo .

En programación funcional , un anamorfismo es una generalización del concepto de despliegue en listas coinductivas . Formalmente, los anamorfismos son funciones genéricas que pueden construir de forma corecursiva un resultado de un tipo determinado y que están parametrizadas por funciones que determinan el siguiente paso de la construcción.

El tipo de datos en cuestión se define como el punto fijo más grande ν X . FX de un functor F . Por la propiedad universal de las coálgebras finales, hay un morfismo de coálgebra ú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 coálgebra a en A .

datos [ valor ] = ( valor : [ valor ]) | []

datos Quizás a = Solo a | Nada datos F valor x = Quizás ( valor , x )

ana :: ( estado -> Quizás ( valor , estado )) -> estado -> [ valor ] ana f estadoAntiguo = caso f estadoAntiguo de Nada -> [] Solo ( valor , estadoNuevo ) -> valor : ana f estadoNuevo

f :: Int -> Maybe ( Int , Int ) f actual = let oneSmaller = actual - 1 en si oneSmaller < 0 entonces Nada más Just ( oneSmaller , oneSmaller )

Datos Árbol a = Hoja a | Rama ( Árbol a ) a ( Árbol a )

ana :: ( b -> Either a ( b , a , b )) -> b -> Tree a ana unspool x = case unspool x of Left a -> Leaf a Right ( l , x , r ) -> Branch ( ana unspool l ) x ( ana unspool r )

newtype List a = List { unCons :: Maybe ( a , List a )}nuevo tipo Árbol a = Árbol { unNodo :: O bien a ( Árbol a , a , Árbol a ))}

newtype List a = List { unCons :: Maybe ( a , List a )} anaList :: ( list_a -> Maybe ( a , list_a )) -> ( list_a -> List a )newtype Tree a = Tree { unNode :: Either a ( Tree a , a , Tree a ))} anaTree :: ( tree_a -> Either a ( tree_a , a , tree_a )) -> ( tree_a -> Tree a )

Una de las primeras publicaciones que introdujo 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 se encontraba 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 un objeto, x, y una función, f, de tales objetos a tales objetos, y devuelve la lista infinita que resulta de la aplicación repetida de f, es decir, la lista [x, (fx), (f (fx)), (f (f (fx))), ...].

zip ( a : as ) ( b : bs ) = si ( as == [] ) || ( bs == [] ) -- || significa 'o' entonces [( a , b )] sino ( a , b ) : ( zip como bs ) iterar f x = x : ( iterar f ( f x ))

Para demostrar 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 -> False )

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).

Eso significa lo siguiente. Supongamos que ( A , fin ) es una F -coalgebra final para algún endofunctor F de alguna categoría en sí misma. 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 -coalgebra (un morfismo f de X a FX ), habrá un único homomorfismo 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 f denotamos por ana f ese morfismo h especificado de forma única .

En otras palabras, tenemos la siguiente relación definitoria, dados algunos valores fijos de F , A y fin como se indicó anteriormente:

• ${\displaystyle h=\mathrm {ana} \ f}$
• ${\displaystyle \mathrm {fin} \circ h=Fh\circ f}$

• Morfismo
• Morfismos de F-álgebras
  • De un álgebra inicial a un álgebra: Catamorfismo
  • Anamorfismo seguido de catamorfismo: Hilemorfismo
  • Extensión de la idea de catamorfismos: Paramorfismo
  • Extensión de la idea de anamorfismos: Apomorfismo

• Anamorfismos en Haskell