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

Anuncios

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