Functors and Applicatives

In one of my earlier articles I tried to explain monads in an approachable way. Here’s an attempt to do the same for some other members of the same family — functors and applicative functors. Even though concepts and principles explained here are general in functional programming, mild accent will be (as usual) on Scala.

Functors

In case you read the aforementioned article about monads, you may remember how I described them as wrappers around values. Every value wrapped in a monad becomes an object equipped with two methods, unit and flatMap (using Scala convention for naming).

So, if you look at a monad as a wrapper (I also like the word “context”) which provides those two methods, then you can look at a functor simply as another kind of wrapper; one that provides a slightly weaker version of a monad.

All you get is:

• map (fmap in Haskel; like monad’s flatMap, but without the flatten part)

Function map probably at least sounds familiar, although I’m quite sure most of you have used it in practice. Beginners are usually introduced to it using the list/array/someOtherCollection example, but the thing is that all functors have this function. You can map every element inside a List or a Set, but you can also map the value inside a Future or an Option into another value (of same or different type).

Moving on, but first we have to sort something out. Didn’t I declare Future, Option, List etc. to be monads in the monad article? Yes, I did. Everything that’s a monad is also a functor; you can look at it from the OOP perspective as monad being a subclass (or a subtype) of functor. OK, don’t really go around saying this to everyone because if you stumble upon category theory mathematicians, they could start talking about functors being simply mappings of elements and morphisms between categories while monads are actually monoids in the category of endofunctors with natural transformations being defined as functor composition and identity functor. I’m not kidding; they actually talk like that. But yes, from a programmer’s point of view it is completely valid to say that monad is in fact a functor, with extra stuff on the side. More specifically, on top of functor’s map monad has a flatten (also known as join), which enables it to define an upgraded version of map — our beloved flatMap (also known as bind). Remember that monad also has a less interesting, but not less important, unit method.

Remember monad laws? We have some laws here too. Given that m is our functor instance (e.g. List or Future) holding some value (e.g. Int) and functions f and g are single-parameter functions that transform that value (in our example they must have signature Int → Something), then we can define the two functor laws as follows:

• identity law: _map id = id_or Scala-way: m.map(identity) == m

• distributive law: F map f map g = F map (g ◦ f)or Scala-way: m.map(f).map(g) == m.map(x => g(f(x))

Here identity is the identity function defined in predef package in Scala (given a value, it simply returns that same value) and ◦ is the standard mathematical notation for function composition (meaning “g after f”, or “apply f and then g”). Note that you can use compose or andThen if you want to compose two functions in Scala; however, that’s not the point of this article so I went for the easiest form and simply apply them one after another: g(f(x)).

Heavy lifting

Instead of map() taking two parameters, we will now curry it. This means that function e.g. (Int, Int) → Int will now become Int → Int → Int. Remember that this is right-associative, so it’s the same as Int → (Int → Int). If you’re not familiar with currying, we’ll get back to it shortly.

Let’s take a List as a functor; our starting point (that is, our starting functor instance) can be, for example, List(1, 2, 3). Let’s also take some function that we can map our List with, such as:

val f = (x: Int) => x.toString

In Scala we would map this list as simple as List(1, 2, 3).map(f). Now, if we shift our viewpoint as we did before so that map becomes a binary function, we could invoke it as map(List(1, 2, 3), f). First argument is the functor instance and second argument is the function. (Note that I’m making up syntax here; I’m merely illustrating a concept. In all standard Scala constructs map() will always be a class method that is invoked upon an instance of that class and it will take only one argument — the mapping function. It’s the convention.)

We said we would take it one step further and curry it, so invocation of our map function now becomes this (note that I switched the places of parameters because it’s easier to illustrate my point this way; function doesn’t need to change its implementation if the order of its arguments in signature is shuffled):

map(f)(List(1, 2, 3))

Currying is taking a function of n parameters and turning it into n single-parameter functions. Any n-parameter function can be curried like this; actually, in Haskell this is the only way of achieving a function with more than one parameter. So for example. instead of having a function that takes two numbers and multiplies them, you can only have a function that takes a number and returns a function that takes a number and returns a number. This way, as we said before, (Int, Int) → Int becomes Int → Int → Int. Or if you prefer to write the precedence explicitly, it becomes Int → (Int → Int).

So our map is now actually a one-parameter function that returns a yet another one-parameter function. This allows us to pass just the first argument like this:

map(f) // returns a function List[Int] => List[String]

If we continued on and passed our List(1, 2, 3) to the result of map(f), we would get back a List(“1”, “2”, “3”). But if we stop here, what we get back is a function that takes a list of integers and returns a list of strings. Curried approach gives us a higher-order function that maps typeA → typeB to Functor[typeA] → Functor[typeB]. This kind of higher-order function is commonly known as lift. It takes a function and “lifts it” so that its operands are put into some context (such as a functor or a monad).

This means that we can write the signature for map() like this:

(A → B) → F[A] → F[B]

This is the classic map signature found in many functional programming books and programming languages. Since it’s a chain of two curried functions, we can view it in two ways:

• map takes a function A → B and a functor instance F[A] and it produces another functor instance, F[B] (our classical, non-curried map)
• map takes a function A → B and returns a function F[A] → F[B]

It’s the awesome nature of currying that allows us these two different viewpoints.

Problem with functors

We saw three different representations of the map function:

• the Scala way: m.map(f)
• as a 2-param function: map(m, f)
• as a curried function: map(m)(f) or map(f)(m)

Even though second and third way are more common in functional programming world, Scala, being not only FP but also OOP language, decided to go with the first choice since it’s closer to the object-oriented paradigm.

Now, we know that map() takes a function of only one parameter — one that is of the same type as the underlying value inside a functor. For example, map on list of integers takes a function that takes a single Int (but it can return any type).

However, we also know that using currying we can cheat a little. If we have a function of n parameters, we can curry it and transform it into a function of only one parameter that returns a function of n-1 parameters. This would allow us to feed map() with a function of any number of parameters (of course, first one would have to be of the appropriate type to match the one wrapped within functor, e.g. Future[Int] could be mapped with a function Int → Whatever → Whatever → Whatever → …).

Nice idea, but map() doesn’t like it too much.

Why? A simple example will illustrate the problem. Let’s take a function that adds two integers and curry it:

val f = (x: Int) => (y: Int) => x + y

If we feed this function with a value, we will get back a function of one less parameter than the original, which leaves us with only one parameter (in our case called “y”). So if we feed function f with value 42, we will get back a function that takes a number and adds 42 to it.

Cool. So let’s feed our curried function to map():

val f = (x: Int) => (y: Int) => x + y

val result = Future(42).map(f)

// result is Future(x => x + 42)

What we get back is a Future in which our integer number 42 is transformed into a function that takes some integer x and returns x+42_._ Now this is a bit of a problem. As we said earlier, normally when you curry a function of n parameters and you supply it with the first parameter, you get back a function of n-1 parameters. In case of our function f that adds two numbers, we would get back a function Int → Int. But when we supply that function to map(), what we get back is not Int → Int, but Future[Int → Int]. We cannot continue applying stuff to the rest of our curried function any more, because map() doesn’t know how to work with a function wrapped inside a future.

Let me repeat this once more, it’s the key part. So, if we wanted to map our Future with some function of, let’s say, four parameters this time, such as f(a: Int, b: Int, c: Int, d: Int), we would curry the function into Int→ Int→ Int→ Int and supply it to map(), but that would be the end of it. Map would consume the first parameter, but would not leave us with Int→ Int→ Int. If it did, we could carry on in the same fashion. What it would leave us with is Future[Int → Int → Int] instead.

What we need now is an applicative functor.

Applicative functors

Applicative functor (sometimes called simply applicative) is an upgraded version of the common functor we saw earlier. While functors use only single-parameter functions, applicative functors can use functions of any number of arguments. They also introduce the unit/return method which lifts a given type A into F[A]. (Note: Applicative functors also come with a bit different set of laws than ordinary functors; I will not go into them here as my intention is simply to explain the idea of applicative functors while leaving “mechanical” parts such as laws to your personal research, once you’re comfortable with the concept)

Let’s consider again some four-parameter function f in curried form. Its signature is Int → Int → Int → Int. Now let’s feed it to map() of some Future[Int]. Result is Future[Int → Int → Int]. We’ve been through this a minute ago. OK, but now something cool happens: our new friend applicative functor comes into play and says: “Hey, so you got your function wrapped into a bit of a context, huh? Not to worry, I know how to apply those kind of wrapped functions. Yes, you heard me well; I can apply functions within a functor context (such as Future, Option or List)”. To avoid confusion, we’ll leave the term “map” to standard functors and use the term “apply” for this new cool function in applicative functors. So, if map is defined as (using curried notation):

• map[A, B](f: F[A])(f: A → B): F[B]

then our new method apply() is defined as:

• apply[A, B](f: F[A])(f: F[A → B]): F[B]

There are two more ways to define an applicative functor: replacing apply with the equally powerful map2, or replacing it with a combination of product and map.

Here are all three definitions:

1. unit[A](a: A): F[A]apply[A, B](f: F[A])(f: F[A → B]): F[B]

2. unit[A](a: A): F[A]map2[A, B, C](fa: F[A], fb: F[B])(f: (A, B) => C): F[C]

3. unit[A](a: A): F[A]map[A](fa: F[A]])(f: A => B): F[B]product[A, B](fa: F[A], fb: F[B]): F[(A, B)]

When I said that methods apply and map2 are “equally powerful”, what I meant is that you can express one by using the other. Product is a bit weaker and needs to be accompanied by map. I will not show the translations between these definitions here, but you can find them online (e.g. here) or try to work them out yourself.

We will be using the apply version for now, but then I will show you how it is related to the other two definitions.

Solving the functor problem

Alright. So what happens if we feed the Future’s map() with function Int → Int → Int → Int? We get back a Future[Int → Int → Int]. Then we can feed its apply() with Future[Int → Int → Int] and get back a F_uture[Int → Int]._ Finally, we apply the Future[Int → Int] and are left with Future[Int].

Let’s finish our “add by 42” example from earlier. Note that I’m going to write some more pseudo-Scala because there is no method apply() in Future defined in this way. For now, just imagine that such method exists and we’ll explain this predicament later.

So, in order to feed a two-parameter function to the functor, we would do:

val f = (x: Int) => (y: Int) => x + yval r1: Future[Int => Int] = Future(42).map(f)Future(10).apply(r1) // results in Future(52)

Do you see what happened here? We took two values of type Future[Int] (Future(42) and Future(10)) and a function f with signature Int → Int and we managed to produce a yet another Future whose underlying value is the result of applying values of our two starting futures to the function f. This is really great. Let’s say you fetch three points of a triangle from a database and wind up with three Future[Int] values. How to calculate the perimeter of the triangle made by those points using function calculate(a: Int, b: Int, c: Int)? You can’t just feed the points to the function because points are not of type Int, but of type Future[Int].

Using an applicative functor it becomes possible:

val f1 = Future(3)val f2 = Future(4)val f3 = Future(5)

val calculate = (a: Int) => (b: Int) => (c: Int) => a + b + c

// btw you can also do:// val calculate = ( (a:Int, b:Int, c:Int) => a + b + c ).curried

f1.apply(f2.apply(f3.apply(unit(calculate)))) // Future(12)

Cool, right? Note that we had to wrap the function into the applicative context by using unit in order for apply to be able to consume it.

Enough of that pseudo-Scala stuff. Let’s write some actual code. We will use the scalaz library:

import scalaz._, Scalaz._

val f1 = Future(3)val f2 = Future(4)val f3 = Future(5)

val calculate = (a: Int) => (b: Int) => (c: Int) => a + b + cval area = f1 <*> (f2 <*> (f3 <*> Future(calculate))) // Future(12)

Operator <*> is the apply operation. For unit, I simply used the Future constructor.

Remember how we talked about the three different definitions for applicatives? Let’s see how things work with product + map:

import scalaz._, Scalaz._

val f1 = Future(3)val f2 = Future(4)val f3 = Future(5)

val calculate = (a: Int) => (b: Int) => (c: Int) => a + b + cval area = (f1 |@| f2 |@| f3)(calculate)// Future(12)

Operator |@| is the product operation. What we did here is that we put together the three applicatives and “merged” them into one (we computed their product) and then we mapped that product with our calculate function. Note that we didn’t explicitly invoke map() because this is how scalaz syntax for applicative product works; combining your applicatives into a product by using |@| results in an ApplicativeBuilder which takes a function to perform on the product (since product + map is a very common use case). Pay attention to one detail: calculate can’t be curried here, since the applicative product takes an uncurried, multi-parameter function (in this case arity 3). I

If it’s easier for you to reason about the whole process by using the product definition instead of by using the apply definition, that’s actually pretty normal. I have shown you both ways, you’re free to pick up whichever you prefer. Anything you can do with unit + apply, you can do with unit + product + map and vice versa. Same goes for the third definition, unit + map2 (I will let you investigate that one on your own; it’s been removed from scalaz7 anyway, so if you decide to skip it that’s fine).

By the way, astute reader will notice that the product version is actually doable in regular Scala. Yup, that’s a zip right there.

val area = (f1 zip f2 zip f3) map {case ((a, b), c) => calculate(a, b, c)} // Future(12)

A bit clumsy, but doable.

Conclusion

“Regular” functors are basically wrappers for values of some type. List[Int], Future[String] and Option[Whatever] are examples of functors.

Applicative functors are a bit more sophisticated — they know how to apply a function wrapped in functor context. For example, given a Future[Int] functor, we can apply a function Future[Int → Int] to it, while regular map() in regular functors only knows how to apply Int → Int. Or, you can look at it this way: on top of regular functor’s map functionality, applicative functor adds the unit function, which lifts an ordinary A into functor context F[A], and product function, which can be used to combine multiple functors into one.

So, there are multiple ways of describing an applicative functor that lead to the same basic principle. Applicative functor is like a functor, but:

• applicative functor can apply functions of more than one parameter
• applicative functor can apply functions wrapped inside a functor context
• applicative functor can combine multiple functors into one product
• etc.

And now one more interesting point before we finish:

You may or may not already know something about monads. Well, monads go one step further and provide you with an even more powerful operation. Here they are in comparison, all three of them (I’m omitting unit because it’s not needed for making this point):

• functor:_map(f: F[A])(f: A → B): F[B]_

• applicative functor:_apply(f: F[A])(f: F[A → B]): F[B]_

• monad:flatMap(f: F[A])(f: A → F[B]): F[B]

Just like applicatives can use other definitions (e.g. product + map instead of apply), same goes for monads (e.g. flatten + map instead of flatMap). Monads are the most powerful; they can be “conditioned”, which means that one monad can take action depending on the result of the previous monadic operation. Or, if you prefer — they can work in series, whereas applicatives work in parallel. See that f: A → F[B] in monad definition? That’s the part that enables this dependency; it says “take A from monad F[A] and compute monad F[B] based on it”.

So if you have e.g. n asynchronous requests (e.g. database queries) that result in n Futures, you should pick a proper abstraction based on your needs:

• if your Futures don’t depend on each other, use an applicative (you can e.g. put them all into one product and map each result with a function that handles success/failure)
• if your Futures do depend on each other, e.g. you want to call them in series and stop on first success or first failure, then use a monad (it allows you to flatMap a future with a function that examines its value and performs the next monadic operation based on it)

This is why you can only build a parser for context-sensitive grammars by using monads, while for context-free grammars it’s enough to use applicatives.

OK, that’s all for now. As usual, in case you feel something is unclear, confusing, misleading or incorrect, drop me a comment here or throw me an email on sinisalouc@gmail.com. Also feel free to find me on Twitter.

Cheers!

Hacker Noon is how hackers start their afternoons. We’re a part of the @AMIfamily. We are now accepting submissions and happy to discuss advertising &sponsorship opportunities.

To learn more, read our about page, like/message us on Facebook, or simply, tweet/DM @HackerNoon.

If you enjoyed this story, we recommend reading our latest tech stories and trending tech stories. Until next time, don’t take the realities of the world for granted!