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 algún 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 de terminación. El anamorfismo es la función que genera la lista de A, B, C, etc. Puede pensar en el anamorfismo como desplegar el valor inicial en una secuencia.
La descripción anterior del profano puede enunciarse 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 endofunctor . Estos objetos se utilizan en la programación funcional a medida que se despliega .
El dual categórico (también conocido como opuesto) del anamorfismo es el catamorfismo .
Anamorfismos en la programación funcional
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 corecursivamente un resultado de cierto tipo y que se parametrizan mediante 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 -coalgebra a: A → FA . Así, se puede definir funciones de un tipo A _into_ un tipo de datos coinductive especificando una estructura coalgebra una en A .
Ejemplo: listas potencialmente infinitas
Como ejemplo, el tipo de listas potencialmente infinitas (con elementos de un valor de tipo fijo ) se da como el punto fijo [valor] = ν X. valor × X + 1 , es decir, una lista consta de un valor y una lista adicional, o está vacía. Una (pseudo-) Haskell -Definition podría verse así:
datos [ valor ] = ( valor : [ valor ]) | []
Es el punto fijo del functor F value
, donde:
datos Quizás a = Solo a | Nada de datos F valor x = Quizás ( valor , x )
Se puede comprobar fácilmente que, efectivamente, el tipo [value]
es isomórfico y F value [value]
, por tanto, [value]
es el punto fijo. (También tenga en cuenta que en Haskell, los puntos de fijación mínimo y mayor de los functores coinciden, por lo tanto, las listas inductivas son las mismas que las listas coinductivas, potencialmente infinitas).
El anamorfismo para listas (entonces conocido generalmente como desplegar ) construiría una lista (potencialmente infinita) a partir de un valor de estado. Normalmente, el despliegue toma un valor de estado x
y una función f
que 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 estadoOld = caso f estadoOld of Nothing -> [] Just ( value , stateNew ) -> valor : ana f stateNew
Ahora podemos implementar funciones bastante generales usando ana , por ejemplo una cuenta regresiva:
f :: Int -> Quizás ( Int , Int ) f current = let oneSmaller = current - 1 in si 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 3
calculará la lista [2,1,0]
.
Anamorfismos en otras estructuras de datos
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 de árbol
árbol de datos a = Hoja a | Rama ( árbol a ) a ( árbol a )
es como sigue
ana :: ( b -> O 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 Tree
y List
se puede definir así:
newtype List a = List { unCons :: Maybe ( a , List a )} newtype Tree a = Tree { unNode :: O a ( Tree a , a , Tree a ))}
La analogía con ana
aparece cambiando el nombre b
en su tipo:
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 :: O a ( Tree a , a , Tree a ))} anaTree :: ( tree_a -> O a ( tree_a , a , tree_a )) -> ( tree_a -> Tree a )
Con estas definiciones, el argumento para el constructor del tipo tiene el mismo tipo que el tipo de retorno del primer argumento de ana
, con las menciones recursivas del tipo reemplazado por b
.
Historia
Una de las primeras publicaciones que introdujo 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 .
Aplicaciones
Las funciones como zip
y iterate
son ejemplos de anamorfismos. zip
toma un par de listas, digamos ['a', 'b', 'c'] y [1,2,3] y devuelve una lista de pares [('a', 1), ('b', 2) , ('c', 3)]. Iterate
toma 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 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 )) iterar2 f = ana ( \ a -> ( a , f a )) ( \ x -> Falso )
En un lenguaje como Haskell, incluso las funciones abstractas fold
, unfold
y ana
son meramente términos definidos, como hemos visto de las definiciones dadas anteriormente.
Anamorfismos en la teoría de categorías
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. Suponga que ( A , fin ) es una F -coalgebra 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 -coalgebra (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 . Entonces, para cada uno de tales f , denotamos por ana f ese morfismo h específicamente especificado .
En otras palabras, tenemos la siguiente relación definitoria, dadas algunas F , A y fin fijas como arriba:
Notación
Una notación para ana f que se encuentra en la literatura es. Los brackets utilizados se conocen como brackets para lentes , después de lo cual los anamorfismos a veces se denominan lentes .
Ver también
- Morfismo
- Morfismos de F-álgebras
- De un álgebra inicial a un álgebra: catamorfismo
- Un anamorfismo seguido de un catamorfismo: Hylomorphism
- Extensión de la idea de catamorfismos: paramorfismo
- Extensión de la idea de anamorfismos: apomorfismo
Referencias
- ^ Meijer, Erik ; Fokkinga, Maarten; Paterson, Ross (1991). "Programación funcional con plátanos, lentes, sobres y alambre de púas". CiteSeerX 10.1.1.41.125 . Cite journal requiere
|journal=
( ayuda )