In my previous blog post about categories and functors I already threatened you with the possibility of a follow-up. Well, here we go. Actually I won’t talk about category theory this time, but about an important abstraction from the world of advanced (at least in my understanding) functional programming which turns out to be a close relative to the now well understood functor.

## Functors

Just in case you don’t remember exactly what a functor looks like, here comes the definition:

trait GenericFunctor[->>[_, _], ->>>[_, _], F[_]] { def fmap[A, B](f: A ->> B): F[A] ->>> F[B] } trait Functor[F[_]] extends GenericFunctor[Function, Function, F] { final def fmap[A, B](as: F[A])(f: A => B): F[B] = fmap(f)(as) }

For the sake of simplicity we will stick to the more specific *Functor* definition throughout the rest of this post. Such a functor is an endofunctor, because its source and target are the same (the category of Scala types and Scala functions). Maybe you remember that such a functor can be regarded as a provider of a computational context: The function *f: A => B* you give to *fmap* is lifted into the functor’s context which means that it is executed (maybe once, maybe several times or maybe even not at all) under the control of the functor.

As an example let’s look at how the *OptionFunctor* defined in the previous blog post is working: If we give *fmap* a *Some* the given function will be invoked, if we give it a *None* it won’t be invoked.

scala> fmap(Option(1)) { x => println("I was invoked!"); x + 1 } I was invoked! res0: Option[Int] = Some(2) scala> fmap(None: Option[Int]) { x => println("I was invoked!"); x + 1 } res1: Option[Int] = None

So far, so good. Using functors we can lift functions of **arity-1** into a computational context.

## Applicatives

But what if we have a function of higher arity? Can we still use a functor to lift a function of, let’s say, **arity-2**?

Let’s look at what happens if we call *fmap* to partially apply an arity-2 function to its first argument within the computational context of an *Option*:

scala> val f = (x: Int) => (y: Int) => x + y + 10 f: (Int) => (Int) => Int = <function1> scala> fmap(Option(1))(f) res0: Option[(Int) => Int] = Some()

What we get back is an *Option[Int => Int]*, i.e. the “rest” of the partially applied function wrapped in an *Option*. Now we have a problem, because we cannot give this lifted function to another call of *fmap*.

scala> fmap(Option(2))(fmap(Option(1))(f)) :13: error: type mismatch; found : Option[(Int) => Int] required: (Int) => ? fmap(Option(2))(fmap(Option(1))(f))

Of course we cannot, because *fmap* expects a pure function, not a lifted one. And that’s the moment when applicatives enter the stage. The idea is simple and follows intutively from what we have just seen: Instead of *fmap* taking a pure function, an *Applicative* defines the method *apply* taking a lifted function. And it defines the method *pure* to lift pure functions. Using these it is perfectly possible to partially apply an arity-n function to all of its arguments within a computational context. Before we look at our example from this new perspective, let’s code up our new abstraction:

trait Applicative[F[_]] extends Functor[F] { def pure[A](a: A): F[A] def apply[A, B](f: F[A => B]): F[A] => F[B] final def apply[A, B](fa: F[A])(f: F[A => B]): F[B] = apply(f)(fa) override def fmap[A, B](f: A => B): F[A] => F[B] = apply(pure(f)) }

As you can see, there is a strong relation between functors and applicatives: Each applicative is a functor and by one of the laws for applicatives the following has to hold true: *fmap = apply ο pure*. Well, this law is pretty intuitive, because it makes sure we can use an applicative as a functor, i.e. for a pure arity-1 function, and it will behave as expected.

In order to be able to work with applicatives we need some scaffolding and for our *Option* example we need an implementation of *Applicative*:

object Applicative { def pure[A, F[_]](a: A)(implicit applicative: Applicative[F]): F[A] = applicative pure a def apply[A, B, F[_]](fa: F[A])(f: F[A => B])(implicit applicative: Applicative[F]): F[B] = applicative.apply(fa)(f) implicit object OptionApplicative extends Applicative[Option] { override def pure[A](a: A): Option[A] = Option(a) override def apply[A, B](f: Option[A => B]): Option[A] => Option[B] = o => for { a <- o; p <- f } yield p(a) } }

Now let’s look at our example from above with an arity-2 function. Using a functor we got stuck, but using an applicative we can make it all the way through the two arguments:

scala> apply(Option(1))(apply(Option(2))(pure(f))) res0: Option[Int] = Some(13)

Ain’t that nice? You might answer, that this code looks cumbersome and is not necessary at all. Regarding the first argument please read on. Regarding the second: Yes, of course we don’t need an applicative for *Option*, because it already offers *flatMap* which does the job. But with this type class approach we can deal with any class, e.g. with *Either* from the Scala standard library or with classes from our own projects.

## Conclusion

You have seen the basic principle of applicatives: We can apply functions of arbitrary arity (well, greater or even one) to its arguments within a computational context. As functors provide exactly this for arity-1, applicatives are generalized functors.

Thanks to Scala’s flexibility we can of course do much better than above. Using a little pimp my library and some operators we can get something that’s elegant and useful. Luckily the scalaz folks have already done this, so I will just show two ways of expressing the above example using this awesome library:

scala> Option(1) <*> (Option(2) <*> Option(f)) res0: Option[Int] = Some(13) scala> (Option(1) <**> Option(2)) { _ + _ + 10 } res1: Option[Int] = Some(13)

Now this is really nice, isn’t it? Especially the second one looks very concise and intuitive. And as I stated above we can use it for types that don’t bring helpful methods like *flatMap*. Let’s conclude with another example using *Either* which is a perfect candidate to be used for results that might fail with well defined errors:

scala> (1.right[String] <**> 2.right[String]) { _ + _ + 10 } res0: Either[String,Int] = Right(13) scala> (1.right[String] <**> "Error".left[Int]) { _ + _ + 10 } res1: Either[String,Int] = Left(Error)

If you are interested in the code examples shown above, you can find these here: https://github.com/weiglewilczek/fun

[…] Applicatives are generalized functors […]

[…] talk about category theory this time, but about an important abstraction from the world …… [full post] Heiko Seeberger Heiko's Blog functional programmingscala 0 0 0 […]

Very educative post, Heiko! Thanks for sharing :)

Thank you, Vasil. My intention is indeed to educate … myself ;-)

Yes blog posts serve in some case an educational purpose, and when dealing with new topics it is a nice practice to get used to them. Hopefully you won’t spare the really interesting ones either :D

Some impatient people don’t see the immediate advantage of functional programming in their day to day coding (that is kind of sad).

I found this to give me some good points to ponder about:

http://aabs.wordpress.com/2008/05/29/functional-programming-lessons-from-high-school-arithmetic/

So will your upcoming book already include “functional” boosted API’s or Code?

regards Andreas

Andreas,

Thanks for the pointer. Looks interesting.

I don’t think I will touch “advanced” FP stuff in my book. It’s intended as a starter for (Java) programmers. From my experience in teaching Scala I know that >90% of the (Java) developers find FP very tough in the beginning.

Cheers,

Heiko

Heiko,

from my own experience, I think your book is also useful and joyful for developers who don’t find FP tough. (Not that you stated this, just wanted to point it out).

Btw, I got here by searching for applicatives after reading the example about scalaz’s validation in your book.

David

Thanks!

Heiko,

> 90% what an pessimistic estimate :D

Well I try to be somehow pragmatic. I see functional programming as a tool (a powerful one) which I can use to solve problems which would be otherwise at least harder to implement. Functional programming also favours immutability, which comes handy in some scenarios. If I have a nested immutable data structure and I have to update some values I can try by myself or use a zipper:

http://stackoverflow.com/questions/3900307/cleaner-way-to-update-nested-structures

So for me functional programming just offers me a much broader toolbox for solving problems, and extending your toolbox can be only fun (IMHO) ;)

looking forward to your follow ups

regards Andreas

“What we get back is an Option[Int => Int]”

I think you mean Option[(Int) => Int]

That’s the same, ain’t it?

[…] Applicatives are generalized functors | Heiko's Blog @dnene a very good introduction to applicative functors is this blog post http://bit.ly/g5PEaA by @hseeberger /cc @debasishg – Martin Krasser (mrt1nz) http://twitter.com/mrt1nz/status/60331010386173953 (tags: via:packrati.us from:mrt1nz) […]

[…] To understand the mechanics of how applicative functors solve our problem, please refer to the references below, in particular Heiko Seeberger’s Applicatives are generalized functors. […]

[…] This is a signature for map that you will also find in articles, either as a primary way to implement it, or as a helper function, delegating to the other signature (like here). […]

[…] Seeberger blog post « Burndown, Prediction, Confidence and Risk A Small Example of the Scalaz IO Monad […]