Catamorfismos y Álgebras F

Así que a menudo escucho las palabras “catamorfismo” y “esquemas de recursión”. ¿De qué va eso?

Los catamorfismos (o cata) son generalizaciones del concepto de pliegue en la programación funcional. Dado un Álgebra F y una estructura de datos recursiva, un catamorfismo producirá un valor al evaluar recursivamente su estructura de datos.

¿Qué es un Álgebra F? ¿Tal vez puedas mostrar algunos ejemplos de código primero?

La configuración no es tan sencilla, así que empecemos de forma sencilla. Supongamos que tiene la siguiente estructura de datos para representar una expresión:

Y una expresión simple puede verse así:

Tener solo una estructura de datos de expresión es inútil, por supuesto, necesitará una función para evaluar y obtener el resultado:

Aquí es donde entra en juego la generalización del catamorfismo:

🤨, ¿pero cuál es el punto? ¿Estás aplicando un argumento a una función?

Eso es porque es notReallyCata. La función real cata es genérica y no depende de ninguna estructura de datos o función de evaluador en particular. Ver, la creación de una estructura de datos recursiva y luego plegarse sobre ella es un patrón común que cata intenta generalizar.

Ok, entonces, ¿cómo se ve el cata real?

🤯

por Eso empezamos con notReallyCata. Desglosaremos la implementación más tarde hasta que haga clic. Pero ahora continuemos con nuestro ejemplo Expression. Primero, necesitamos deshacernos de la recursividad introduciendo un parámetro de tipo:

Todas las referencias a Expression se sustituyen por el parámetro de tipo a para que la estructura de datos ya no sea recursiva.

¿por Qué hay un F al final de los constructores de tipos?

Me alegro de que hayas preguntado — es una pista de que ExpressionF puede ser un Functor:

Nada sofisticado, simplemente aplicando alguna función al valor envuelto preservando la estructura.

No estoy seguro de por qué necesitamos eso 🤔

No tiene sentido ahora, pero lo tendrá un poco más tarde. Ahora, la forma en que creamos nuestra expresión no ha cambiado (excepto los nombres de constructores):

Pero el tipo resultante es diferente:

expr contrae todo en un único Expression mientras que exprF codifica información sobre el nivel de anidamiento de nuestro árbol de expresiones. Hablando de evaluación, así es como podemos implementar la evaluación para ExpressionF:

La principal diferencia con original evalExpr es que no tenemos llamada recursiva a evalExprF (ExpressionF no es recursiva, ¿recuerdas?). También significa que nuestro evaluador puede trabajar solo con una expresión de un solo nivel:

Y no compilará en esto:

Simplemente porque exprF expepects ExpressionF Int y estamos empujando ExpressionF (ExpressionF Int).

Para que funcione podríamos definir otro evaluador:

Parece un poco ad hoc, ¿y si tienes expresiones profundamente anidadas?

Sí, para expresiones anidadas arbitrarias, este enfoque no es escalable: cada nivel de anidamiento adicional requiere que escriba una función especializada.

Hay una manera de generalizar este anidamiento con un nuevo tipo de:

Fix? Parece una estructura de datos recursiva que no hace mucho. ¿Cómo es útil?

Veamos primero la expresión antes del signo igual: indeed Fix es una estructura de datos recursiva que tiene un parámetro de tipo f. Este parámetro tiene tipo * -> *, por ejemplo, también toma un parámetro tipo. Por ejemplo, no puedes construir Fix proporcionando Int o Bool, tiene que ser algo como Maybe, List o ExpressionF. Esta es la razón por la que introdujimos el parámetro de tipo para ExpressionF. A continuación, después del signo igual tenemos un constructor de tipo único Fx que toma un solo argumento de tipo f (Fix f) que es básicamente una expresión que construye el valor de f. En el caso de Maybe sería Maybe (Fix Maybe) y luego todo se envuelve con Fx en el tipo Fix Maybe.

La firma de tipo es confusa de leer al principio debido a que el constructor de tipo puede tener el mismo nombre que el tipo en sí más auto referencia. Pero no hay mucho más que envolver un tipo de orden superior en una estructura de datos. Por cierto, unfix es un opuesto a Fx y todo lo que hace es coincidencia de patrones en Fx y devuelve un valor envuelto, no es gran cosa.

Ahora, reemplazaremos cada ExpressionF de nuestro árbol de expresiones con Fix ExpressionF. Observe la diferencia en la construcción de expresiones con y sin Fx – son básicamente las mismas, excepto que necesitamos anteponer Fx $:

El tipo resultante de una versión ‘fija’ es Fix ExpressionF, por lo que volvemos a una representación recursiva, pero ahora tenemos que usar la función unfix para recuperar nuestra estructura de datos no recursiva.

¿cuáles son los beneficios de tener Fix? Parece que es el mismo enfoque que el tipo original Expression, pero ahora tenemos este extraño Fix y unfix sin sentido?

Sí, pero estamos tratando de generalizar el proceso de plegado, requiere la introducción de abstracciones adicionales, como Fix y Algebra que discutiremos más adelante. Ten paciencia, más adelante tendrá más sentido.

Así que tenemos nuestra estructura de datos “fija”, ¿cómo se vería la función de evaluación?

Dado un Fix ExpressionF lo único que podemos hacer con él es llamar a unfix que produce ExpressionF (Fix ExpressionF):

El ExpressionF devuelto puede ser uno de nuestros ValueF, AddF o MultF con un Fix ExpressionF como parámetro de tipo. Tiene sentido hacer coincidencias de patrones y decidir qué hacer a continuación:

Sí, se ve igual que nuestro primer evaluador recursivo para Expression con la adición de tener que desenvolver la expresión con unfix. Entonces, ¿por qué molestarse con Fix de todos modos?

Aquí está la clave: reutilizaremos nuestro evaluador original “sin correcciones” para ExpressionF y de alguna manera lo distribuiremos sobre la estructura Fix ExpressionF. Por lo tanto, esta debe ser una función que tome dos argumentos: el evaluador y la estructura a evaluar:

Intentemos averiguar la implementación: la primera cosa lógica a hacer es usar unfix para obtener ExpressionF y luego tal vez pasarlo a evaluator:

Obviamente esto no funciona, evaluator espera ExpressionF Int y no ExpressionF (Fix ExpressionF). Por cierto, recuerde que ExpressionF es Functor? Aquí es donde se vuelve útil: podemos usar fmap para aplicar el mismo proceso al nivel interno de nuestro árbol de expresiones:

Tómese un momento y piense en lo que sucede: estamos pasando una función recursiva almostCata evaluator a fmap. Si la expresión actual es AddF o MultF, esta función se pasará un nivel más profundo y se volverá a llamar a fmap. Esto sucederá hasta que alcancemos ValueF, el mapeo de fm sobre ValueF devuelve un valor de tipo ExpressionF Int y eso es exactamente lo que acepta nuestra función evaluator.

Mirando almostCata podemos ver que realmente no tiene nada específico de tipo ExpressionF o Int y teóricamente se puede generalizar con algún parámetro de tipo f. La única restricción debe ser tener una instancia Functor para f, porque estamos usando fmap:

Y esa es la versión final de cata. Aquí está la implementación completa con algunos ejemplos de uso:

Supongo que está bien. ¿Pero por qué tho?

Muchos conceptos en teoría de categorías y programación funcional son bastante abstractos y, a veces, es difícil encontrar una aplicación práctica inmediata para cierta idea. Pero buscar abstracciones y generalizaciones es útil para encontrar patrones y soluciones elegantes a problemas que de otro modo requerirían una implementación ad hoc.

Por cierto, al generalizar nuestra función ExpressionF -> Int a Functor f => (f a -> a) descubrimos otro concepto importante llamado Álgebra F. Básicamente, el álgebra F es un triple de funtor f, algún tipo a y función evaluadora f a -> a. Tenga en cuenta que a aquí no es polimórfico, tiene que ser un tipo de concreto, como Int o Bool y se llama un tipo portador. Para cualquier funtor endo f puede crear múltiples álgebras de F basadas en él. Tomemos como ejemplo nuestras expresiones endo-funtor f es ExpressionF, a es Int y evaluador es evalExprF. Pero podemos cambiar el tipo de portador y producir más álgebras:

Eso son solo diferentes evaluadores que se pueden pasar a cata, ¿verdad?

Sí, elegimos diferentes tipos de operadores y elegimos nuestra implementación. Pero ahí está el truco: hay una madre de todos los evaluadores que podemos crear eligiendo nuestro tipo de portador para que sea Fix ExprF.

Evaluar a Int o Bool tiene totalmente sentido, pero ¿qué evaluaría esto initialAlgebra? Cuando necesito tener Fix de algo como resultado de mi evaluador?

Por supuesto, no escribirás algo así tú mismo, solo quieres mostrarte el significado más profundo detrás de álgebras f y cata. De hecho, ya tenemos una implementación para dicho evaluador y eso es exactamente Fx constructor:

Esperar, Fx es un evaluador? Eso es una locura.

Sí y hace lo más simple que puede hacer: guardar la sesión en una estructura de datos. Mientras que todos los demás evaluadores (algebra0, algebra1) produjeron algún valor al reducir la expresión (como hacer suma o concatenación) Fx simplemente envuelve la expresión sin perder ningún dato.

Esta es la razón por la que introdujimos Fix en primer lugar: primero evalúa su estructura de datos original con Fx en álgebra inicial Fix f y luego usa cata la evaluación ‘real’ ocurre al fmaping su evaluador concreto sobre álgebra inicial.

Desde el punto de vista de la teoría de categorías, todas las álgebras basadas en el mismo funtor endo forman una categoría. Esta categoría tiene un objeto inicial que es nuestro álgebra inicial creado al elegir el tipo portador como Fix f. Hay algunas excelentes publicaciones de blog de Bartosz Milewski que recomiendo revisar si quieres obtener una comprensión categórica profunda.

Todavía es bastante difícil de comprender, creo que no entiendo completamente el concepto

Siempre es mejor hacerlo de forma práctica: intente reimplantar Fix y cata por su cuenta, piense en posibles estructuras de datos y álgebras. Por ejemplo, un String se puede representar recursivamente (como un Char cabeza y cola de String), el length de una cadena se puede calcular con cata. Aquí hay algunos excelentes recursos para leer más:

• Comprensión de Álgebras F y Álgebras F ligeramente diferentes por Bartosz Milewski
• Catamorfismos en 15 minutos por Chris Jones
• Programación de base de datos Funcional Pura con Tipos de puntos fijos por Rob Norris
• Catamorfismos en Haskell wiki
• Esquemas de recursión prácticos por Jared Tobin