Autor

Alejandro Alcalde

Graduado en Ingeniería Informática en la ETSIIT, Granada. Creador de El Baúl del Programador

Más artículos de Alejandro Alcalde

¿Has visto algún error?: Por favor, ayúdame a corregirlo contactando conmigo.

Este artículo forma parte de una serie sobre Teoría de Categorías en Scala que estoy escribiendo basándome en el libro de Bartosz Milewski. Conforme voy leyendo, tomo notas y intento resolver los ejercicios propuestos por Bartosz, pero en Scala. El producto de ese trabajo son estos artículos que comparto en este blog. Todo el código está en elbaulp/Scala-Category-Theory, también puedes visitar la tabla de contenidos de esta serie.

CHANGELOG

Gracias a Jesús López por comentar en este artículo y corregir unos cuantos errores.

Introducción

Este es el primer artículo de una serie que voy a escribir sobre teoría de categorías.

Llevaba un tiempo queriendo aprender teoría de categorías, ya que he leido bastante sobre el tema y parece que tiene aplicaciones en el desarrollo de software.

Esta serie de artículos se basan en gran libro que Bartosz Milewski escribió hace un tiempo. Para aportar mi granito de arena, he decidido implementar los ejercicios que propone usando scala y tests basados en propiedades con scalacheck. Espero que te guste esta serie, y no dudes en comentar tu opinión o sugerir/corregir el contenido.


¿Te gusta el blog? Ayúdame a seguir escribiendo


Categoría: La esencia de la composición

Antes de continuar, ¿Qué es una categoría?, de Wikipedia:

En teoría de categorías, una categoría es una estructura algebraica que consta de una colección de objetos, conectados unos con otros mediante flechas tales que se cumplen las siguientes propiedades básicas: las flechas se pueden componer unas con otras de manera asociativa, y para cada objeto existe una flecha que se comporta como un elemento neutro bajo la composición.

En resumen, una categoría está formada por objetos y flechas, y pueden componerse. Esto se aprecia mejor con una imagen:

Ejemplo de Categoría

Cada flecha puede componerse, p.e: Si A -> B y B -> D entonces debe existir una flecha de A -> D. Las flechas pueden llamarse morfismos, y se pueden componer. En la imagen de arriba tienes:

La composición se lee de derecha a izquierda, por tanto g∘f quiere decir g(f(x)).

Propiedades de la composición

  1. Asociatividad: f∘(g∘h) == (f∘g)∘h == f∘g∘h.
  2. Para cada objeto existe una flecha Identidad, o morfismo Identidad, que va del objeto a sí mismo: f∘IDₐ = f == IDₐ∘f = f, como muestro debajo:

Ejemplos en Scala

Ahora que ya he comentado un poco de la teoría, vamos a implementarlo en scala. Como dije al principio, voy a usar tests basados en propiedades para comprobar que el objeto creado cumple las propiedades algebraicas de una categoría. Estas propiedades son la Identidad y asociatividad.

El código de abajo es la definición de una categoría (Para ser más precisos, es una instancia de la categoría Hask). En la categoría Hask, los objetos son tipos y las flechas funciones. Puedes consultar el código en el fichero Category.scala de mi respositorio.

object Category {
  def Id[T](x: T) = x
  def compose[A, B, C](f: A => B, g: B => C): A => C =
     f andThen g
}

Es bastante simple, una función identidad y otra función que compone dos funciones. Para comprobar que cumple las propiedades, he escrito los siguientes tests.

Tests basados en propiedades

Para mantener el artículo limpio, muestro solo el código necesario, puedes consultar el código completo de los tests en github.

Propiedad Identidad

property("a == Id(a)") {
  check(forAll { i:String =>
    Category.Id(i) === i
  })
}

property("Id∘f = f") {
  check(forAll { i: Int =>
    Category.Id(square(i)) === square(i)
  })
}

property("f∘Id = f") {
  check(forAll { i: Int =>
    f(Category.Id(i)) === f(i)
  })
}

La primera propiedad manifiesta que para todo String posible que se le pase a la función identity, la identidad siempre será la cadena de texto que se le pasó a la función.

La segunda y tercera propiedad indican que no importa cómo se componga la función identidad con otra función f, ya que el resultado siempre será esa función f.

Propiedad asociativa

property("Associativity: h∘(g∘f) = (h∘g)∘f = h∘g∘f"){
  check(forAll { i: Int =>
    Category.compose(Category.compose(f, g), h)(i) === Category.compose(f, Category.compose(g, h))(i)
  })
}

Como puedes ver, este test comprueba que la propiedad asociativa es cierta.

Si ejecutas estos tests, verás que todos pasan:

Eso es todo para esta primera parte, espero que te haya gustado. Me gustaría saber tu opinión, te animo a comentar abajo.

Recursos

Quizá también te interese leer...