Semigrupos y monoids

Una vez que hemos entendido lo que son las typeclasses y cómo implementarlas en Scala, lo que sigue es hablar de abstracciones,

Muchos programadores se asustan cuando leen algo que tiene que ver con teoría de categorías o matemáticas abstractas; después de todo, se puede programar bien sin meterse en tantos líos. No obstante, hay un principio que todo programador conoce: DRY (Don’t Repeat Yourself), que básicamente se refiere a no repetir el mismo código en diferentes partes; de hecho, es de lo más importante que se aprende cuando se aprende programación estructurada: si vas a usar una serie de instrucciones en más de un lugar, mejor júntalas, ponlas en un método por separado y mándalo llamar cada vez que lo necesites con los datos que necesites procesar. Simple.

Las abstracciones matemáticas son exactamente lo mismo, solamente llevado a más alto nivel: si existe un patrón que se repite constantemente en diferentes programas, ¿por qué no abstraerlo en código separado y llamarlas con los datos necesarios?

Un patrón común en diversos programas es el de aplicar una operación en 2 elementos de un mismo tipo. Por ejemplo, pensemos en la adición de dos números enteros: 5 + 4. Nada del otro mundo. Ahora, ¿qué pasa si en vez de enteros usamos números de punto flotante? Fácil: 3.7 + 5.9. ¿Y si ahora pensamos en strings? “Hola” + “mundo”. ¿Y si lo hacemos con listas? [1,2,3] + [4,5,6].

Como se puede observar, sumar 2 elementos del mismo tipo es una operación relativamente común. Ahora, ¿cómo lo abstraemos? La primera solución que muchos pueden proponer es tener un método  que tome un parámetro de cualquier tipo, evalúe ese tipo y aplique la operación correspondiente. Algo como lo siguiente:

def append(a: Any, b: Any) =                                                                                   
  if (a.getClass != b.getClass)                                                                                
    None                                                                                                       
  else                                                                                                        
    a match {                                                                                                  
      case _: Int => Some(a.asInstanceOf[Int] + b.asInstanceOf[Int])                                           
      case _: Double => Some(a.asInstanceOf[Double] + b.asInstanceOf[Double])                                  
      case _: String => Some(a.asInstanceOf[String] + b.asInstanceOf[String])                                  
      case _: List[_] => Some(a.asInstanceOf[List[_]] ++ b.asInstanceOf[List[_]])                              
      case _ => None                                                                                           
    }

scala> append(5,"Hola")
res6: Option[Any] = None

scala> append(5,6)
res7: Option[Any] = Some(11)

scala> append("Hola", "mundo")
res8: Option[Any] = Some(Holamundo)

scala> append(List(1,2,3), List(4,5,6))
res9: Option[Any] = Some(List(1, 2, 3, 4, 5, 6))

El código funciona, pero inmediatamente podemos ver que tiene muchas desventajas:

• Tenemos que revisar explícitamente por errores en tipos, por eso se regresa un Option[Any].
• El resultado tiene que volver a ser evaluado para saber de qué tipo es el valor está dentro del Option.
• Hay muchas conversiones de tipo dentro del match.
• El código no es fácil de leer.
• Tenemos que modificar este método cada vez que le agreguemos un nuevo tipo en el match. Por ejemplo, cuando creamos una clase y queremos usar este método para adicionar 2 instancias.

Además de las anteriores, no podemos usar fácilmente ese código dentro de un fold porque necesitamos un valorneutral para la serie de operaciones a realizar, y para obtenerlo necesitaríamos, de nuevo, evaluar el tipo y proveer el valor neutral en concordancia con él. Recordemos que fold está definido como:

def fold[A1 >: A](z: A1)(op: (A1, A1) => A1): A1

/* foldLeft y foldRight también aplican, aunque aquí z es
   un valor inicial
*/

def foldLeft[B](z: B)(f: (B, A) => B): B
def foldRight[B](z: B)(op: (A, B) => B): B

Es decir: fold toma como parámetros un valor neutral (z) y una función binaria que regresa un valor del mismo tipo que sus parámetros (op: (A1, A1)  => A1), y regresa un valor del mismo tipo recibido.

Como se puede notar, es mucho que tener en cuenta para poder hacer un código “general”.

Lo que podemos hacer es: en vez de definir nosotros la implementación de todas las posibles clases que se pueden adicionar, dejamos que cada tipo defina su propia forma de adicionarse, siguiendo una regla que definiremos, y simplemente en nuestro código “general” mandamos llamar esa función de adición.

Ésta es una gran oportunidad para usar typeclasses: creamos una donde los elementos que quieran pertenecer a ella necesitan implementar una función específica, que en este caso llamaremos append. Todo esto es, en esencia, un semigrupo.

Definamos pues nuestra typeclass:

trait Semigroup[T] {
  def append(a: T, b: T) : T
}

Pero antes de proveer algunas implementaciones, podemos aprovechar para generalizar el concepto de “valor neutro”, ya que, de esa forma, podríamos definir operaciones fold de forma general sin preocuparnos por ver si todo es del tipo correcto.

Llamemos zero a ese elemento neutro. Recuerden que tiene que ser un elemento el cual, al momento de ser adicionado con otro del mismo tipo de datos, tiene que regresar ese mismo elemento. Es como el 0 en la adición de números (a + 0 = a) o el 1 en la multiplicación (a * 1 = a). Ahora, juntando la capacidad de adición de los semigrupos con la definición del valor neutro nos da como resultado lo que se conoce como monoid.

trait Monoid[T] extends Semigroup[T] {
  def zero : T
}

Como se puede apreciar, los monoids son simples abstracciones de la capacidad de adición, con valor neutro, de algo. Quizá nos asusta el nombre al principio, pero en realidad no es nada con lo que no hayamos trabajado en el pasado. Solamente necesitamos un poco de formalización: un monoid tiene que cumplir 3 leyes para poder ser considerado como tal.

• Asociatividad. Para todo a, b, c que petenezcan a un monoid M, (a op b) op c = a op (b op c)
• Elemento de identidad. Un monoid debe definirlo. i op a = a op i = a
• Cierre (“Closure” en inglés). Para todos los elementos a,b en un monoid, el resultado de a op b también pertenece al mismo monoid.

(“op” es la operación de adición “append”, aunque no necesariamente es sinónimo de suma).

¿Para qué las leyes? Sí, a veces las matemáticas dan flojera, pero no se equivocan 🙂 Si nos aseguramos que cualquier monoid cumple con ellas, podemos programar de forma abstracta y sabemos que cualquier monoid se comportará de la misma manera, lo que se traduce en menos preocupaciones para nosotros.

Volvamos a definir la función append que usamos arriba, pero esta vez, usando monoids:

def append[T](v1: T, v2: T)(implicit m: Monoid[T]) = m.append(v1,v2)

¡Listo! … ¿Eh? ¿Cómo?
Ahora append acepta tipos genéricos (T), y toma 3  parámetros: los dos valores a agregar (de tipo T) y el monoid del tipo T de forma implícita. Usar implícitos no es obligatorio, pero nos ayuda a que el código que manda llamar esta función sea mucho más claro, y provee polimorfismo ad hoc. Ya veremos cómo un poco más abajo. La definición de cómo agregar elementos del tipo T la define el mismo tipo, y como estamos seguros que recibiremos un monoid de él, simplemente mandamos llamar la operación y listo. El tipo del valor de retorno está asegurado que será T por la tercera propiedad de los monoids, por lo que no hay que hacer ningún chequeo de tipos con él.

Solamente falta proveer la implementación de algunos monoids, pero gracias a las typeclasses abrimos la posibilidad de que cualquier otro programador cree monoids de las clases que use y aproveche el código generalizado sin tener que volver a definir la rueda.

Comencemos con un monoid que ya mencionamos: números enteros y la operación adición (+). Revisemos:

• Para todo entero a, b, c, (a + b) + c = a + (b +c)
• Elemento neutro: 0, Para todo entero a, a + 0 = a
• Cierre: Para todo entero a, b, a + b siempre da como resultado un entero.

Las reglas se cumplen, entonces, al código:

object MonoidDefinitions {
  implicit def intMonoid : Monoid[Int] = new Monoid[Int] {
    def append(a: Int, b: Int) = a + b
    def zero = 0
  }
}

Noten de nuevo que declaramos al nuevo monoid como implícito para que nuestra función “append” lo encuentre sin que tengamos que expresarlo directamente.

Hora de probar. No hay que olvidar importar el objeto que tiene las implementaciones de los monoids para que el compilador pueda encontrarlo. Si no lo hacemos, esto es lo que sucede:

scala> append(3,4)
<console>:11: error: could not find implicit value for parameter m: Monoid[Int]
              append(3,4)

Entonces:

scala> import MonoidDefinitions._
import MonoidDefinitions._

scala> append(3,4)
res12: Int = 7

¡Funciona! El monoid que definimos para enteros fue encontrado, su operación append fue aplicada y el resultado es otro entero. Esto nos pone del otro lado. Ahora nada más necesitamos proveer implementación de monoid para los tipos de datos que queramos.

String:

implicit def stringMonoid : Monoid[String] = new Monoid[String] {
     def append(a: String, b: String) = a + b
     def zero = ""
}

scala> append("Hola", "mundo")
res13: String = Holamundo

Listas:

/* Como las listas necesitan un parámetro de tipo, 
   declaramos la función de forma que reciba genéricos (A)
*/
implicit def listMonoid[A]: Monoid[List[A]] = new Monoid[List[A]] {
     def append(a: List[A], b: List[A]) = a ++ b
     def zero = Nil
}

scala> append(List(1,2,3), List(4,5,6))
res15: List[Int] = List(1, 2, 3, 4, 5, 6)

scala> append(List("Hola","a"), List("todo", "el", "mundo"))
res16: List[String] = List(Hola, a, todo, el, mundo)

Uno más, un poco más complicado: definamos el monoid de un Map[A,B] (recuerden que nosotros decidimos la implementación):

• El monoid solamente estará definido si existe un monoid del tipo de los valores (B) .
• “append” llamará al append del monoid de B solamente para los valores que tengan la misma llave en los 2 mapas a agregar.
• El elemento neutro será un mapa vacío.

/* Map: asocia llaves (de tipo A), con valores (de tipo B) */

implicit def mapMonoid[A,B](implicit ev: Monoid[B]) : Monoid[Map[A,B]] = new Monoid[Map[A,B]] {

 def append(a: Map[A,B], b: Map[A,B]): Map[A,B] = {
   val z = ev.zero
   (a.keys ++ b.keys).foldLeft(zero){case (newMap, key) =>
     newMap + (key -> ev.append(a.getOrElse(key,z), b.getOrElse(key,z)))
    }

 }

 def zero = Map[A,B]()
}


val m1 = Map("a" -> 1, "b" -> 2, "c" -> 3)
val m2 = Map("a" -> 4, "c" -> 14, "d" -> 5)

/* Los valores son enteros, y ya hemos definido ese Monoid */

scala> append(m1,m2)
res17: scala.collection.immutable.Map[String,Int] = Map(a -> 5, b -> 2, c -> 17, d -> 5)

Analicemos el contenido de la implementación de append para el monoid de mapas:

• Como la condición es que el tipo de datos de los valroes sea un monoid, asignamos a la constante z el elemento neutro de ese monoid.
• (a.keys ++ b.keys) crea un Set que contiene las llaves de ambos mapas. Al ser un set, nos aseguramos que no hay elementos repetidos.
• foldLeft toma como valor inicial el elemento neutro del monoid de Map, es decir, un mapa vacío, y la función binaria agrega al nuevo mapa la llave en cuestión asociada con el valor de aplicar la operación append del monoid de los valores a aquellos asociados con la llave en cuestión (key -> ev.append()). Pero como no sabemos si la llave está presente en ambos mapas, usamos getOrElse para obtener un valor default en caso de que no existe; ese valor es la constante z, la cual, al ser elemento neutro, no afecta el valor del otro mapa que sí tiene la llave al momento de aplicar append.

Al principio no es tan obvio dónde se pueden usar Monoids en nuestro código, pero si le buscan, seguramente en más de una ocasión han tenido que hacer algo similar en código o proyectos diferentes. Ciertamente cuesta trabajo ver esas abstracciones al principio, pero conforme las vas usando comienzas a ver dónde podrían entrar.

Como nota final, la librería ScalaZ provee implementación de monoids para los tipos de datos más comunes, solamente que, aunque tiene append, es más común (y conciso en mi opinión) usar el operador |+|, que es simplemente otra forma de llamar a append. Por tanto, en el código de arriba en vez de  usar ev.append(m1,m2) podríamos usar m1 |+| m2 si queremos usar la implementación que Scalaz ofrece para el tipo Map.  Además,  en ScalaZ hay clases o extensiones de  interesantes que usan monoids directamente, por lo que mucho boilerplate puede omitirse. Por ejemplo, Option tiene una función llamada orZero, definida de la siguiente forma:

final def orZero(implicit z: Monoid[A]): A

Lo que hace es esencialmente getOrElse(z.zero), pero se escribe menos, y si el monoid ya está dentro del scope, entonces tenemos código como

import scalaz._
import Scalaz._

/* Monoid de String en scope */

def something(opStr: Option[String]) = optStr orZero

que a mi gusto es mucho más legible, y nos aseguramos que el valor default sea uno perfectamente preestablecido; en este caso, la cadena vacía (“”).

Los semigrupos y monoids son, creo yo, una manera muy buena de ver el uso de typeclasses y, al mismo tiempo, de entrar en el mundo de las abstracciones. Lo que sigue es volver a ver Functors, aunque sea un repaso de lo ya visto anteriormente, y después ver su extensión natural, los Applicative Functors.