Abstract alge… what? Functors and cucumbers

Category mania! Are we paid for speaking about it? I’m afraid we don’t. Would we like to? Very likely. In previous posts we spoke about monoids and monads, but now it’s functor’s time. Functors are everywhere and we can prove it. Before reviewing its different kinds, let’s focus on key concepts.

What’s a morphism?

It’s just a transformation between two structures, a change between spaces, a mutation.
In Scala? A simple function:

val f: A => B

What’s a functor?

Quick and simple answer: the behavior that defines, for a certain F[A] type constructor, the map method.

trait Functor[F[_]]{
  def map[A, B](fA: F[A])(f: A => B): F[B]
}

There are functors for List, Option, Future, Try, …

object ListFunctor extends Functor[List]{
  def map[A, B](fA: List[A])(f: A => B): List[B] =
    fA match {
      case Nil => Nil
      case (head :: rest) =>
        f(head) +: this.map(rest)(f)
    }
}
object OptionFunctor extends Functor[Option]{
  def map[A, B](fA: Option[A])(f: A => B): Option[B] =
    fA match {
      case None => None
      case Option(a) => Option(f(a))
    }
}
//...

Actually, apart from the famous map method, they should fit into a couple of properties:

  • Identity morphism: F[Id[A]] = Id[F[A]]. For example, being identity the identity function defined in Scala, Option(identity(1)) == identity(Option(1))
  • Morphism composition: If we have two morphisms f: A => B and g: B => C, it must be checked that F[f o g] = F[f] o F[g]. It’s not as complicated as it seems:
    val f: Int => String = _.toString
    val g: String => Boolean = _.length > 1
    val l: List[Int] = List(1,20,3)
    l.map(f).map(g) ==
      l.map(f andThen g) ==
      l.map(n => g(f(n)))
    //List(false, true, false)
    

Even though, we can describe functors (in the context of a F[_] production chain) as the instructions for transforming some given A input value into some B output value within the same F[_] production chain, by using a morphism (a transformation function) A => B.

Functor types

Ordinary functors are also known as co-variant functors (in order to differentiate itself from contravariant and invariant functors). Let’s se what makes the difference between these different kinds of functor:

Contravariant Functor

Formal definition says that a F[_] functor is contravariant if, instead of having the map method, it has a contramap method defined:

trait Contravariant[F[_]]{
  def contramap[A, B](fA: F[A])(f: B => A): F[B]
}

That’s it: if it exists a function B => A, the contramap method defines F[A] => F[B].

…ok, let’s stop being so hardcore. We’ll illustrate it with an example.

Imagine a type class that knows how to compare certain type elements:

type Comparison = Int
val Greater = 1
val Equal = 0
val Lower = -1

trait Comparator[T]{
  def compare(t1: T, t2: T): Comparison
}

Imagine as well, that I know how to compare integer numbers (and here comes the tricky tip):

if I know how to compare integers and I know how to convert ‘cucumbers’ into integer numbers, I do know how to compare ‘cucumbers’

object ComparatorF extends Contravariant[Comparator]{
  def contramap[A, B]
    (fA: Comparator[A])
    (f: B => A): Comparator[B] =
    new Comparator[B]{
      def compare(t1: B, t2: B): Comparison =
        fA.compare(f(t1), f(t2))
    }
}

And now, the so-expected example about how to generate a contravariant functor for cucumbers:

trait Cucumber
val intC: Comparator[Int] = ???
val cucumberToInt: Cucumber => Int = ???
val cucumberC: Comparator[Cucumber] =
  ComparatorF.contramap(intC)(cucumberToInt)

cucumberC.compare(new Cucumber{}, new Cucumber{})

…sublime…

Invariant functors

Invariant functors for F[_] are determined by the imap method:

trait Invariant[F[_]] {
  def imap[A, B](fA: F[A])(f: A => B)(g: B => A): F[B]
}

…once again the doubt is killing you: I know and I beg you for some time to explain properly. Let’s see some example.

Imagine a type class that knows how to store stuff in some database (MongoDB, for example):

case class ObjectId(hash: String)

trait DataStorage[T]{
  def store(t: T): ObjectId
  def get(id: ObjectId): T
}

If we forget about possible effects (exceptions, timeouts and so) for not messing up the example, we could define an invariant functor for DataStorage that allows storing any-kind elements:

object DataStorageF extends Invariant[DataStorage]{
  def invariant[A, B]
    (fA: DataStorage[A])
    (f: A => B)
    (g: B => A): DataStorage[B] = {

    new DataStorage[B]{
      def store(b: B): Option[ObjectId] =
        fA.store(g(b))
      def get(id: ObjectId): B =
        f(fA.get(id))
    }
  }
}

So…

If I know how to store integers and I know how to convert integers into cucumbers (and the other way round), I know how to store cucumbers!

val intDS: DataStorage[Int] = ???
val cucumberToInt: Cucumber => Int = ???
val intToCucumber: Int => Cucumber = ???
val cucumberDS: DataStorage[Cucumber] =
  DataStorageF
    .imap(intDS)(intToCucumber)(cucumberToInt)

val id = cucumberDS.store(new Cucumber{})
val originalCucumber = cucumberDS.get(id)

We couldn’t say this is all, but it may be a good introduction to the wonderful functor world. See you in the next poxt. ‘Like’ and share if you like storing cucumbers.
Peace out!

Sources:
[1] Advanced Scala with Cats – Noel Welsh & Dave Gurnell
[2] Variance and functors – Typelevel blog

Teoría de Cate-movidas: Functores y pepinos

Que manía con las categorías. ¿Nos pagan por hablar de ello? No. ¿Nos gustaría que lo hiciesen? Es muy probable. En otras ocasiones hablábamos de monoides y mónadas, pero esta vez le toca el turno a los functores. Los functores están por todas partes y no son los padres: podemos demostrarlo. Antes de detallar sus variantes, centrémonos en los conceptos clave.

¿Qué es un morfismo?

Una transformación entre dos espacios, un cambio, una mutación.
¿En Scala? Una función:

val f: A => B

¿Qué es un functor?

Respuesta corta y simple: el comportamiento que define, para un constructor de tipos F[A], el método ‘map’:

trait Functor[F[_]]{
  def map[A, B](fA: F[A])(f: A => B): F[B]
}

Existen functores para List, Option, Future, Try, …

object ListFunctor extends Functor[List]{
  def map[A, B](fA: List[A])(f: A => B): List[B] =
    fA match {
      case Nil => Nil
      case (head :: rest) =>
        f(head) +: this.map(rest)(f)
    }
}
object OptionFunctor extends Functor[Option]{
  def map[A, B](fA: Option[A])(f: A => B): Option[B] =
    fA match {
      case None => None
      case Option(a) => Option(f(a))
    }
}
//...

En realidad, a parte del famoso método map, deben cumplir un par de propiedades más:

  • Morfismo identidad: F[Id[A]] = Id[F[A]]. Por poner un ejemplo, siendo identity la función identidad definida en Scala, Option(identity(1)) == identity(Option(1))
  • Composición de morfismos: Si tenemos dos morfismos f: A => B y g: B => C, se debe cumplir que F[f o g] = F[f] o F[g]. Que no es tan complicado si lo vemos con
    val f: Int => String = _.toString
    val g: String => Boolean = _.length > 1
    val l: List[Int] = List(1,20,3)
    l.map(f).map(g) ==
      l.map(f andThen g) ==
      l.map(n => g(f(n)))
    //List(false, true, false)
    

Pero a grandes rasgos, podemos pensar en los functores ordinarios como la descripción de como, en una cadena de producción o montaje F[_], se permite realizar transformaciones de manera que, para argumento un A, y usando un morfismo (una función de transformación) A => B, obtenemos un B dentro de la misma cadena de producción F[_]

Clasificación de functores

Los functores ordinarios también son denóminados co-variantes (para ser diferenciados de los contravariantes y de los invariantes). Veamos a continuación qué caracteriza a estos otros tipos de functor:

Functor contravariante

La definición formal dice que un functor para F[_] es contravariante si, en vez el método map, tiene definida la operación contramap:

trait Contravariant[F[_]]{
  def contramap[A, B](fA: F[A])(f: B => A): F[B]
}

Esto es, si existe una función B => A, el functor define F[A] => F[B].

…venga va, sin ser hardcore, ponemos un ejemplo.

Imagina una type class que sabe comparar elementos de un cierto tipo:

type Comparison = Int
val Greater = 1
val Equal = 0
val Lower = -1

trait Comparator[T]{
  def compare(t1: T, t2: T): Comparison
}

Imagina del mismo modo que yo dispongo de un comparador de números enteros (y aquí viene el quid de la cuestión):

si yo se comparar enteros y se como transformar ‘pepinos’ a enteros, ya se como comparar ‘pepinos’

object ComparatorF extends Contravariant[Comparator]{
  def contramap[A, B]
    (fA: Comparator[A])
    (f: B => A): Comparator[B] =
    new Comparator[B]{
      def compare(t1: B, t2: B): Comparison =
        fA.compare(f(t1), f(t2))
    }
}

Y ahora el archi-esperado ejemplo de generar un functor contravariante para pepinos:

trait Cucumber
val intC: Comparator[Int] = ???
val cucumberToInt: Cucumber => Int = ???
val cucumberC: Comparator[Cucumber] =
  ComparatorF.contramap(intC)(cucumberToInt)

cucumberC.compare(new Cucumber{}, new Cucumber{})

…sublime…

Functor invariante

Los functores invariantes para F[_] se caracterizan por tener un método denominado imap como sigue:

trait Invariant[F[_]] {
  def imap[A, B](fA: F[A])(f: A => B)(g: B => A): F[B]
}

…otra vez en el valle de la duda después de esta definición, lo se y pido paciencia. Se ve mucho mejor con otro ejemplo.

Imagina una type class que sabe almacenar objetos en una base de datos (MongoDB, por ejemplo):

case class ObjectId(hash: String)

trait DataStorage[T]{
  def store(t: T): ObjectId
  def get(id: ObjectId): T
}

Olvidándonos de los posibles efectos (excepciones, timeouts, etc) para no liar el ejemplo, podemos definir un functor invariante para DataStorage que permita almacenar cualquier elemento:

object DataStorageF extends Invariant[DataStorage]{
  def invariant[A, B]
    (fA: DataStorage[A])
    (f: A => B)
    (g: B => A): DataStorage[B] = {

    new DataStorage[B]{
      def store(b: B): Option[ObjectId] =
        fA.store(g(b))
      def get(id: ObjectId): B =
        f(fA.get(id))
    }
  }
}

Por lo tanto…

Si yo se como almacenar enteros y se transformar pepinos a enteros (y viceversa),
¡se cómo almacenar pepinos!

val intDS: DataStorage[Int] = ???
val cucumberToInt: Cucumber => Int = ???
val intToCucumber: Int => Cucumber = ???
val cucumberDS: DataStorage[Cucumber] =
  DataStorageF
    .imap(intDS)(intToCucumber)(cucumberToInt)

val id = cucumberDS.store(new Cucumber{})
val originalCucumber = cucumberDS.get(id)

No podemos decir que esto sea todo, pero sí puede ser una buena introducción al maravilloso mundo de los functores. Nos vemos en el próximo post. ‘Like’ y comparte si te gusta almacenar pepinos.
¡Agur de limón!

Fuentes:
[1] Advanced Scala with Cats – Noel Welsh & Dave Gurnell
[2] Variance and functors – Typelevel blog

Graffiti Rules: playing with JSON [Snow]

A few months ago we talked about Spray, a toolkit that allowed us to build REST APIs in an easy way with a pretty complete DSL.

One of the components belonging to this toolkit is spray-json. This module allows us to serialize and deserialize our objects to/from a JSON format. Today we’ll see how to work with it quickly and easily.

How to create serializers to different classes? Well, there are two options depending on how the class we want to serialize is defined.

Easy option: when we have a case class

Well, that’s a piece of cake. The only thing we need to use is the jsonFormatN() method where N represents the number of arguments of the case class apply method. Let’s see it with an example:

case class Character(name: String, family: String, isDead: Boolean)

object MyJsonProtocol extends DefaultJsonProtocol {

 implicit val characterFormat = jsonFormat3(Character.apply)

}

As you can see, in order to create a serializer for the Character case class, we create an implicit value with the help of jsonFormat3 (as it has 3 attributes). Such an implicit object will be defined inside a trait which will extend from DefaultJsonProtocol. In this trait, the serializers for Scala basic types (Int, String, Boolean…) are defined… Easy peasy.

tumblr_mfuulmem1p1qem4feo1_250

Less easy option: when we don’t have a case class or we want to serialize a case class in a different way.

In such a case, we’ll need to implement how the serialization and deserialization of the given type should be. To do so, we may need to create an implicit object extending from RootJsonFormat[T] where T is the type we want to serialize. Such a trait contains two methods that need to be implemented. On the one hand, there is the write method, which converts a typeT in a Json, and on the other a method read, performing the reverse process. We’ll now see an example with the same type as before:

class Character(val name: String, val family: String, val isDead: Boolean)

object MyJsonProtocol extends DefaultJsonProtocol {

  implicit object CharacterJsonFormat extends RootJsonFormat[Character] {

    def write(c: Character) =
      JsArray(JsString(c.name), JsString(c.family), JsBoolean(c.isDead))

    def read(value: JsValue) = value match {
      case JsArray(Vector(JsString(name), JsString(family), JsBoolean(isDead))) =>
        new Character(name, family, isDead.toBoolean)
      case _ => throw new DeserializationException("Character expected")
    }
  }
}

As can be observed, it is a bit more tedious but not too complicated.

And how do we use it? We just have to import the object where we have defined the implicits and call the methods toJson or convertTo[T].

import MyJsonProtocol._

val json = Character("Jon Snow", "Stark", ???).toJson //....You know nothing!!!!
// Returns {"name": "Jon Snow", "family": "Stark", "isDead": ???}
val jonSnow = json.convertTo[Character]

giphy

Besides, if we use Spray’s REST API, the transformation will be done in a transparent way and it won’t be necessary to call  toJson or convertTo explicitely. But we’ll leave that to other post. Next week we’ll be talking about this library so we’d better see something of it before 🙂

See you all!

Grafitti Rules: jugando con JSON [Snow]

Hace ya unos meses hablamos de Spray, un toolkit que nos permitía construir API’s REST de una forma sencilla con un DSL bastante completo.

Uno de los componentes que forman el toolkit es spray-json. Con este modulo podemos serializar y deserializar nuestros objetos a un formato JSON. Hoy vamos a ver como trabajar con él de forma muy rápida y sencilla.

¿Cómo crear los serializadores de las distintas clases? Pues existen dos opciones en función de cómo esté definida la clase que queramos serializar.

Opción fácil: cuando tenemos una case class

Esto está tirado. Lo único que tenemos que utilizar es el método jsonFormatN() donde N representa el número de argumentos que tiene el método apply de la case class. Veamos un ejemplo:

case class Character(name: String, family: String, isDead: Boolean)

object MyJsonProtocol extends DefaultJsonProtocol {

 implicit val characterFormat = jsonFormat3(Character.apply)

}

Como se puede ver, para crear un serializador para la case class Character creamos un valor implícito con la ayuda de jsonFormat3 (ya que tiene 3 atributos). Dicho objeto implícito lo definiremos dentro de un trait que extenderá de DefaultJsonProtocol. En este trait están definidos los serializadores para los tipos básicos de Scala: Int, String, Boolean … Fácil y sencillo.

tumblr_mfuulmem1p1qem4feo1_250

Opción menos fácil: cuando no tenemos una case class o queremos serializar una case class de una forma distinta.

En este caso, es necesario picarnos a mano como debe ser la serialización y la deserialización del tipo en cuestión. Para ello, es necesario crear un implicit object que extienda de RootJsonFormat[T] donde T es el tipo que se quiere serializar. Dicho trait contiene dos métodos a implementar. Por un lado existe un método write, que convierte un tipo T en un Json, y por otro lado un tipo read, que realiza el proceso inverso. A continuación vemos un ejemplo con el mismo tipo que antes:

class Character(val name: String, val family: String, val isDead: Boolean)

object MyJsonProtocol extends DefaultJsonProtocol {

  implicit object CharacterJsonFormat extends RootJsonFormat[Character] {

    def write(c: Character) =
      JsArray(JsString(c.name), JsString(c.family), JsBoolean(c.isDead))

    def read(value: JsValue) = value match {
      case JsArray(Vector(JsString(name), JsString(family), JsBoolean(isDead))) =>
        new Character(name, family, isDead.toBoolean)
      case _ => throw new DeserializationException("Character expected")
    }
  }
}

Como se puede observar, es un poco más tedioso pero no demasiado complicado.

¿Y cómo lo usamos? Basta con importar el objeto donde hemos definido los implícitos y realizar llamadas a los métodos toJson o convertTo[T].

import MyJsonProtocol._

val json = Character("Jon Snow", "Stark", ???).toJson //....You know nothing!!!!
// Returns {"name": "Jon Snow", "family": "Stark", "isDead": ???}
val jonSnow = json.convertTo[Character]

giphy

Además, si usamos la API REST de Spray, la transformación se hará de forma transparente y no será necesario llamar a toJson o convertTo de forma explícita. Pero esto para otro post. La semana que viene, se hará una pequeña mención a esta librería, por lo que no venía mal dar unas pequeñas pinceladas antes 🙂
Agur de limón!

Recursion recursive recursively.

Today we will discuss about recursion. Don’t you know what is the recursion? Don’t worry, now we are going to talk about recursion. Don’t you know what is the recursion? Don’t worry, now we are going to talk about recursion. Don’t you know what is the recursion?  Don’t worry, now we are going to talk about recursion. Do …. Well, as a joke it’s ok 🙂

Because Scala is a language that, despite being object-oriented, its true potential lies largely in its functional part, it is normal that recursion has a special importance. However, even more important, it is to generate the recursive calls properly to not have a stack overflow.

Stack Overflow: plus a pretty famous page, is what happens when we perform many recursive calls and, in consequence, the stack memory is overflowed.

szpjhwz

In order to generate recursive calls properly it is necessary that the function will be tail-recursive. This means that the function needn’t to stored in memory the result of the recursive call. Thus, a stack overflow is not triggered. It can also be seen as a recursive function when the function only calls itself with different arguments. Examples of functions that do not meet the tail-recursive condition are those in which operations are performed with the results of the recursive calls. For example, the factorial function encoded on this way:

def factorial(n: Int): Int =
  if (n <= 1) 1
  else n * factorial(n - 1)

because the call is multiplied by n, it will not perform a tail-recursive recursion.

And how do you know if a function is tail-recursive? Scala makes the whole thing easy. We can add the tailRecursive annotation in this function so that if it has not been written on a tail-recursive way, Scala return us a compilation error. The compiler makes the work for us 🙂

Let’s see how we can build a function which returns the element n of the Fibonacci sequence (a tipical example). First without tail-recursive:

@annotation.tailrec
def fibonacci(n : Int) : Int = n match {
  case 0 | 1 => n
  case _ => fibonacci( n-1 ) + fibonacci( n-2 )
}

This returns a compilation error like this:

“could not optimize @tailrec annotated method fibonacci: it contains a recursive call not in tail position”

However, if we think a little more we can get it a function much efficient 🙂

def fibonacci(n: Int): Int = {

  @annotation.tailrec
  def loop(i: Int, previous: Int, current: Int): Int =
    if (i == 0) previous
    else loop(i - 1, current, previous + current)

  loop(n, 0, 1)
}

In this case there will be no compilation error.

28b5865ebe59280d5c3ed18fc1147964309d9d0c81663c0c3f81d42fc5979c8f

And that’s all. And that’s all. And that’s …

Recursividad recursivamente recursiva

Hoy hablaremos de la recursividad. ¿No sabés lo que es la recursividad? No te preocupes, hoy hablaremos de la recursividad. ¿No sábes lo que es la recursividad? No te preocupes, hoy hablaremos de la recursividad. ¿No sabes lo que es la recursividad? No te preocupes, hoy hablaremos de la recursividad. ¿No sa….bueno, como broma ya está bien 🙂

Debido a que Scala es un lenguaje que, a pesar de ser orientado a objetos, su verdadero potencial reside en gran parte en su parte funcional, es normal que la recursividad sea un factor importante. Sin embargo, aún más importante es generar las llamadas recursivas de forma correcta para no provocar un stack overflow.

Stack Overflow: además de una página bastante famosa, es lo que ocurre cuando realizamos tantas llamadas recursivas que la pila de memoria se llena.

szpjhwz

Para generar las llamadas recursivas de forma correcta es necesario que la función sea tail-recursive. Esto quiere decir, que la función no necesita guardarse nada en memoria a la espera del resultado de la llamada recursiva. De esta forma no se provocará un overflow de la pila. También puede verse como una función que en el caso recursivo solamente se llama a si misma con distintos argumentos. Ejemplos de funciones que no cumplen la condición tail-recursive son aquellas en las que se realizan operaciones con los resultados de las llamadas recursivas. Por ejemplo, la función factorial codificada de la siguiente manera:

def factorial(n: Int): Int =
  if (n <= 1) 1
  else n * factorial(n - 1)

al estar multiplicada la llamada por n, no cumplirá una recursividad tail-recursive

¿Y cómo saber si una función es tail-recursive? Scala nos lo pone fácil. Podemos añadir la anotación tailRecursive en dicha función para que en caso de que no se haya codificado de forma tail-recursive, Scala nos devuelva un error de compilación. El compilador nos hace el trabajo 🙂

Vamos a ver como lo haríamos con la función que nos devuelve el elemento n de la sucesión de Fibonacci (un clásico). En primer lugar sin tail-recursive:

@annotation.tailrec
def fibonacci(n : Int) : Int = n match {
  case 0 | 1 => n
  case _ => fibonacci( n-1 ) + fibonacci( n-2 )
}

Esto nos devuelve un error de compilación tal que así:

“could not optimize @tailrec annotated method fibonacci: it contains a recursive call not in tail position”

Sin embargo, si pensamos un poco más podremos conseguir la misma función mucho más eficiente 🙂

def fibonacci(n: Int): Int = {

  @annotation.tailrec
  def loop(i: Int, previous: Int, current: Int): Int =
    if (i == 0) previous
    else loop(i - 1, current, previous + current)

  loop(n, 0, 1)
}

En este caso no habrá ningún error de compilación.

28b5865ebe59280d5c3ed18fc1147964309d9d0c81663c0c3f81d42fc5979c8f

Y hasta aquí este post. Y hasta aquí este post. Y hasta aquí este …

Transforming the Future

A few weeks ago we talked about the type Future and its use to create asynchronous calls.

We saw how to work with blocking calls to obtain the value of the future. We also used callbacks in order to obtain the result of the future asynchronously. However, there are some issues that were left unsaid. And by that I’m referring to transforming the Future without blocking the execution.

Future transformations

In order to transform futures, as with other Scala basic types, mainly two methods are used: map and flatmap.

Map method

Map method allows us to change the content of a future by applying a function. For instance, if we have a method to get the first million prime numbers but we want to transform it to return just the first hundred ones, we can apply the map method in the following way:

def getFirstMillionOfPrimes(): Future[List[Int]] = ???

getFirstMillionOfPrimes().map(
  (list: List[Int]) => list.take(100)
)

This way we will be transforming the inside of the future without breaking the asynchrony.

pi2band2bi

FlatMap method

On the other hand, the flatMap method allows us to apply a function to the content of the future and returning a future in turn. After that, a flatten operation is applied to convert the Future[Future[A]] into a simple Future[A]. What the f…? Better explained with an example.

Imagine we want to concatenate the first million prime numbers in a string. To do so, we’ll use a new method:

def concatenate(l: List[Int]): Future[String] = ???

and now we perform a  flatMap

getFirstMillionOfPrimes().flatMap(
  (list: List[Int]) => concatenate(list)
) //Future[String]

And how can we do all this in a more simple way?

Easy question. For comprehension to the rescue! With a spoonful of syntactic sugar we can write a much more readable code.

for {
  primes <- getFirstMillionOfPrimes()
  primesString <- concatenate(primes)
} yield primesString

This way, the concatenation operation won’t be applied until the prime numbers are obtained with the method getFirstMillionPrimes.

This allows us to keep an order when composing asynchronous calls. Besides, if the first asynchronous call fails, the second won’t be conducted.

And that’s all for today. Now you know how to change the future. What a shame not to be able to change the past 😦

doesnt-go-into-girls-shower

See you soon!