Hispanopedia Wiki
Articulo de referencia

Catamorfismo

En la programación funcional , el concepto de catamorfismo (del griego antiguo : κατά "hacia abajo" y μορφή "forma, figura") denota el homomorfismo único de un álgebra inicial e...

Hispanopedia WikiContenido en espanolLectura gratuita

En la programación funcional , el concepto de catamorfismo (del griego antiguo : κατά "hacia abajo" y μορφή "forma, figura") denota el homomorfismo único de un álgebra inicial en otra álgebra.

Los catamorfismos proporcionan generalizaciones de pliegues de listas a tipos de datos algebraicos arbitrarios , que pueden describirse como álgebras iniciales . El concepto dual es el de anamorfismo , que generaliza despliegues . Un hilemorfismo es la composición de un anamorfismo seguido de un catamorfismo.

Definición

Consideremos un inicioF{\displaystyle F}-álgebra(A,inorte){\displaystyle (A,in)}para algún endofunctorF{\displaystyle F}de alguna categoría en sí misma. Aquíinorte{\displaystyle en}es un morfismo deFA{\displaystyle FA}aA{\displaystyle A}. Dado que es inicial, sabemos que siempre que(incógnita,F){\displaystyle (X,f)}es otroF{\displaystyle F}-álgebra, es decir, un morfismoF{\displaystyle f}deFincógnita{\displaystyle FX}aincógnita{\displaystyle X}, existe un homomorfismo únicoh{\displaystyle h}de(A,inorte){\displaystyle (A,in)}a(incógnita,F){\displaystyle (X,f)}. Por la definición de la categoría deF{\displaystyle F}-álgebra, estoh{\displaystyle h}corresponde a un morfismo deA{\displaystyle A}aincógnita{\displaystyle X}, convencionalmente también se denotah{\displaystyle h}, de tal manera queh∘inorte=F∘Fh{\displaystyle h\circ in=f\circ Fh}. En el contexto deF{\displaystyle F}-álgebra, el morfismo especificado de forma única a partir del objeto inicial se denota pordoata F{\displaystyle \mathrm {cata} \f}y por lo tanto se caracteriza por la siguiente relación:

  • h=doata F{\displaystyle h=\mathrm {cata} \f}
  • h∘inorte=F∘Fh{\displaystyle h\circ in=f\circ Fh}

Terminología e historia

Otra notación que se encuentra en la literatura es(|F|){\displaystyle (\!|f|\!)}Los corchetes abiertos utilizados se conocen como corchetes banana , por lo que a veces se hace referencia a los catamorfismos como bananas , como se menciona en Erik Meijer et al . [ 1 ] Una de las primeras publicaciones que introdujo la noción de catamorfismo en el contexto de la programación fue el artículo “Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire”, de Erik Meijer et al. , [ 1 ] que se encontraba en el contexto del formalismo Squiggol . La definición categórica general fue dada por Grant Malcolm . [ 2 ] [ 3 ]

Ejemplos

Presentamos una serie de ejemplos y, a continuación, un enfoque más global de los catamorfismos en el lenguaje de programación Haskell .

Catamorfismo para álgebra de posibilidad

Consideremos el functor Maybedefinido en el siguiente código Haskell:

datos Quizás a = Nada | Solo un -- Quizás tipoclase Functor f donde -- clase para functores fmap :: ( a -> b ) -> ( f a -> f b ) -- acción del functor sobre morfismosinstancia Functor Maybe donde -- convierte Maybe en un functor fmap g Nothing = Nothing fmap g ( Just x ) = Just ( g x )

El objeto inicial del Maybe-Algebra es el conjunto de todos los objetos de tipo número natural Natjunto con el morfismo inidefinido a continuación: [ 4 ] [ 5 ]

datos Nat = Cero | Succ Nat -- tipo de número naturalini :: Maybe Nat -> Nat -- objeto inicial del álgebra Maybe (con un ligero abuso de notación) ini Nothing = Zero ini ( Just n ) = Succ n

El catamapa se puede definir de la siguiente manera: [ 5 ]

cata :: ( Quizás b -> b ) -> ( Nat -> b ) cata g Cero = g ( fmap ( cata g ) Nada ) -- Nota: fmap (cata g) Nada = g Nada y Cero = ini(Nada) cata g ( Succ n ) = g ( fmap ( cata g ) ( Solo n )) -- Nota: fmap (cata g) (Solo n) = Solo (cata gn) y Succ n = ini(Solo n)

Como ejemplo, consideremos el siguiente morfismo:

g :: Maybe String -> String g Nothing = "¡ve!" g ( Just str ) = "espera..." ++ str

Entonces cata g ((Succ. Succ . Succ) Zero)se evaluará a "espera... espera... espera... ¡vamos!".

Lista plegada

Para un tipo fijo, aconsidérese el functor MaybeProd adefinido por lo siguiente:

datos MaybeProd a b = Nothing | Just ( a , b ) -- (a,b) es el tipo de producto de a y bclase Functor f donde -- clase para functores fmap :: ( a -> b ) -> ( f a -> f b ) -- acción del functor sobre morfismosinstancia Functor ( MaybeProd a ) donde -- convierte MaybeProd a en un functor, la funtorialidad está solo en la segunda variable de tipo fmap g Nothing = Nothing fmap g ( Just ( x , y )) = Just ( x , g y )

El álgebra inicial de MaybeProd aviene dada por las listas de elementos de tipo ajunto con el morfismo inidefinido a continuación: [ 6 ]

Lista de datos a = ListaVacía | Cons a ( Lista a )ini :: MaybeProd a ( Lista a ) -> Lista a -- álgebra inicial de MaybeProd a ini Nothing = EmptyList ini ( Just ( n , l )) = Cons n l

El catamapa se puede definir mediante:

cata :: ( MaybeProd a b -> b ) -> ( List a -> b ) cata g EmptyList = g ( fmap ( cata g ) Nothing ) -- Nota: ini Nothing = EmptyList cata g ( Cons s l ) = g ( fmap ( cata g ) ( Just ( s , l ))) -- Nota: Cons sl = ini (Just (s,l))

Nótese también que cata g (Cons s l) = g (Just (s, cata g l)). Como ejemplo, considérese el siguiente morfismo:

g :: MaybeProd Int Int -> Int g Nothing = 3 g ( Just ( x , y )) = x * y

cata g (Cons 10 EmptyList)se evalúa a 30. Esto se puede ver al expandir cata g (Cons 10 EmptyList) = g (Just (10,cata g EmptyList)) = 10*(cata g EmptyList) = 10*(g Nothing) = 10*3.

De la misma manera se puede demostrar que eso cata g (Cons 10 (Cons 100 (Cons 1000 EmptyList)))se evaluará como 10*(100*(1000*3)) = 3.000.000.

El catamapa está estrechamente relacionado con el pliegue derecho (véase Plegado (función de orden superior) ) de listas foldrList. El morfismo liftdefinido por

levantar :: ( a -> b -> b ) -> b -> ( MaybeProd a b -> b ) levantar g b0 Nada = b0 levantar g b0 ( Just ( x , y )) = g x y

Se relaciona catacon el pliegue derecho foldrListde las listas a través de:

foldrList :: ( a -> b -> b ) -> b -> List a -> b foldrList fun b0 = cata ( lift fun b0 )

La definición cataimplica que foldrListes el pliegue derecho y no el pliegue izquierdo. Como ejemplo: foldrList (+) 1 (Cons 10 (Cons 100 (Cons 1000 EmptyList)))se evaluará a 1111 y foldrList (*) 3 (Cons 10 (Cons 100 (Cons 1000 EmptyList))a 3.000.000.

Pliegue del árbol

Para un tipo fijo a, considere el functor que asigna tipos ba un tipo que contiene una copia de cada término de aasí como todos los pares de b(términos del tipo producto de dos instancias del tipo b). Un álgebra consiste en una función a b, que actúa sobre un atérmino o dos btérminos. Esta fusión de un par puede codificarse como dos funciones de tipo a -> brespectivamente b -> b -> b.

type TreeAlgebra a b = ( a -> b , b -> b -> b ) -- la función de "dos casos" se codifica como (f, g) data Tree a = Leaf a | Branch ( Tree a ) ( Tree a ) -- que resulta ser el álgebra inicial foldTree :: TreeAlgebra a b -> ( Tree a -> b ) -- los catamorfismos mapean de (Tree a) a b foldTree ( f , g ) ( Leaf x ) = f x foldTree ( f , g ) ( Branch left right ) = g ( foldTree ( f , g ) left ) ( foldTree ( f , g ) right )
treeDepth :: TreeAlgebra a Integer -- un álgebra f para números, que funciona para cualquier tipo de entrada treeDepth = ( const 1 , \ i j -> 1 + max i j ) treeSum :: ( Num a ) => TreeAlgebra a a -- un álgebra f, que funciona para cualquier tipo de número treeSum = ( id , ( + ))

Caso general

Estudios teóricos de categorías más profundos sobre las álgebras iniciales revelan que el álgebra F obtenida al aplicar el functor a su propia álgebra inicial es isomorfa a ella.

Los sistemas de tipos fuertes nos permiten especificar abstractamente el álgebra inicial de un functor fcomo su punto fijo a = fa . Los catamorfismos definidos recursivamente ahora se pueden codificar en una sola línea, donde el análisis de casos (como en los diferentes ejemplos anteriores) está encapsulado por fmap. Dado que el dominio de este último son objetos en la imagen de f, la evaluación de los catamorfismos salta de un lado a otro entre ay f a.

tipo Álgebra f a = f a -> a -- las f-álgebras genéricasnewtype Fix f = Iso { invIso :: f ( Fix f ) } -- nos da el álgebra inicial para el functor fcata :: Functor f => Algebra f a -> ( Fix f -> a ) -- catamorfismo de Fix f a a cata alg = alg . fmap ( cata alg ) . invIso -- tenga en cuenta que invIso y alg se mapean en direcciones opuestas

Ahora, volvamos al primer ejemplo, pero esta vez pasando el functor Maybe a Fix. La aplicación repetida del functor Maybe genera una cadena de tipos que, sin embargo, pueden unirse mediante el isomorfismo del teorema del punto fijo. Introducimos el término zero, que surge de Maybe, Nothinge identificamos una función sucesora con la aplicación repetida de Just. De esta forma surgen los números naturales.

tipo Nat = Fix Maybe zero :: Nat zero = Iso Nothing -- cada 'Maybe a' tiene un término Nothing, e Iso lo asigna a un sucesor :: Nat -> Nat successor = Iso . Just -- Just asigna a a 'Maybe a' e Iso lo asigna de vuelta a un nuevo término
pleaseWait :: Álgebra Quizás Cadena -- de nuevo el tonto ejemplo de f-álgebra de arriba pleaseWait ( Solo cadena ) = "espera.. " ++ cadena pleaseWait Nada = "¡adelante!"

Nuevamente, lo siguiente se evaluará como "espera... espera... espera... espera... ¡adelante!":cata pleaseWait (successor.successor.successor.successor $ zero)

Y ahora volvemos al ejemplo del árbol. Para ello debemos proporcionar el tipo de datos del contenedor del árbol para poder configurarlo fmap(no tuvimos que hacerlo para el Maybefunctor, ya que forma parte del preludio estándar).

datos Tcon a b = TconL a | TconR b b instancia Functor ( Tcon a ) donde fmap f ( TconL x ) = TconL x fmap f ( TconR y z ) = TconR ( f y ) ( f z )
tipo Árbol a = Fix ( Tcon a ) -- el álgebra inicial fin :: a -> Árbol a fin = Iso . TconL encuentro :: Árbol a -> Árbol a -> Árbol a encuentro l r = Iso $ TconR l r
treeDepth :: Álgebra ( Tcon a ) Entero -- de nuevo, el ejemplo de f-álgebra treeDepth ( TconL x ) = 1 treeDepth ( TconR y z ) = 1 + max y z

Lo siguiente se evaluará a 4:cata treeDepth $ meet (end "X") (meet (meet (end "YXX") (end "YXY")) (end "YY"))

Véase también

Referencias

  1. 1 2 Meijer, Erik; Fokkinga, Maarten; Paterson, Ross (1991), "Programación funcional con plátanos, lentes, sobres y alambre de púas" , en Hughes, John (ed.), Lenguajes de programación funcional y arquitectura de computadoras , vol.  523, Springer Berlin Heidelberg, pp. 124–144 , doi : 10.1007/3540543961_7 , ISBN  978-3-540-54396-1, S2CID 11666139 , consultado el 07-05-2020 
  2. ↑ Malcolm, Grant Reynold (1990), Tipos de datos algebraicos y transformación de programas (PDF) (Tesis doctoral), Universidad de Groningen, archivado del original (PDF) el 10 de junio de 2015.
  3. ↑ Malcolm, Grant (1990), "Estructuras de datos y transformación de programas", Science of Computer Programming , vol. 14, n.º 2–3 , pp. 255–279 , doi : 10.1016/0167-6423(90)90023-7   .
  4. ↑ "Álgebra inicial de un endofunctor en nLab" .
  5. 1 2 "Número natural en nLab" .
  6. ↑ "Álgebra inicial de un endofunctor en nLab" .

Lecturas adicionales

  • Ki Yung Ahn; Sheard, Tim (2011). "Una jerarquía de combinadores de recursión al estilo Mendler: domando tipos de datos inductivos con ocurrencias negativas" . Actas de la 16.ª conferencia internacional ACM SIGPLAN sobre programación funcional . ICFP '11.
  • Catamorfismos en HaskellWiki
  • Catamorfismos de Edward Kmett
  • Catamorfismos en Fa# (Parte 1 , 2 , 3 , 4 , 5 , 6 , 7 ) por Brian McNamara
  • Catamorfismos en Haskell