Tuesday, 25 April 2017

Monads as Applicatives

Applicative functor (or just "applicative" in short) is a more general abstraction than a monad; in other words, monad is an applicative with some extra functionality. However, despite being conceptually present, applicative's functions are rarely explicitly exposed in a monad. Let's try to do that manually.

Applicative can be expressed as: 
  • unit + apply 
  • unit + map2 
  • unit + map + product   
with apply and product being the popular ones (in scalaz library they are known as <*> and |@|). By using an applicative functor instead of the non-applicative one, we can map by using multi-parameter curried functions (either by applying curried parameters one by one with apply or by lifting everything into a product and mapping on that).

So now we want to see how can both apply and product be implemented by using monad's operations map and flatten (we won't be needing unit; also, note that other than unit + map + flatten, monad can also be expressed as unit + flatMap and unit + compose).

Let's say we have the following definition of a monad in Scala (as announced, unit was omitted for brevity):
trait Monad[F[_]] {
  def map[AB](fa: F[A], f: => B): F[B] = ???
  def flatten[A](fa: F[F[A]]): F[A] = ???
Applicative's methods can then be implemented as:
trait Monad2[F[_]] extends Monad[F] {

  def apply[A, B](fa: F[A], fab: F[A => B]): F[B] = 
    flatten(map(fab, (f: A => B) => map(fa, f)))

  def product[A, B](fa: F[A], fb: F[B]): F[(A, B)] = 
    flatten(map(fa, (a: A) => map(fb, (b: B) => (a,b)))) 
Here's an example of using apply with a curried function. I will provide a concrete implementation of apply for List just for simplicity.
def apply[A, B](list: List[A], f: List[A => B]): List[B] = f.flatMap(f => list.map(f))  

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

val list1 = List(1)  
val list2 = List(2)  
val list3 = List(3)   

val result1 = apply(list1, List(curriedF))  
val result2 = apply(list2, result1)  
val result3 = apply(list3, result2)   

result3 // List(6)
The usage is the same as in applicative case. However, there's a significant difference - if apply is implemented using a flatMap, we are taking advantage of monad's power to chain things into series. Standard apply and product from applicative lack this ability.

Let's show this difference in practice. Since we were working with apply in the previous example, let's take product now. We can provide two different implementations: one using monadic functions and another one in standard applicative fashion (we can use standard Scala's zip):

// we'll need these throughout the example 
import scala.concurrent.{Await, Future}  
import scala.concurrent.duration._  
import scala.concurrent.ExecutionContext.Implicits.global  

// monad version  
def product1[A, B](f1: => Future[A], f2: => Future[B]): Future[(A, B)] = f1.flatMap(a => f2.map(b => (a, b)))    

// applicative version  
def product2[A, B](f1: => Future[A], f2: => Future[B]): Future[(A, B)] = f1 zip f2
Note that both are taking their parameters by-name instead of by-value in order to prevent futures from executing as soon as they are passed.

Let's now create the futures:
def first = Future { println("first"); Thread.sleep(2000); 1 } 
def second = Future { println("second"); Thread.sleep(2000); 2 }
Using serial product, we get:
// prints "first", then two seconds later "second" 
val result1 = product1(first, second).map { case (a, b) => a + b } 
Await.result(result1, 10 seconds)
Using parallel product, we get:
// performs in parallel; order of printing is indeterministic 
val result2 = product2(first, second).map { case (a, b) => a + b } 
Await.result(result2, 10 seconds)
Finally, the scalaz version:
import scalaz._, Scalaz._ 

// "first" and "second" are printed simultaneously 
val result3 = (first |@| second) { case (a, b) => a + b } 
Await.result(result3, 10 seconds)
While monad as a generic data structure could have methods such as apply or product exposed in its API, it probably doesn't make a lot of sense. Still, if one needs them, we have seen here that they can be easily implemented in terms of existing monad functions. Note that even if their signatures are the same as applicative's, we have also seen that monad's power - ability to chain computations in series - is still present and at disposal, if desired. In this particular example we could force the product implemented with flatMap to behave the same as the parallel one by simply going from by-name to by-value invocation (by removing the => from each parameter type). This way each future is evaluated as soon as it is passed to product.

As tempting as it may feel to implement a single "swiss army" abstraction and equip it with unit, map, map2, flatMap, apply, product, compose etc. it's important to remember that best practice is to always use the least powerful abstraction that does the job. If you need apply or product (meaning you have more than one operation, which is a stronger requirement than what a non-applicative functor can give you, but they don't depend on each other, which is a weaker requirement than what a monad would give you) your abstraction of choice should be the applicative functor.

Monads as Applicatives

Applicative functor (or just "applicative" in short) is a more general abstraction than a monad; in other words, monad is an app...