Type Class 101: Applicative

Gestaltwechsel

In the last installation of this series, we covered the Functor and now we take a turn to discuss the Applicative type class.

It’s all about functions

Being functional programmers, the thing we embrace most are functions. Despite scala being an object-functional language, I fell in love with it, due to it’s possibilities to write code using the functional paradigm and not state mutating object nonsense. And I believe it is a good exercise, if you (like me) come from a java background to emphasize functions over objects first. It is a different way of approaching problems, and it needs getting used to, but it pays of in the end.

Having said all that, let us remember that functions come in different flavours, they can have one parameter or multiple parameters and return a value and if they don’t return a value, but Unit we basically know that this function stinks. It is no wonder then that functions can be transformed to take on a new Gestalt:

Gestalt Functiosopy

What this tells us, that we can turn any function expecting multiple parameters in a function with one parameter (tupled), or in function were we can apply the parameters “lazily” in the curried version. We can also revert these forms into the original “multiple parameter” style. And don’t worry about the different use of “X” and “-” in the table, I just got carried away.

The problem with our Functor typeclass and map

map takes a function f: A => B and applies this function in a context F. What about functions taking more than one parameter? For example if we have a function f: A => B => C and do Functor[Option].map(Some(3))(f) we would end up with a value of Some(B => C):

val add : Int => Int => Int = x => y => x + y
Functor[Option].map(Some(3))(add)

add: Int => (Int => Int) = <function1>
>>> res0: Option[Int => Int] = Some(<function1>)
  • Problem 1: we cannot continue to map over the resulting value, which is a function in the context of Option, whereas map does not provide that type signature. Try on your own, to see what happens, if you try to continue to map over the resulting value (spoiler: compiler errors happen, but which ones?)
  • Problem 2: we cannot supply 2 parameters to map as in the fictional Functor[Option].map(Some(3), Some(4)).map(add)

Workaround

One workaround to our problem with map, could be to transform any function to their tupled representation, and map over a tuple, as in:

def add(x: Int, y: Int) = x + y
Functor[Option].map(Some((3,4)))((add _).tupled)
>>>  res0: Option[Int] = Some(7)
  • Problem 3: Though this seems to work, it is clumsy, and what happens, if we do not have all values at hand, e.g. if we want to add Some(3) and None. How would we build a tuple from that?

Applicative

Having understood these problems, we can introduce the Applicative type class. It solves our problems, and as an aside has some very funny properties, which make it super powerful. Boiled down to its core interface the Applicative looks like this:

trait Applicative[F[_]] {
  // other functions ommitted for now

  def ap[A, B](fa: => F[A])(f: => F[A => B]): F[B]
}

Let’s have a look at the problems which we have described above and see how an Applicative might help. The signature of ap seems to suggest that we can apply a value A in context F to a function A=>B which resides in a context F and get a result B in the context of F. WTF?

Option ap

Or in plain english: If we have an optional parameter and apply it to an optional function we get an optional result. The same for the context List: if we have a list of parameter values and a apply those to a list of functions we get a list of results. If the list of functions or parameters would be empty, we would get an empty list of results. Cool, eh? (we observe that an Applicative executes functions in a context, and preserves that context.)

Interlude

Before we can consider the other problems, we introduce two more functions to the Applicative trait:

trait Applicative[F[_]] extends Functor[F] {
  def pure[A](a: A): F[A]

  def ap[A, B](fa: => F[A])(f: => F[A => B]): F[B]

  override def map[A, B](fa: F[A])(f: A => B): F[B] =
    ap(fa)(pure(f))
}

One is pure (often aliased as point) and one is the fact that every Applicative is also a Functor, and we can implement map in terms of the functions of ap and pure. pure is the function which allows us to put a single value A into some context F. In plain scala this would often be the apply method of the companion object, and with pure we have the means to abstract over the construction of values in a context. Every Applicative is also a Functor as we can simply lift the function f into the context F using pure and then use ap to apply the value to the function inside the context.

Here are some sample instances:

val optionApplicativeInstance : Applicative[Option] = new Applicative[Option] {
  override def pure[A](a: A): Option[A] = Some(a)

  override def ap[A, B](fa: => Option[A])(f: => Option[(A) => B]): Option[B] = {
    (fa, f) match {
      case (Some(fa1), Some(f1)) => Some(f1(fa1))
      case _ => None
    }
  }
}

val listApplicativeInstance : Applicative[List] = new Applicative[List] {
  override def pure[A](a: A): List[A] = List(a)
  override def ap[A, B](fa: => List[A])(f: => List[(A) => B]): List[B] = {
    for { // cheating as I implement this using flatMap which is a function of monads.
      fa1 <- fa
      f1 <- f
    } yield (f1(fa1))
  }
}

Problem solving continued

Let’s try to tackle problem 2 and find a way to supply 2 arguments to a function f: (A,B) => C. In fact Applicative contains lots of derived functions, and some of them are ap2ap22, where the number denotes the number of arguments of our function.

def ap2[A,B,C](fa: => F[A],fb: => F[B])(f: F[(A,B) => C]) : F[C] =
  (ap(fb)(ap(fa)(map(f)(_.curried))))

Step by Step: * we map over the function f, thus looking into the context, and create the curried version of our function A => B => C * after leaving map, we have F[A => B => C] * we apply fa, resulting in F[B => C] and * apply fb which results in * F[C].

q.e.d. Yikes!

There is another group of functions associated with Applicative which are the applyN functions. The difference to apN, is that they do not take function(s) in a context, but just a plain function and put it in the context via pure for us.

def apply2[A,B,C](fa: => F[A],fb: => F[B])(f: (A,B) => C) : F[C] =
  ap2(fa,fb)(pure(f))

Notes

The naming conventions and precise structure within Applicative can vary between differnt type class libraries. For example most of the functions in scalaz are implemented in Apply with Applicative adding the point/pure function. In my own testbed [simplez][http://github.com/inoio/simplez] I unified this classes and the type classes in the play framework, again use pure instead of point and does not inherit directly from Functor, but implements map directly. But in the end, it all boils down to the same thing.

Further learning

The books Functional programming in Scala and Scala in Depth both cover the essentials of Applicatives very well.

That’s it?

No, there will be a part 2 for Applicatives in this series covering the ApplicativeBuilderand a (gosh!) practical example. Slowly but steady we continue to build our type class toolbox. As we will see, the previous classes will pop up here and there again, especially when we want to use Applicatives to “collect information” while still keeping the control flow intact.

For further articles in this series: TypeClass101

Comments