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!

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!

Scalera tip: Why ‘scala.util.Try’ doesn’t have ‘finally’ clause?

Some days ago, a work colleage raised the million-dollar question.

If we use the traditional java try, we could be handling some code similar to this:

val connection = database.getConnection()
var data: Seq[Data] = Seq()
try {
  val results = connection.query("select whatever")
  data = results.map(convertToWhatIneed)
} catch {
  case t: Throwable => logger.error("Oh noes!")
} finally {
  connection.close()
}

In Scala, we have a more functional version of this mechanism: scala.util.Try.
The same example could be implemented by using this data type:

val connection = database.getConnection()
val data: Seq[Data] = Try{
  val results = connection.query("select whatever")
  val data: Seq[Data] = 
    results.map(convertToWhatIneed)
  connection.close()
  data
} recover {
  case t: Throwable => 
    logger.error("Oh noes!")
    connection.close()
    Seq.empty[Data]
} get

The question is, why doesn’t scala.util.Try even consider a finally clause like Java’s try?

Side effects….side effects everywhere…

If you remember the post where David talked about Try[T] data type, it’s a type that may have two different possible values Success(t: T) or Failure(t: Throwable).

On the other hand, if you remembet another post where we talked about vals and vars, we mentioned the referential transparency as principle that must be followed for considering a function to be pure.

So, if we test this principle with the previously described snippet, we could replace the Try[Seq[Data]] expression with the same type value that we would have got by evaluating the expression; and we should retrieve the same result. I.e.:

val connection = database.getConnection()
val data: Seq[Data] = 
  Success(Seq(data1,data2,data3)).get

We can see it hasn’t closed the connection that we opened before though…

o6dau

For this reason, it makes more sense to code something like this:

val connection = database.getConnection()
val data: Seq[Data] = Try{
  val results = connection.query("select whatever")
  results.map(convertToWhatIneed)
} recover {
  case t: Throwable => 
    Seq.empty[Data]
} get
connection.close()

This way, the data value can be replaced easily, without any extra side effect implication.

…And for this reason, fellows, it doesn’t make sense to think about a finally clause for Try[T]! 🙂

Peace out!

Scalera tip: ¿Por qué ‘scala.util.Try’ no tiene ‘finally’?

Hace algunos días, un compañero del trabajo planteó la duda del millón.

Si usamos el try tradicional de Java, podríamos encontrarnos con código similar a:

val connection = database.getConnection()
var data: Seq[Data] = Seq()
try {
  val results = connection.query("select whatever")
  data = results.map(convertToWhatIneed)
} catch {
  case t: Throwable => logger.error("Oh noes!")
} finally {
  connection.close()
}

En Scala, disponemos de una versión más funcional de este mecanismo: scala.util.Try.
El mismo ejemplo, utilizando esté tipo de datos, sería algo como

val connection = database.getConnection()
val data: Seq[Data] = Try{
  val results = connection.query("select whatever")
  val data: Seq[Data] = 
    results.map(convertToWhatIneed)
  connection.close()
  data
} recover {
  case t: Throwable => 
    logger.error("Oh noes!")
    connection.close()
    Seq.empty[Data]
} get

La pregunta es, ¿por qué scala.util.Try no considera una claúsula finally como el try de java?

Side effects….side effects everywhere…

Si recordáis el post en el que David habló sobre el tipo Try[T], es un tipo que puede tener dos posibles estados: Success(t: T) o Failure(t: Throwable).

Por otra parte, si hacéis memoria sobre el post en el que hablábamos sobre los valores y las variables, mencionábamos la transparencia referencial como principio que debe cumplirse para considerar una función pura.

Por lo tanto, si ponemos a prueba este principio con el snippet arriba descrito, podríamos sustituir la expresión de tipo Try[Seq[Data]] por el valor del mismo tipo que hubiéramos obtenido al evaluar la expresión, y deberíamos tener el mismo resultado. Por ejemplo:

val connection = database.getConnection()
val data: Seq[Data] = 
  Success(Seq(data1,data2,data3)).get

Sin embargo, vemos que no ha cerrado la conexión que hemos abierto justo antes…

o6dau

Por ese motivo, tiene más lógica hacer algo así como:

val connection = database.getConnection()
val data: Seq[Data] = Try{
  val results = connection.query("select whatever")
  results.map(convertToWhatIneed)
} recover {
  case t: Throwable => 
    Seq.empty[Data]
} get
connection.close()

De esta forma, el valor de data puede ser sustituido fácilmente, sin implicar más efectos de lado.

…¡y por esto, amigos, no tiene sentido pensar en un finally para Try[T]! 🙂

Agur de limón

Scalera tips: Referential transparency

We have already talked in other posts about several details of pure functional programming and the importance of avoiding side effects wherever possible.

Should we investigate a bit further about it, we would likely run into the concept of referential transparency. Today it’s time to see what this concept is about.

giphy

Referential transparency is strongly linked to the substitution model. If we want to use Scala and exploit its full potential as a functional programming language, we must keep this concept in mind. Despite its weird name, it is pretty easy to understand. Referential transparency means that a function of type I => O ought to be replaceable by a value of type O, without that entailing any loss of functionality. This way, we can be sure that the function has no side effects.

Side effects: a function has no side effects if it only transforms the input arguments into output arguments and does nothing else. Connecting to a database, printing on screen, writing logs or modifying a variable outside the scope of the function are considered to be side effects.

Let’s see an example with code. In this example we are going to create a function that will allow us to book a hotel room. The function will update the hotel’s reservations list and will return an identifier for the user:

var reservations: List[Reservation] = List.empy[Reservation]

def reserveRoom(roomNumber: Int, from: String, to: String): Int = {
  val id = generateId()
  reservations = Reservation(roomNumber, from, to, id) :: reservations
  id
}

val myReservation: Int = reserveRoom(1, "1/8/16", "15/8/16")

In this case, we are modifying a list which is outside the scope of the function. This is a side effect. Therefore, if we performed a substitution by any value belonging to the function domain, we would lose functionality as nothing would be added to the reservations list:

var reservations: List[Reservation] = List.empy[Reservation]

val myReservation: Int = "1" //Result of reserveRoom method

reservations.isEmpty //true....where is my reservation???

How can referential transparency be achieved? A simple option would be to return both the new updated list and the reservation identifier:

var reservations: List[Reservation] = List.empy[Reservation]

def reserveRoom(
  roomNumber: Int,
  from: Date,
  to: Date
): (Int, List[Reservation]) = {
  val id = generateId()
  (id, Reservation(roomNumber, from, to, id) :: reservations)
}

val (myReservation, reservationsUpdated) = reserveRoom(1, "1/8/16", "15/8/16")
reservations = reservationsUpdated

This way, if we repeated the exercise of substituting by a value, we wouldn’t be losing any information at all. And that’s all for today! See you soon 😉

Scalera tips: Transparencia referencial

Ya hemos hablado en otros post sobre algunos detalles de la programación funcional pura o sobre la importancia de evitar los efectos de lado siempre que sea posible.

Si investigamos un poco en el tema, es posible que nos encontremos con el concepto de transparencia referencial. Hoy vamos a ver a qué se refiere este concepto.

giphy

La transparencia referencial está fuertemente ligada con el modelo de sustitución. Si queremos utilizar Scala utilizando toda su potencia como lenguaje de programación funcional, es necesario que tengamos en mente este concepto. A pesar de tener un nombre algo raruno, es bastante fácil de entender. La transparencia referencial indica que una función de tipo E => S debería poder ser sustituda por un valor de tipo S sin que eso supusiera una pérdida de funcionalidad. De esta forma, podemos estar seguros de que no la función no tiene efectos de lado.

Efectos de lado: una función no tiene efectos de lado si solamente transforma los argumentos de entrada en los de salida, y no realiza absolutamente nada más. Conectarse con una base de datos, imprimir por pantalla, crear logs o modificar una variable fuera del scope de la función, se consideran efectos de lado.

Vamos a ver un ejemplo con código. En este ejemplo vamos a crear una función que permita reservar una habitación de hotel. La función actualizará la lista de reservas del hotel y además devolverá un identificador para el usuario:

var reservations: List[Reservation] = List.empy[Reservation]

def reserveRoom(roomNumber: Int, from: String, to: String): Int = {
  val id = generateId()
  reservations = Reservation(roomNumber, from, to, id) :: reservations
  id
}

val myReservation: Int = reserveRoom(1, "1/8/16", "15/8/16")

En este caso, estamos modificando una lista que está fuera del ámbito de la función. Esto es un efecto de lado. Por tanto, si realizamos una sustitución por un valor cualquiera perteneciente al dominio de la función realmente estamos perdiendo funcionalidad porque ya no se está añadiendo nada a la lista de reservas:

var reservations: List[Reservation] = List.empy[Reservation]

val myReservation: Int = "1" //Result of reserveRoom method

reservations.isEmpty //true....where is my reservation???

¿Cómo podríamos cumplir la transparencia referencial? Una opción sencilla sería devolver, tanto una nueva lista actualizada, como el identificador de la reserva:

var reservations: List[Reservation] = List.empy[Reservation]

def reserveRoom(
  roomNumber: Int,
  from: Date,
  to: Date
): (Int, List[Reservation]) = {
  val id = generateId()
  (id, Reservation(roomNumber, from, to, id) :: reservations)
}

val (myReservation, reservationsUpdated) = reserveRoom(1, "1/8/16", "15/8/16")
reservations = reservationsUpdated

De esta manera, si repetimos el ejercicio de sustituir por un valor, no perdemos información ¡Y ya hemos acabado! Hasta la próxima 😉