Algrebraic Data Types in Scala

What a delightful idea to come back from vacation with batteries fully charged and with some wacky ideas around our minds to write about. Best of these came from the very influence of joints the moon.

ADT?

An Algebraic Data Type (TDA from now so we can save money for each word in WordPress) is just a way to express a data type (Cat, Dog, Prevarication) based on an algebra. And when we say ‘algebra’, we mean type sums and products (of Integers, Cats, Cars, Prevarications, …). For example:

Train = Locomotive + Wagon * Train

How do one read that? A train may be: a locomotive OR a wagon AND another train (that may be as well a wagon and another train, that may be as well a …).
Take a look at both disjunction and conjunction: the sum represents an OR, and the product represents an AND (like Boole algebra).

It’s also worthy to notice that, from this type definition you can infer a recursive pattern. With the Train type, the base case is definitively the Locomotive and, at the recursive case, we have a wagon and another train. As we’ll see later, this pattern is very frequent and makes easier the type definition.

And how are sum and product represented in Scala?

The easier way to represent the type sum (also called co-product), in a paradigm with polimorphism support (in general) and in Scala (in particular), is just the inheritance feature. If we have the following case:

sealed trait Animal
case object Cat extends Animal
case object Dog extends Animal

we’re indeed expressing a type co-product:

Animal = Cat + Dog

that is, an Animal can only be, a Cat, or a Dog.

Regarding the product, we could define it as the attribute set that compounds a certain type instance. For example,

case class Student(name: String, age: Int)

expressed as a product sum, would be as follows:

Student = String * Int

So, for building a Student instance, you need a String and an Int.

If we try now to materialize the previously exposed train model (with some additives) we’ll notice that

Wagon = String * Int
Train = Locomotive + Wagon * Train

is translated into Scala as

sealed trait Train
case object Locomotive extends Train
case class Wagon(model: String, passengers: Int)
case class Nexus(wagon: Wagon, next: Train)

So what is it good for?

hqdefault

…absolutely nothing, listen to me♩♪♫♬.
If you think, my fellow, that this is stuff that nobody uses, you haven’t thought about which scala.Prefef structures are defined this way. Lists, for example, as defined as:

trait List[+T]
case object Nil extends List[Nothing]
case class ::[T](head: T, tail: List[T]) extends List[T]

That is, a List can be, an empty one, or an element followed by another list.
If we express that idea in terms of products and co-products:

List[T] = EmptyList[T] + NonEmptyList[T]
NonEmptyList[T] = T * List[T]

Please, notice that, the case of the empt list (Nil) has a bizarre but beautiful implementation in Scala.

If we try to define an empty list for eeeeeeeeeevery single existing type, we would have to instantiate a Nil[Cat], a Nil[Dog], …
In order to avoid this, and having an only Nil, we make it extend from List[Nothing] that, as you’ll probably remember from other posts, Nothing extends from eeeeeeeeevery single existing type (both primitive and programmer defined). If we add the fact of List[T] being covariant at T, we’ll have an only object Nil that represents the empty lists for all types. Awesome, right?

odtUdEE

Example: Even numbers

In order to harden to this new way of thinking, let’s suppose the following challenge: how could we represent even numbers in Scala?

Requirements

If we’re not sophisticated enough and we trust a lil’ bit in runtime assertions, we could say that even numbers are defined as:

case class Even(value: Int) { 
  require(value%2==0, "it's not even")
}

But, if we try to create an Even with an odd integer number we’ll get a giant NOPE:

Even(1)
java.lang.IllegalArgumentException: requirement failed: it's not even
	at scala.Predef$.require(Predef.scala:233)
	at Even.<init>(<console>:7)

However this assertion won’t be verified until run-time, the moment when require is executed. Thus, our code could be compiled without being correct…
We can do it much better…

Next(Next(…))

Another option is to assume (and we won’t discuss about it) that zero is an even number, that we have infinite memory installed in our machine, that the overflow error doesn’t exist…

907958

In that, not so far, case (…), we could define even numbers as:

sealed abstract class Even(val value: Int)
case object Zero extends Even(0)
case class Next(previousEven: Even) 
  extends Even(2 + previousEven.value)

So, if we have a method that generate reservations for the Boat Love, that requires an even number of participants, we can use our brand new defined Even type:

def loveBoatReservation(
  peopleAmount: Even): Reservation = ???

Given there’s no way to build an Even from an integer that is not even, we avoid uncomfortable situations at runtime, where the amount of people that get on the Love Boat are odd. Otherwise, someone could be…

forever-alone-400x400

Recursive ADTs and its techniques

Once the data type is defined, let’s suppose we want to implement the sum of even numbers:

def sum(e1: Even, e2: Even): Even = ???

We handle several alternatives. One of them could be the quick-and-dirty one:

def sum(e1: Even, e2: Even): Event = 
  new Even(e1.value + e2.value){}

But take a closer look at the fact that we’re totally ignoring the constructors we’ve defined. If we want to use pattern matching over the result:

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)

51067781

The other technique (much more sophisticated by the way) consists on invoking a recursive method that, for each call, it decreases the second even number, while it increases the first one. For doing so, we make use of Next apply(constructor) and unapply(extractor) methods:

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
}

Undeniably beautiful 🙂

Conclusions

Apart from becoming a lil’ bit crazier when reading back-from-vacation posts, we can extract several main conclusions from what we’ve read:

  • As we always say, every possible assertion that we can check at compile time instead of runtime, it’s saving time and headaches hunting bugs of software in production (which is more expensive and more keen to make heads roll).
  • Constructors are THE key. If we define an ADT, we can control that generated values of that type are correct by defining the proper constructors: Zero and Next. In both cases, we are certainly sure that even number rules are satisfied.
  • Methods that operate over recursive data types use to be recursive as well. And, apart from that, for generating values of the mentioned type (Even in our example) they should only use the existing constructor methods.

In a future post, we’ll talk about the relation between data types algebra and definition of formal grammars…or not.

Peace out!

Anuncios

Tipos de datos algebraicos en Scala

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?

odtUdEE

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, …

907958

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 …

forever-alone-400x400

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)

51067781

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 el Next. 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!