Índice
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.
<!–ad–>
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:
<figure> <a href="/img/category-theory-composition.jpg"> <img on="tap:lightbox1" role="button" tabindex="0" layout="responsive" src="/img/category-theory-composition.jpg" alt="Arrows and objects category Theory" title="Arrows and objects category Theory" sizes="(min-width: 640px) 640px, 100vw" width="640" height="360"> </img> </a> <figcaption>Ejemplo de Categoría</figcaption> </figure>
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:
f: A -> Bg: B -> DSi componemos esas dos, también tienes
h: A -> D.
La composición se lee de derecha a izquierda, por tanto g∘f quiere decir g(f(x)).
Propiedades de la composición
Asociatividad:
f∘(g∘h) == (f∘g)∘h == f∘g∘h.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:
<figure> <a href="/img/category-theory-identity.jpg"> <img on="tap:lightbox1" role="button" tabindex="0" layout="responsive" src="/img/category-theory-identity.jpg" alt="Category Theory, object identity" title="Category Theory, object identity" sizes="(min-width: 640px) 640px, 100vw" width="640" height="360"> </img> </a> </figure>
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:
<figure> <a href="/img/category-theory-composition-test.png"> <img on="tap:lightbox1" role="button" tabindex="0" layout="responsive" src="/img/category-theory-composition-test.png" alt="Category theory property tests" title="Category theory property tests" sizes="(min-width: 397px) 397px, 100vw" width="397" height="105"> </img> </a> </figure>
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
¿Has visto algún error?: Por favor, ayúdame a corregirlo contactando conmigo o comentando abajo.