Qué mejor que volver de vacaciones con las pilas cargadas y con algún que otro tornillo suelto que nos empuje a escribir sobre temas que solo se te ocurren bajo el influjo de los puerros la luna.
¿TDA?
Un Tipo de Datos Algebraico(TDA en adelante para que no nos cobre WordPress por palabra) no es sino expresar un tipo de datos (Gato, Coche, Prevaricación) en base a un álgebra. Y cuando decimos álgebra nos referimos a sumas y productos de tipos (de Enteros, Gatos, Coches, Prevaricaciones, …). Por ejemplo:
Train = Locomotive + Wagon * Train
¿Esto como se lee? Un tren puede ser: una locomotora O un vagón Y otro tren (que a su vez puede ser otro vagón y otro tren, que a su vez …).
Fijaos en la disyunción y la conjunción: la suma suele representar un OR y el producto un AND (como en el álgebra de Boole).
Es interesante también darse cuenta que, de esta definición de tipos, se puede inferir un patrón recursivo. En el caso del tren, el caso base es la locomotora y en el caso recursivo tenemos un vagón y otro tren. Como veremos más adelante, este patrón se repite y facilita la definición de tipos.
¿Y cómo se representa la suma y el producto en Scala?
La forma más sencilla de representar la suma (también llamada coproducto) de tipos, en un paradigma que soporte polimorfismo (en general) y en Scala (en particular), no es sino la herencia. Si tenemos el siguiente caso:
sealed trait Animal case object Cat extends Animal case object Dog extends Animal
estamos formulando un coproducto de tipos:
Animal = Cat + Dog
es decir, un Animal
solamente puede ser, o un Cat
, o un Dog
.
En cuanto al producto, podríamos definirlo como el conjunto de atributos que componen una instancia de un cierto tipo. Por ejemplo,
case class Student(name: String, age: Int)
expresado como suma de productos, es como sigue:
Student = String * Int
Es decir, para construir el tipo Student
hace falta un String
y un Int
.
Si ahora tratamos de bajar a tierra el modelo de tren antes propuesto (con algún aditivo) tendremos que
Wagon = String * Int Train = Locomotive + Wagon * Train
se traduce en Scala a
sealed trait Train case object Locomotive extends Train case class Wagon(model: String, passengers: Int) case class Nexus(wagon: Wagon, next: Train)
¿Y esto para qué?
Si piensas, amigo, que esto son cosas que nadie usa, es porque no te paraste a pensar en qué estructuras de scala.predef
se definen de esta forma. Las listas (List
) por ejemplo se definen como:
trait List[+T] case object Nil extends List[Nothing] case class ::[T](head: T, tail: List[T]) extends List[T]
Es decir, una lista puede ser, o lista vacía, o un elemento seguido de otra lista.
Si lo expresamos en función de productos y coproductos:
List[T] = EmptyList[T] + NonEmptyList[T] NonEmptyList[T] = T * List[T]
Fijaos que el caso de la lista vacía (Nil
) tiene una implementación muy bonita en Scala.
Si tenemos que definir una lista vacía para tooooodos los tipos existentes, tendríamos que instanciar un Nil[Cat]
, Nil[Dog]
, …
Para evitar eso, y tener un único Nil
, hacemos que este extienda de List[Nothing]
que, como recordareis de otros posts, Nothing
extiende de tooooodos los tipos (tanto primitivos como definidos por el programador). Si a esto le sumamos que List[T]
es covariante en T
, tenemos un único objeto Nil
que representa las listas vacías de tooooodos los tipos. Alucinante, ¿no?
Ejemplo: Números pares
Para afianzar esta novedosa forma de pensar, pongámonos en la siguiente tesitura, ¿cómo podríamos representar los números pares en Scala?
Requirements
Si somos poco delicados y confiamos más en las aserciones en tiempo de runtime, podríamos decir que los números pares son:
case class Even(value: Int) { require(value%2==0, "it's not even") }
Si intentamos crear un Even
con un número impar nos dirá que nope:
Even(1) java.lang.IllegalArgumentException: requirement failed: it's not even at scala.Predef$.require(Predef.scala:233) at Even.<init>(<console>:7)
Sin embargo esta comprobación no se realiza hasta el momento de ejecución, que es cuando se comprueba el require
. Por lo que nuestro código podría estar compilando pero no ser correcto…
Podemos hacerlo mejor…
Next(Next(…))
Otra opción es asumir (y no vamos a discutir sobre ello) que el número 0 es par, que tenemos memoria infinita en nuestra máquina, que no existe el overflow, …
En ese caso, para nada alejado de la realidad (…) podríamos definir los números enteros pares como:
sealed abstract class Even(val value: Int) case object Zero extends Even(0) case class Next(previousEven: Even) extends Even(2 + previousEven.value)
De manera que si tenemos un método que genera una reserva para el barco del amor que requiere de un número par de participantes, podemos usar nuestro recién definido tipo Even
:
def loveBoatReservation( peopleAmount: Even): Reservation = ???
Dado que no hay forma de construir un Even
a partir de un entero que no sea par, evitamos situaciones en runtime en las que el número de personas que se montan en el barco sean impares. Sino siempre habría alguien …
Mecánica de métodos sobre TDAs recursivos
Una vez definido el tipo de datos, supongamos que queremos implementar la suma de números pares:
def sum(e1: Even, e2: Even): Even = ???
Tenemos varias alternativas. Una de ellas puede ser la quick-and-dirty:
def sum(e1: Even, e2: Even): Event = new Even(e1.value + e2.value){}
Pero fijaos que estamos pasando un kilo de los constructores que hemos definido. Si queremos hacer pattern matching ahora sobre el resultado:
val four = new Even(4){} sum(Zero, four) match { case Zero => //it never gets inside this case! case Next(Next(Zero)) => //OMG! IT DOESN'T FIT HERE EITHER! } scala.MatchError: $anon$1@649f2009 (of class $anon$1)
La otra técnica (algo más fina por otra parte) consiste en lanzar un método recursivo que, en cada llamada, vaya disminuyendo el segundo número par mientras que aumenta el primero. Para ello hacemos uso del constructor y extractor Next
:
def sum(e1: Even, e2: Even): Even = { @tailrec def rSum(ev1: Even, ev2: Even): (Even, Even) = { ev2 match { case Zero => (ev1, Zero) case Next(e) => rSum(Next(ev1), e) } } val (result, _) = rSum(e1, e2) result }
Innegablemente bello 🙂
Conclusiones
Pues a parte de que los posts de vuelta de vacaciones suelen ser para volverse majara, saquemos varias conclusiones principales:
- Como siempre decimos, que toda comprobación que nos podamos llevar de runtime a tiempo de compilación es un ahorro de quebraderos de cabeza cazando fallos con software en producción (lo cual es caro y es más fácil que haga rodar cabezas).
- Que los constructores son la clave. Si definimos un TDA sobre los números pares, podemos controlar que los valores generados son correctos definiendo los constructores adecuados: el
Zero
y elNext
. En ambos casos, tenemos la certeza de que se cumplen las leyes de los números enteros. - Que los métodos que operan sobre tipos de datos recursivos suelen ser, a menudo, recursivos también. Y no solo eso, sino que para poder generar valores del tipo en cuestión (
Even
en nuestro caso) solo deberían hacer uso de los constructores ya existentes.
En otro post hablaremos sobre la relación del álgebra de tipos y la definición de gramáticas formales…o no.
¡Agur de limón!
[…] (o puede que no) que nombramos hace tiempo de pasada los co-productos cuando hablábamos de tipos algebraicos de datos. Los definíamos entonces como la manera natural de expresar unión de tipos (Wine = White U Red U […]
Me gustaMe gusta