Applicative Programming 5

prev next

From Monad to Applicative Functor

What Do We Actually Need

Last time we stopped bewildered by non-commuting monads and by the question what can we do then.

To start, let us look at one more monadic operation example.

    def process(user: User, phone: Phone) = { 
      val s = user.name + ": " + phone.number; println(s); 
      s
    }

    for (user <- db.getUser(userId); // actually it's one user at most
        phone <- db.getPhones(userId) // can have more than one phone, bummer if we use Java
    ) process(user, phone)

In SQL this would look like this:

    select user.name, phone.number from user, phone where user.id = userId and phone.userId = userId

What's interesting, in SQL we can actually execute two database requests in parallel - but not in Scala. In Scala we do it sequentially. There's something wrong here; so this is the good starting point to do our applicative deconstruction.

No, first let us apply one more trick. We have a two-parameter function process here. We will curry it, turn it into a function of one variable that returns another function of one variable, like this:

    def process (user: User) (phone:Phone) = { 
        val s = user.name + ": " + phone.number; 
        println(s); 
        s
    }

Now if we call process(user), the result will have a type Phone => String`. Why would we need it? Well, we could transform our loop to this form:

    for (user  <- db.getUser(userId);
         f     =  process(user);
         phone <- db.getPhones(userId);
    ) f(phone)

Which can be rephrased like this:

    val fs     = db.getUser(userId).map(process)
    val phones = db.getPhones(userId)
    for (f <- fs; phone <- phones) f(phone)

Note the types of our values:

    val fs:     Set[Phone => String] = db.getUser(userId).map(process)
    val phones: Set[Phone]           = db.getPhones(userId)

In the loop for (f <- fs; phone <-phones) f(phone) we apply a set of functions to a set of phones (one by one), producing a set of strings. In math this kind of operation is frequently called folding. I will call it ap throughout this text.

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

    val fs     = db.getUser(userId).map(process)
    val phones = db.getPhones(userId)
    val result = fs ap phones

We assume that type Set has a method ap which comes from trait Applicative which we will introduce later.

We have defined above val fs = db.getUser(userId).map(process), but we could as well define it using the same ap operation:

    val processes = Set(process)
    processes ap db.getUser(userId))

Again, assuming that Set somehow has this ap method, we just call it for the singleton set that we have build from our process method.

Of course this ap that we have so easily defined above for Set, has to be defined for each specific functor. Thanks to Scala's pimping technique, we can implicitly add it whenever we find convenient.

Introducing Applicative Functor

Below is the code that compiles and works, but is not exactly industrial grade.

Start with a trait that specifies functoriality:

    trait Functor[T[_]] {
      def map[A,B](f:A=>B)(ta:T[A]):T[B]
    }

Now define applicativity:

    trait Applicative[T[_]] extends Functor[T] {
      def pure[A](a:A):T[A]
      def ap[A,B](tf:T[A=>B])(ta:T[A]):T[B]
    }

Now turn Set into Applicative:

    implicit object AppSet extends Applicative[Set] {
      def pure[A](a: A) = Set(a)
      def ap[A,B](fs:Set[A=>B])(as:Set[A]):Set[B] = (for (f <- fs; a <- as) yield f(a)).toSet
      def map[A,B](f:A=>B)(as:Set[A]) = ap(pure(f))(as)
    }

Throw in a fold operation for sets (a set of functions and a set of values).

    implicit def applicable[A, B](fs: Set[A=>B]) = new {
      def <*>(as: Set[A]) = ap(fs, as)
    }

Here is an example how it can work:

    val p2 = AppSet.pure((first: String) => (second:String) => first + " " + second)
    val firsts = Set("Jedi", "Michael Valentine")
    val lasts = Set("Smith", "Frazer")
    p2 <*> names <*> lasts

Now we can use pure and <*> for our operations:

    processes = AppSet.pure(process)
    processes <*> db.getUser(userId)

And the whole business logic looks like this:

    val result: Set[String] = AppSet.pure(process) <*> db.getUser(userId) <*> db.getPhones(userId)

What happens here? We take a function called process, build a singleton set (that is, apply monadic unit), then fold it with users and phones. As a result we get the set of strings we were looking for.

So far we dealt with a monad, but used only parts of its features. We used its unit, now called pure, and folding operation, which we have built based on monadic multiplication and the monad's functoriality (the presence of map).

Folding is associative. Associative operations have a very interesting feature. They can be a) parallelized, and b) optimized at O(ln(n)). Imagine we have a composition of a hundred of such folds - we can draw a binary tree and fold the leaves in parallel - like in map/reduce. Well, this is map/reduce.

prev next