Shapeless: polymorphic functions

Time ago, our friend Javier Fuentes illustrated us with an introduction to Shapeless.
Some months after that, at Scala Madrid meetup, he offered a pretty interesting speech about structural induction with Shapeless and HLists. We couldn’t avoid it and we got the enthusiasm flu 馃槢

What we want to achieve

Let’s set as our study case what I think more than one has thought before: how can I compose in the same for-comprehension different types. Something like:

import scala.util.Try

for {
  v1 <- List(1,2,3)
  v2 <- Try("hi, person ")
} yield s"$v2 $v1"

which usually comes from the hand of the following frustrating error:

<console>:15: error: type mismatch;
 found   : scala.util.Try[String]
 required: scala.collection.GenTraversableOnce[?]
         v2 <- Try("hi, person ")
            ^

Therefore we need a way to transform these data types (Future, Try) into iterable ‘stuff’ (GenTraversable[T] might work). In our example we won’t have in mind the information that we loose about the error that might happen, for example, if certain Try or Future expression has failed. For have a better understanding about the problem we present, let’s talk about some theory.

53132063

Monomorphism vs polymorphism

We say a method is monomorphic when you can only invoke it with parameters whose concrete type is explicitly declared in the method signature, whilst the polymorphic methods can take parameters of any type while it fits in the signature (in case of Scala language: parameter types). Speaking proper English:

def monomorphic(parameter: Int): String

def polymorphic[T](parameter: T): String

Polimorphism

It’s also good to know that a method can be polymorphic due to parameter types or just to parameter subtyping. E.g.:

def parametricallyPolymorphic[T](parameter: T): String

def subtypedPolymorphic(parameter: Animal): String

subtypedPolymorphic(new Cat)

If we use parameter types and we have NO information at all about those types, we are in front of a parametric polymorphism case.

If we use parameter types but we need any extra view / context bound for that type (T <: Whatever o T:TypeClass), then we are talking about ad-hoc polymorphism.

Problem: Function values

There’s not such a problem when using parametric polymorphism and methods but, what about function values? In Scala, it cannot be achieved and therefore it produces some lack of expressiveness:

val monomorphic: Int => String = _.toString

val anotherMonomorphic: List[Int] => Set[Int] = 
  _.toSet

Please, notice the definition of the function that trasforms a List into a Set. It could be totally independant of the list element type, but Scala syntax doesn’t allow to define something similar. We could try asigning the method to a val (Eta expansion):

def polymorphic[T](l: List[T]): Set[T] = l.toSet

val sadlyMonomorphic = polymorphic _

But the compiler (as clever as usual) wil infer that the list contained type is Nothing: a special one, but concrete as the most.

64331666

Shapeless parametric polymorphism

How does Shapeless solve this problem? If we had to define a transformation function from Option to List in Scala, we’d have the previously mentioned limitation for using function values and we could only achieve it by defining a method:

def toList[T](o: Option[T]): List[T] =
  o.toList

However, Shapeless, using its alchemy, provides us some ways to do so. In category theory, when talking about type constructors transformations, it’s so called natural transformations. First of them has the following notation:

import shapeless.poly._

val polyFunction = new (Option ~> List){
  def apply[T](f: Option[T]): List[T] = f.toList
}

If you have a closer look at it, the parametric polymorphism is moved to the method inside the object. Using this function is as simple as:

val result: List[Int] = polyFunction(Option(2))

The other possible notation consists on defining the function behavior based on cases, in other words, if we want the function to be defined only for Int, String and Boolean, we’ll add a case for each of them.

import shapeless.Poly1

object polymorphic extends Poly1 {

  implicit optionIntCase = 
    at[Option[Int]](_.toList.map(_ + 1))

  implicit optionStringCase = 
    at[Option[String]](_.toList.map(_ + " mutated"))

  implicit optionBooleanCase = 
    at[Option[Boolean]](_.toList.map(!_))

}

As you can see, if we want our function to be defined at the case where the input parameter is an Option[Int], we define that all contained elements in the list are added to 1.

This expression returns a this.Case[Option[Int]], where this refers to polymorphic object that we are defining:

implicit optionIntCase = 
  at[Option[Int]](_.toList.map(_ + 1))

The good part of this? In case we wanted to use the funcion on a input type that doesn’t have a defined case at the function, we’ll get a compile-time error (Awesome, right?):

The result

Applying this last way (based on cases), we get the expected result that we mentioned in the introductory section: to be able to use a for-comprehension for composing different typed values: iterables, Try, Future…

The proposed solution can be found in the following file.

In our function we have a case for GenTraversable, another for Try and Future (this last one needs to have its expression evaluated for being able to iterate over it, so we need a timeout for waiting):

object values extends Poly1 {

  implicit def genTraversableCase[T,C[_]](implicit ev: C[T] => GenTraversable[T]) = 
    at[C[T]](_.toStream)

  implicit def tryCase[T,C[_]](implicit ev: C[T] => Try[T]) = 
    at[C[T]](_.toOption.toStream)

  implicit def futureCase[T,C[_]](implicit ev: C[T] => Future[T], atMost: Duration = Duration.Inf) =
    at[C[T]](f => Try(Await.result(f,atMost)).toOption.toStream)

}

Now we can use it in our controversial code snippet:

import scala.concurrent.ExecutionContext.Implicits.global

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

val result: Stream[_] = for {
  v1 <- values(List(1,2,3))
  v2 <- values(Set("hi","bye"))
  v3 <- values(Option(true))
  v4 <- values(Try(2.0))
  v5 <- values(Future(User("john",15)))
} yield (v1,v2,v3,v4,v5)

The sole solution?

At all! you can always implement it using traditional Scala type classes, though it implies defining a trait that represent the ADT iterable. You can take a look at the example at the following gist content.

Peace out!

Shapeless: funciones polim贸rficas

Hace ya un tiempo, nuestro amigo Javier Fuentes nos ilustr贸 con una introducci贸n a Shapeless.
Unos meseses despu茅s, en el meetup de Scala en Madrid, dio una interesante charla sobre inducci贸n estructural con Shapeless y HLists. No pudimos evitarlo y nos contagiaron el entusiasmo 馃槢

Lo que queremos hacer

Pongamos como caso de estudio lo que yo creo que a m谩s de uno le ha debido pasar: querer mezclar en la misma for-comprehension distintos tipos. Algo del estilo:

import scala.util.Try

for {
  v1 <- List(1,2,3)
  v2 <- Try("hi, person ")
} yield s"$v2 $v1"

con la consiguiente frustraci贸n que produce ver el siguiente error:

<console>:15: error: type mismatch;
 found   : scala.util.Try[String]
 required: scala.collection.GenTraversableOnce[?]
         v2 <- Try("hi, person ")
            ^

Necesitamos por tanto, una manera de transformar estos tipos de datos (Future, Try) en ‘cosas’ iterables (algo GenTraversable[T] nos podr铆a valer). En nuestro ejemplo no tendremos en cuenta la informaci贸n sobre el error si, por ejemplo, un tipo Try o un Future ha fallado e impide seguir evaluando la for-comprehension. Para entender un poco mejor el problema planteado, vamos a ver algunas pinceladas de teor铆a.

53132063

Monomorfismo vs polimorfismo

Se define un m茅todo como monom贸rfico cuando solo se puede aplicar al tipo que indican los argumentos en su signatura, mientas que los m茅todos polim贸rficos pueden aplicarse a argumentos de cualquier tipo (siempre que encajen en la signatura: en el caso de Scala, tipos parametrizados). En cristiano:

def monomorphic(parameter: Int): String

def polymorphic[T](parameter: T): String

Tipos de polimorfismo

Otra cuesti贸n importante es que un m茅todo puede ser polim贸rfico debido a los parameter types o bien por sub-tipado, por ejemplo:

def parametricallyPolymorphic[T](parameter: T): String

def subtypedPolymorphic(parameter: Animal): String

subtypedPolymorphic(new Cat)

Si usamos parameter types, y no tenemos NADA de informaci贸n sobre dichos tipos, nos encontramos ante un caso de polimorfismo param茅trico.

Si usamos parameter types pero tenemos alg煤n view / context bound sobre dicho tipo ( T <: Whatever o T:TypeClass ), entonces hablamos de polimorfismo ad-hoc.

Problema: Function values

Con los m茅todos no hay problema a la hora de usar gen茅ricos pero, 驴qu茅 ocurre con los valores que son funciones? En Scala, el polimorfismo param茅trico no puede expresarse en base a valores que son funciones:

val monomorphic: Int => String = _.toString

val anotherMonomorphic: List[Int] => Set[Int] = 
  _.toSet

N贸tese que la definici贸n de una funci贸n que pasa de List a Set es independiente del tipo de elemento que contiene la lista; pero la sintaxis de Scala no nos permite definir nada parecido. Podr铆amos intentarlo asignando a un val (eta expansion) :

def polymorphic[T](l: List[T]): Set[T] = l.toSet

val sadlyMonomorphic = polymorphic _

Pero el compilador, que es muy listo, inferir谩 que que el tipo de la lista es Nothing: un tipo peculiar, pero concreto al fin y al cabo.

64331666

Polimorfismo param茅trico en Shapeless

驴C贸mo soluciona este problema Shapeless? Si por ejemplo tuvi茅ramos que definir una funci贸n de transformaci贸n de Option a List en Scala, tendr铆amos la limitaci贸n antes citada para usar function values y s贸lo podr铆amos hacerlo definiendo un m茅todo:

def toList[T](o: Option[T]): List[T] =
  o.toList

Sin embargo Shapeless, haciendo gala de toda su alquimia, nos aporta varias formas de tener function values polim贸rficas. Es lo que en teor铆a de categor铆as, cuando hacemos referencia a transformaciones de constructores de tipos, se denomina transformaciones naturales. La primera de ellas tiene la siguiente notaci贸n:

import shapeless.poly._

val polyFunction = new (Option ~> List){
  def apply[T](f: Option[T]): List[T] = f.toList
}

Fijaros que lo que hace es trasladar el polimorfismo param茅trico a la definici贸n del objeto. Para usar posteriormente esta funci贸n basta con:

val result: List[Int] = polyFunction(Option(2))

La otra notaci贸n posible consiste en definir el comportamiento de la funci贸n en base a casos, es decir, si queremos que la funci贸n solo valga para Int, String y Boolean, a帽adir铆amos un caso para cada uno de estos tipos.

import shapeless.Poly1

object polymorphic extends Poly1 {

  implicit optionIntCase = 
    at[Option[Int]](_.toList.map(_ + 1))

  implicit optionStringCase = 
    at[Option[String]](_.toList.map(_ + " mutated"))

  implicit optionBooleanCase = 
    at[Option[Boolean]](_.toList.map(!_))

}

Como pod茅is ver, si queremos que nuestra funci贸n est茅 definida para el caso en que un argumento de entrada sea Option[Int], definimos que a todos los elementos de la lista que se devuelve, por ejemplo, se les sume 1.

Esta expresi贸n devuelve un this.Case[Option[Int]], donde this hace referencia a la funci贸n polymorphic que estamos definiendo:

implicit optionIntCase = 
  at[Option[Int]](_.toList.map(_ + 1))

驴Lo bueno de esto? Que en caso de usar la funci贸n sobre un tipo de entrada que no tiene un caso definido en la funci贸n, obtendremos un error en tiempo de compilaci贸n (Brutal, 驴no?):

El resultado

Aplicando esta 煤ltima forma de expresar funciones polim贸rficas en base a casos, obtenemos el resultado deseado que se planteaba en la introducci贸n: poder usar una for-comprehension sobre valores de distintos tipos: iterables, Try, Future…

Pod茅is ver en detalle la soluci贸n propuesta en el siguiente fichero.

En nuestra funci贸n tenemos un caso para los GenTraversable, el tipo Try y el tipo Future (en este 煤ltimo caso necesitamos disponer del valor del futuro para poder iterar sobre 茅l, de manera que nos hace falta un timeout):

object values extends Poly1 {

  implicit def genTraversableCase[T,C[_]](implicit ev: C[T] => GenTraversable[T]) = 
    at[C[T]](_.toStream)

  implicit def tryCase[T,C[_]](implicit ev: C[T] => Try[T]) = 
    at[C[T]](_.toOption.toStream)

  implicit def futureCase[T,C[_]](implicit ev: C[T] => Future[T], atMost: Duration = Duration.Inf) =
    at[C[T]](f => Try(Await.result(f,atMost)).toOption.toStream)

}

Ahora podremos utilizarlo en nuestro controvertido snippet de c贸digo:

import scala.concurrent.ExecutionContext.Implicits.global

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

val result: Stream[_] = for {
  v1 <- values(List(1,2,3))
  v2 <- values(Set("hi","bye"))
  v3 <- values(Option(true))
  v4 <- values(Try(2.0))
  v5 <- values(Future(User("john",15)))
} yield (v1,v2,v3,v4,v5)

驴脷nica soluci贸n?

隆En absoluto!, siempre se puede implementar usando type classes tradicionales de la huerta de Scala, aunque implique definir un trait que represente el iterable del ADT. Puedes ver el ejemplo en el contenido del siguiente gist.

隆Agur de lim贸n!

Curry, please…

One of the Scala’s rock starts that we cannot miss the chance to speak about is currying.

4252082-curry

What theory says

If we have a function (T,U) => V, currying it implies decomposing the function in a simpler one that allows building the result incrementally. In that case, we would get a function T => (U => V), what means that, from a T value we get a function whose only need is a U value for generating a V one. Messy? Let’s take a better look with next example.

Let’s suppose that we have a case class for modeling the student entity:

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

We could have a method for instantiate a student: oh wait, like method apply, which has been automatically generated by creating the case class:

//Auto generated code below
object Student {

  def apply(
    name: String, 
    age: Int, 
    enrolled: Boolean): Student =
    new Student(name, age, enrolled)

}

By using such method, we can create a Student as shown below:

Student("john", 18, enrolled=true)

So easy so far. So let’s imagine next requirement:

In our student admission process, the candidate has to provide his/her personal data sequentially in a set of windows (At window A name must be provided. At window B so must the age. And finally, at window C, we would admit or not the candidate by setting the ‘enrolled’ attribute).

First approach: Classes are free!

We can define our windows as type aliases of transforming functions (so redundant…). I mean:

type WindowA = String => NotAStudientYet
type WindowB = (NotAStudentYet, Int) => AlmostAStudent
type WindowC = (AlmostAStudent, Boolean) => Student

case class NotAStudentYet(name: String)
case class AlmostAStudent(name: String, age: Int)

Take a look that windows are represented as functions.
So first window is a function that, given a name, it generates a “not-a-student-yet-like” object.
Second window takes as parameters a NotAStudientYet and the age of the subject, and it returns an “almost-a-student”.
And the last one takes an “almost-a-student” and an admission or rejection parameter, which will finally allow generating a Student.

So for our purpose, with this first approach, we have created a couple of new classes that will be used as data-accumulators for, at the end, creating a Student.

The implementation should look like:

val windowA: WindowA = 
  (name) => 
    NotAStudentYet(name)

val windowB: WindowB = 
  (notStudent, age) => 
    AlmostStudent(notStudent.name, age)

val windowC: WindowC = 
  (almost, enrolled) => 
    Student(almost.name, almost.age, enrolled)

…sincerely, there’s no way to think that for doing such a thing, we have define additional classes. Let’s try another way.

Second approach: functions, functions everywhere …

Let’s have a try to defining functions that return another functions (higher order functions):

type WindowA = String => WindowB
type WindowB = Int => WindowC
type WindowC = Boolean => Student

val windowA: WindowA = 
  (name: String) => {
    val windowB: WindowB =
      (age: Int) => {
        val windowC: WindowC =
          (enrolled: Boolean) =>
            Student(name, age, enrolled)
        windowC
      }
    windowB
  }

By using a bunch of little functions, we’re setting values to all parameters that will build our Student. It’s pretty easier if we try to read the code from the most inside function to the most outside one (first windowC, then windowB and finally windowA). For invoking our function it’s enough with executing:

val student = windowA("john")(18)(true)

Third approach: U sure there’s nothing existing for this?

Of course it is. Inside the Function companion object in Scala, you can find curried method, which purpose is to separate a function that takes N parameters, in N concatenated functions, as we were previously discussing and with the last example as well.

For applying this wonder to the exposed example, it’s as easy as writing:

val f = (Sudent.apply _).curried
//f: String => (Int => (Boolean => Student))

f("john")(18)(true)
//Student("john", 18, true)

The reverse function called uncurried can also be found at the same Function companion object, so that N concatenated functions, for example, Int => (String => (Boolean => Double))) are converted to a single function that takes N different parameters: (Int, String, Boolean) => Double:

val myApply = Function.uncurried(f)
//myApply: (String, Int, Boolean) => Student

myApply("john",18,true)
//Student("john",18,true)

Easy peasy.
Peace out! 馃檪

Curry, por favor…

Uno de los aportes de Scala de los que no podemos dejar pasar la ocasi贸n de hablar acerca de ellos es el currying.

4252082-curry

La teor铆a

Si tenemos una funci贸n (T,U) => V, currificar la funci贸n supone descomponer la funci贸n en otra m谩s sencilla que permite construir el resultado de manera incremental. En este caso pasar铆amos a tener una funci贸n T => (U => V), es decir, a partir de un T obtenemos una funci贸n que solo necesita un U para generar un V. 驴Lioso? Ve谩moslo mejor con el siguiente ejemplo.

Supongamos que tenemos una case class que modela un estudiante:

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

Podr铆amos tener adicionalmente un m茅todo que nos instanciara un estudiante como, por ejemplo, el m茅todo apply que se ha generado autom谩ticamente para la case class:

//Auto generated code below
object Student {

  def apply(
    name: String, 
    age: Int, 
    enrolled: Boolean): Student =
    new Student(name, age, enrolled)

}

Utilizando dicho m茅todo, podemos construir un estudiante como sigue:

Student("john", 18, enrolled=true)

Hasta aqu铆 f谩cil. Ahora supongamos la siguiente situaci贸n:

En nuestro proceso de admisi贸n de alumnos, el candidato tiene que pasar por una serie de ventanillas para aportar su documentaci贸n poco a poco (en la ventanilla A indicar铆a el nombre, en la ventanilla B indicar铆a la edad; y en la ventanilla C le dar铆amos el visto bueno, o no, para formar parte de la escuela).

Primera aproximaci贸n: Hacer clases es gratis

Podemos definir nuestras ventanillas como alias de funciones transformadoras. Es decir:

type WindowA = String => NotAStudientYet
type WindowB = (NotAStudentYet, Int) => AlmostAStudent
type WindowC = (AlmostAStudent, Boolean) => Student

case class NotAStudentYet(name: String)
case class AlmostAStudent(name: String, age: Int)

Fijaros que, por una parte, las ventanillas se representan mediante funciones.
La primera ventanilla es una funci贸n que, a partir de un nombre, genera algo “que a煤n no es estudiante”.
La segunda ventanilla, teniendo algo “que a煤n no es estudiante” y recibiendo una edad, devuelve algo que “casi es un estudiante”.
Y la 煤ltima ventanilla recibe algo “que casi es un estudiante” y una aprobaci贸n de admisi贸n (aprobada o denegada) y genera un estudiante.

Para ello, en esta primera aproximaci贸n, hemos generado dos case classes nuevas, que van a servir de acumuladores, para finalmente crear un estudiante.

La implementaci贸n ser铆a algo del estilo:

val windowA: WindowA = 
  (name) => 
    NotAStudentYet(name)

val windowB: WindowB = 
  (notStudent, age) => 
    AlmostStudent(notStudent.name, age)

val windowC: WindowC = 
  (almost, enrolled) => 
    Student(almost.name, almost.age, enrolled)

…sinceramente, no es posible que para hacer tal cosa tengamos que definirnos dos clases adicionales. Optemos por dar otro enfoque.

Segunda aproximaci贸n: Funciones, funciones everywhere …

Probemos a definir funciones que devuelvan otras funciones (funciones de orden superior):

type WindowA = String => WindowB
type WindowB = Int => WindowC
type WindowC = Boolean => Student

val windowA: WindowA = 
  (name: String) => {
    val windowB: WindowB =
      (age: Int) => {
        val windowC: WindowC =
          (enrolled: Boolean) =>
            Student(name, age, enrolled)
        windowC
      }
    windowB
  }

Fijaros que a partir de peque帽as funciones, vamos dando valores a los par谩metros que construir谩n nuestro estudiante. Es m谩s f谩cil si intentamos leerlo desde la funci贸n m谩s interior a la mas exterior(primero windowC, despu茅s windowB y finalmente windowA). Para invocar nuestra funci贸n basta con ejecutar:

val student = windowA("john")(18)(true)

Tercera aproximaci贸n: 驴Seguro que no existe nada que haga esto?

Por supuesto que lo hay. Dentro del companion de Function en Scala, se encuentra el m茅todo curried, cuyo cometido es descomponer una funci贸n que recibe N argumentos en N funciones concatenadas, como ve铆amos al principio del post, y en el 煤ltimo ejemplo.

Para aplicar esta maravilla al ejemplo expuesto bastar铆a con escribir:

val f = (Sudent.apply _).curried
//f: String => (Int => (Boolean => Student))

f("john")(18)(true)
//Student("john", 18, true)

Existe adem谩s la funci贸n inversa uncurried, que dadas N funciones encadenadas, por ejemplo, Int => (String => (Boolean => Double))) devuelve una 煤nica funci贸n que recibe N argumentos: (Int, String, Boolean) => Double:

val myApply = Function.uncurried(f)
//myApply: (String, Int, Boolean) => Student

myApply("john",18,true)
//Student("john",18,true)

F谩cil, sencillo y para toda la familia.
Agur de lim贸n 馃檪