Catamorfismo

En la teoría de categorías , el concepto de catamorfismo (del griego antiguo : κατά "hacia abajo" y μορφή "forma, forma") denota el homomorfismo único de un álgebra inicial en alguna otra álgebra.

En programación funcional , 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 se despliega . Un hilomorfismo es la composición de un anamorfismo seguido de un catamorfismo.

Considere un -algebra inicial para algún endofunctor de alguna categoría en sí mismo. Aquí hay un morfismo de a . Dado que es inicial, sabemos que siempre que es otro -álgebra, es decir, un morfismo de a , existe un homomorfismo único de a . Según la definición de la categoría de -álgebra, esto corresponde a un morfismo de a , también denotado convencionalmente , tal que . En el contexto de -álgebra, el morfismo especificado unívocamente del objeto inicial se denota por ${\ Displaystyle F}$ ${\ Displaystyle (A, in)}$ ${\ Displaystyle F}$ ${\ Displaystyle en}$ ${\ displaystyle FA}$ ${\ Displaystyle A}$ ${\ Displaystyle (X, f)}$ ${\ Displaystyle F}$ ${\ Displaystyle f}$ ${\ Displaystyle FX}$ ${\ Displaystyle X}$ ${\ Displaystyle h}$ ${\ Displaystyle (A, in)}$ ${\ Displaystyle (X, f)}$ ${\ Displaystyle F}$ ${\ Displaystyle h}$ ${\ Displaystyle A}$ ${\ Displaystyle X}$ ${\ Displaystyle h}$ ${\ Displaystyle h \ circ en = f \ circ Fh}$ ${\ Displaystyle F}$ ${\ Displaystyle \ mathrm {cata} \ f}$ y por lo tanto caracterizado por la siguiente relación:

Otra notación que se encuentra en la literatura es . Los corchetes abiertos utilizados se conocen como corchetes de banano , después de lo cual los catamorfismos a veces se denominan bananos , como se menciona en Erik Meijer et al . ^[1] Una de las primeras publicaciones en introducir la noción de catamorfismo en el contexto de la programación fue el artículo “Programación funcional con plátanos, lentes, sobres y alambre de púas”, de Erik Meijer et al. , ^[1] que estaba en el contexto del formalismo Squiggol . La definición categórica general fue dada por Grant Malcolm .^[2]^[3] ${\ Displaystyle (\! | f | \!)}$

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