Damos una serie de ejemplos, y luego un enfoque más global de los catamorfismos, en el lenguaje de programación Haskell.
Iteracióneditar
Las prescripciones de paso de iteración conducen a números naturales como objeto inicial.
Considere el functor fmaybe asignación de un tipo de datos b para un tipo de datos fmaybe b, que contiene una copia de cada término de b así como un término adicional Nothing (en Haskell, esto es lo Maybe hace). Esto se puede codificar usando un término y una función. Así que vamos a una instancia de un StepAlgebra también incluye una función de fmaybe b a b, que se asigna Nothing a un plazo fijo nil de b, y donde las acciones en el copiado de los términos será llamado next.
List foldEdit
Para un tipo fijo a, considere los tipos de asignación de funtor b al tipo de producto de esos dos tipos. Además, también agregamos un término Nil a este tipo resultante. Una f-álgebra ahora map Nil para algunos especiales término nil de b o «combinar» un par (de cualquier otro término del tipo construido) en un plazo de b. Esta fusión de un par se puede codificar como una función de tipo a -> b -> b.
Árbol de foldEdit
Por un tipo fijo a, considerar el functor de asignación de tipos de b a un tipo que contiene una copia de cada término de a así como de todos los pares de b‘s (términos del tipo de producto de dos instancias del tipo b). Un álgebra consiste de una función a b, que actúa en un a plazo o dos b términos. Esta fusión de un par se puede codificar como dos funciones de tipo a -> b resp. b -> b -> b.
Caso generaleditar
Los estudios teóricos de categorías más profundas de álgebras iniciales revelan que el álgebra F obtenida de aplicar el funtor a su propio álgebra inicial es isomórfica.
Los sistemas de tipos fuertes nos permiten especificar de forma abstracta el álgebra inicial de un funtor f como su punto fijo a = f a. 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 el fmap. Dado que el dominio de estos últimos son los objetos en la imagen de f, la evaluación de la catamorphisms saltos atrás y adelante entre a y f a.
Ahora de nuevo el primer ejemplo, pero ahora pasando el funtor Maybe a Fix. La aplicación repetida del funtor Maybe genera una cadena de tipos, que, sin embargo, puede ser unida por el isomorfismo del teorema del punto fijo. Introducimos el término zero, que surge de Nothing de Maybes e identificamos una función sucesora con la aplicación repetida del Just. De esta manera surgen los números naturales.
Y ahora de nuevo el ejemplo de árbol. Para ello debemos proporcionar el tipo de datos del contenedor de árbol para que podamos configurar el funtor fmap (no tuvimos que hacerlo para el funtor Maybe, ya que es parte del preludio estándar).
data Tcon a b = TconL a | TconR b binstance Functor (Tcon a) where fmap f (TconL x) = TconL x fmap f (TconR y z) = TconR (f y) (f z)
type Tree a = Fix (Tcon a) -- the initial algebraend :: a -> Tree aend = Iso . TconLmeet :: Tree a -> Tree a -> Tree ameet l r = Iso $ TconR l r
treeDepth :: Algebra (Tcon a) Integer -- again, the treeDepth f-algebra exampletreeDepth (TconL x) = 1treeDepth (TconR y z) = 1 + max y z
El siguiente evaluará a 4: cata treeDepth $ meet (end "X") (meet (meet (end "YXX") (end "YXY")) (end "YY"))
