Mónadas para programadores en C++: std::optional (Parte I)

Conceptos matemáticos relevantes: Categorías, functores y mónadas

Desde un punto de vista matemático, una categoría C está constituida por [1]:

1. Una colección Ob(C) de objetos.
2. Una colección Hom(C) de flechas o morfismos que enlazan dichos objetos. Un morfismo f del objeto X al objeto Y se denota f: X → Y. El conjunto de morfismos entre los objetos X e Y se denota Hom_C(X, Y).
3. Una operación binaria de composición de morfismos. La composición de f: X → Y con g: Y → Z se denota g ∘ f: X → Z. 

Asumimos los siguientes axiomas en relación a la composición:

• Asociatividad: Si f: A → B, g: B → C y h: C → D, entonces h ∘ (g ∘ f) = (h ∘ g) ∘ f.
• Para cada objeto X, existe un morfismo identidad id_X: X → X que se comporta como elemento neutro bajo composición, i.e., para todo morfismo f: X → Y se cumple f ∘ id_X = id_Y ∘ f = f. Se puede demostrar que id_X es único para cada X.

La figura superior muestra, a modo de ejemplo, una categoría simple con tres objetos X, Y, Z, los morfismos f, g y g ∘ f, así como los morfismos identidad id_X, id_Y e id_Z. Como ya hemos indicado, aunque no se represente en la figura, entre dos objetos puede existir más de un morfismo. 

Consideremos la denominada categoría de conjuntos, denotada Set, cuyos objetos son todos los conjuntos matemáticos, los morfismos son las funciones totales (es decir, no parciales) entre dichos conjuntos y donde la composición de morfismos viene dada por la composición usual de funciones. Los axiomas antes mencionados se verifican aquí claramente, pues la composición de funciones entre conjuntos es asociativa y, dado cualquier conjunto S, es posible definir el morfismo identidad id_S: S → S que sirve como elemento neutro para la composición de funciones.

En el ámbito de la programación funcional, cabe señalar la categoría de tipos y funciones de Haskell, denotada Hask. En ésta, los objetos son los tipos de Haskell y los morfismos desde un tipo T a otro U son las funciones de tipo T → U (se considera aquí que dos funciones f y g definen el mismo morfismo si f x = g x para todo x) [2]. El operador (.) proporciona la composición de funciones, canalizando el resultado de una función como entrada de otra.

---

Un functor F: C₁ → C₂ (no confundir con el término habitualmente empleado en C++ para referirnos a objetos función) es una aplicación entre dos categorías C₁ y C₂ que [3]:

1. Asocia a cada objeto X en C₁ un nuevo objeto F(X) en C₂.
2. Asocia a cada morfismo f: X → Y en C₁ un nuevo morfismo F(f): F(X) → F(Y) en C₂ tal que F(id_X) = id_F(X) para todo X en C₁ y F(g ∘ f) = F(g) ∘ F(f) para todo par de morfismos f: X → Y, g: Y → Z en C₁.

Así pues, un functor preserva los morfismos identidad y la composición de morfismos.

---

Finalmente, una mónada definida sobre una categoría C es una terna (M, η, μ) consistente en [4]:

• Un endofunctor M: C → C, es decir, un functor que mapea objetos a objetos y morfismos a morfismos desde la categoría C a ella misma.
• Dos transformaciones naturales η: id_C → M, donde id_C denota el endofunctor identidad en C, y μ: M² → M, donde M² denota el endofunctor M ∘ M: C → C.

Se deben verificar las condiciones de coherencia μ ∘ Mμ = μ ∘ μM, μ ∘ Mη = id y μ ∘ ηM = id. En Haskell, η y μ reciben los nombres de return y join, respectivamente. 

La definición anterior es sin duda formal y, para nuestros propósitos, en exceso abstracta. Desde el punto de vista de la programación funcional, y para cualesquiera tipos T y U, una mónada consiste sencillamente en una terna (M, unit, bind) donde [5]:

• M es un constructor de tipos que asocia al tipo T un nuevo tipo monádico M T.
• unit: T → M T (también llamado return) es un conversor de tipos que recibe un valor de tipo T y lo embebe en un valor monádico de tipo M T.
• bind: (M T, (T → M U)) → M U es un combinador que, dada una función f: T → M U, puede transformar un valor monádico de tipo M T aplicando f sobre el valor desembebido de tipo subyacente T, devolviendo un valor monádico de tipo M U. Así pues, bind permite encadenar la salida de una función a la entrada de otra. En Haskell, esta operación se representa mediante el operador de notación de infijo ≫=.

Deben cumplirse las siguientes tres leyes (≡ señala equivalencia):

• unit es un elemento neutro por la izquierda para bind, es decir, unit(t) ≫= f  ≡  f(t).
• unit es un elemento neutro por la derecha para bind, es decir, M T ≫= unit  ≡  M T.
• bind es esencialmente asociativo (véase [6] para una definición más precisa).

En el próximo artículo de esta serie explicaremos el modo de empleo de la plantilla de clase std::optional en C++ [7], similar a Maybe en Haskell [8], la cual gestiona un valor contenido opcional, es decir, un valor que puede o no estar presente. En particular, analizaremos las operaciones monádicas que el próximo estándar C++23 incorporará para esta plantilla [9]. Para ello, aplicaremos las definiciones más relevantes presentadas en este post, particularmente los conceptos de functor y mónada.

---

Referencias bibliográficas:

1. Haskell Programming Language - Category theory - https://wiki.haskell.org/Category_theory
2. Haskell Programming Language - Hask category - https://wiki.haskell.org/Hask
3. Wikipedia - Functor - https://en.wikipedia.org/wiki/Functor
4. J. Adámek, H. Herrlich, and G. E. Strecker, Abstract and Concrete Categories. Dover Publications (2009).
5. Wikipedia - Monad - https://en.wikipedia.org/wiki/Monad_(functional_programming)
6. Haskell Programming Language - Monad Laws - https://wiki.haskell.org/Monad_laws
7. cppreference.com - std::optional - https://en.cppreference.com/w/cpp/utility/optional
8. Haskell Programming Language - Maybe - https://wiki.haskell.org/Maybe
9. P0798R8 - Monadic operations for std::optional - https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p0798r8.html