Applicative

With functor, we now have a convenient way to apply functions to the contents of an effect, regardless of the type of the effect itself. We were able to check the fish and cook it by applying the same logic we had for an effect-free fish. To get even more comfortable with functors, we will now make a fish pie with our new tool.

First, we'll define a function to make a pie from a single fish:

final case class FishPie(weight: Int)
import ch08.Model._
def bakePie(fish: FreshFish, potatoes: Int, milk: Float): FishPie = FishPie(fish.fish.weight)

That was easy—one fish, one pie, with the size of the fish. Now, we are ready to bake every fish in the bucket:

mapFunc(listOfFishGen.sample.get)(bakePie)

Oops! This won't compile because the functor only accepts the function of one argument, and we have three.

What can we do? One of the possibilities would be to refactor and partially apply our function. We could also create a function that uses mapC to convert the bucket of fish in to a fresh fish bucket so that we can simplify further actions:

val freshFishMaker: List[Fish] => List[FreshFish] = ch08.Functor.bucketFunctor.mapC(check)

And then we can implement the rest of the logic with the partially applied function:

def bucketOfFish: Bucket[Fish] = listOfFishGen.sample.get

def bakeFishAtOnce(potatoes: Int, milk: Float): FreshFish => FishPie = 
  bakePie(_: FreshFish, potatoes, milk)

val pie: Seq[FishPie] = mapFunc(freshFishMaker(bucketOfFish))(bakeFishAtOnce(20, 0.5f))

This is a valid approach and would work, but this will use the same amount of ingredients for each and every fish. Some of the pies won't taste very good if this strategy. Can we do better?

Well, we can make our original function curried. This will give us a function that accepts a single fish and then other arguments on top:

def bakeFish: FreshFish => Int => Float => FishPie = (bakePie _).curried
val pieInProgress: List[Int => Float => FishPie] = 
  mapFunc(freshFishMaker(bucketOfFish))(bakeFish)

Now, we would like to use the ingredients from another bucket so that we can add to the pieInProgress. Unfortunately, this is something that a functor can't help us with. If we try and nest, the map calls for a bucket of potatoes and a bucket of milk, so we would come up with something like the following:

mapFunc(pieInProgress) { (pieFactory: Int => Float => FishPie) =>
  mapFunc(bucketOfPotatoes) { potato =>
    mapFunc(bucketOfMilk) { milk =>
      pieFactory(potato)(milk)
    }
  }
}

Unfortunately, each nested call will leave the result in the nested bucked so that even if this were able to compile at the end, we'd have three nested buckets. Our functors do not know how to extract nested buckets from each other.

What can help us is the Applicative Functor. Sometimes just known as Applicative, this structure extends the original functor with two more methods:

trait Applicative[F[_]] extends Functor[F] {
  def apply[A,B](a: F[A])(f: F[A => B]): F[B]
  def unit[A](a: => A): F[A]
}

The apply method takes an effect, a, and a function, f, defined in the context of the same effect and applies f to a, thus returning the result that's wrapped in the very same effect.

The unit method allows us to wrap a plain value, a, into the effect. This is often called lifting, especially if a is a function, as it "lifts" the original value (or function) into the context of the effect, F.

An astute reader will expect some laws to pop up for the aforementioned functions. And you would be absolutely right! There are a few of them:

Identity law states that an application of an identity function should return the argument unchanged, the same way the identity function does. This is similar to the identity law for the functor, but this time defined for the apply function.
Homomorphism law states that applying a function to a value and then lifting the result is the same as first lifting this function and value and then applying them in the context of the applicative.
Interchange law states that changing the order of the parameters for the apply method should not change the result.
Composition law states that function composition should be preserved.

Now, this might start to sound abstract. Let's make these points clear by capturing them as properties.

The identity property is the simplest one. The only caveat is that we can't use the identity function—we have to be explicit about the type of the argument for the unit method because there is no possibility for the compiler to infer it for us:

def identityProp[A, F[_]](implicit A: Applicative[F],
                          arbFA: Arbitrary[F[A]]): Prop =
  forAll { as: F[A] =>
    A(as)(A.unit((a: A) => a)) == as
  }

Homomorphism is also not very spectacular—it literally encodes the rules we stated in prose. Similar to the case of identityProp, we're taking advantage of the apply syntax:

def homomorphism[A, B, F[_]](implicit A: Applicative[F],
                             arbA: Arbitrary[A],
                             arbB: Arbitrary[B],
                             cogenA: Cogen[A]): Prop = {
  forAll((f: A => B, a: A) => {
    A(A.unit(a))(A.unit(f)) == A.unit(f(a))
  })
}

The interchange law is where it starts to become interesting. We'll define left and right sides separately to simplify the definition:

def interchange[A, B, F[_]](implicit A: Applicative[F],
                            arbFA: Arbitrary[F[A]],
                            arbA: Arbitrary[A],
                            arbB: Arbitrary[B],
                            cogenA: Cogen[A]): Prop = {
  forAll((f: A => B, a: A) => {
    val leftSide = A(A.unit(a))(A.unit(f))
    val func = (ff: A => B) => ff(a)
    val rightSide = A(A.unit(f))(A.unit(func))
    leftSide == rightSide
  })
}

The left side is identical to the homomorphism definition—we're lifting some random function and a value into the applicative. Now, we need to change the order of f and a. The f is a first-class value, so we're fine on this side, but a is not a function. Therefore, we're defining a helper func which takes something with the same type as f and returns type B. Given a, we have only one way to implement this. With this helper, the types will align. Finally, we are defining the rightSide with the changed order of arguments and finish with the property comparing them.

The composition property is the most lengthy one because we have to define the functions that we are about to compose. First, let's define function composition as a function:

def composeF[A, B, C]: (B => C) => (A => B) => (A => C) = _.compose

Given two functions with matching types, composeF will return a function composition by delegating to the compose method of the first argument.

We'll again define left and right sides of the property separately:

def composition[A, B, C, F[_]](implicit A: Applicative[F],
                               arbFA: Arbitrary[F[A]],
                               arbB: Arbitrary[B],
                               arbC: Arbitrary[C],
                               cogenA: Cogen[A],
                               cogenB: Cogen[B]): Prop = {
  forAll((as: F[A], f: A => B, g: B => C) => {
    val af: F[A => B] = A.unit(f)
    val ag: F[B => C] = A.unit(g)
    val ac: F[(B => C) => (A => B) => (A => C)] = A.unit(composeF)
    val leftSide = A(as)(A(af)(A(ag)(ac)))
    val rightSide = A(A(as)(af))(ag)

    leftSide == rightSide
  })
}

The right side is straightforward—we're applying lifted functions f and g in succession on some effect, as. As the composition law states, this must be preserved if we apply composition inside of an applicative. This is what the left side does. It is better to read it from right to left: we're lifting our function which composes functions into the applicative and than applying lifted f and g in succession, but this time inside of the A. This gives us a compose function that's built inside of the applicative, which we finally apply to as.

For a valid applicative, all of these properties must hold, as well as the functor properties we defined earlier, as shown in the following snippet (not showing the implicit parameters):

identityProp[A, F] && homomorphism[A, B, F] && interchange[A, B, F] && composition[A, B, C, F] && FunctorSpecification.functor[A, B, C, F]

Secured with properties, we can define a few instances of applicative for the standard effects, just like we did for functor. The Option is arguably the easiest one to implement. Unfortunately, we can't just delegate to the instance method as we did with map, so we have to get our hands dirty:

implicit val optionApplicative: Applicative[Option] = new Applicative[Option] {
  ... // map and mapC are the same as in Functor
  override def apply[A, B](a: Option[A])(f: Option[A => B]): Option[B] = (a,f) match {
    case (Some(a), Some(f)) => Some(f(a))
    case _ => None
  }
  override def unit[A](a: => A): Option[A] = Some(a)
}

The type signatures dictate the implementation. We can't return Option[B] in any other way but by applying f to a. Similarly, we can't return Option[A] from the unit method. Please pay attention, though, to how we're using the Some constructor in both cases instead of the Option constructor. This is done in order to preserve structure in the case of null parameters or returned values.

The implementation for Either and Try is very similar with respect to the effect type. Remarkably, our Bucket type, which is represented by List, is quite different:

implicit val bucketApplicative: Applicative[List] = new Applicative[List] {
  ... // map and mapC are the same as in Functor
  override def apply[A, B](a: List[A])(f: List[A => B]): List[B] = (a, f) match {
    case (Nil, _) => Nil
    case (_, Nil) => Nil
    case (aa :: as, ff :: fs) =>
      val fab: (A => B) => B = f => f(aa)
      ff(aa) :: as.map(ff) ::: fs.map(fab) ::: apply(as)(fs)
  }
  override def unit[A](a: => A): List[A] = List(a)
}

Because we need to apply all functions to all arguments, we're doing this in a recursive way in our example (notice that it is not tail-recursive!) by splitting the process into four parts—dealing with both first elements, the first element and all of its functions, all of the elements and the first function, and the recursive call for all but the first elements from both lists.

With bucketApplicative at hand, we can finally finish our curried pieInProgress function by first applying it to potato and then to milk:

def bakeFish: FreshFish => Int => Float => FishPie = (bakePie _).curried

val pieInProgress: List[Int => Float => FishPie] = 
  mapFunc(freshFishMaker(bucketOfFish))(bakeFish)

def pie(potato: Bucket[Int], milk: Bucket[Float]) = 
  bucketApplicative(milk)(bucketApplicative(potato)(pieInProgress))

scala> pie(List(10), List(2f))
res0: List[ch08.Model.FishPie] = List(FishPie(21), FishPie(11), FishPie(78))

This definition works and produces the expected result—nice. But the implementation does not show the intent to mix three ingredients, which is not so nice. Let's improve this.

In fact, there are three different valid ways to define an applicative in terms of its basic functions:

The one we just implemented, with apply and unit.
To define it with the unit and map2 methods so that map2[A, B, C](fa: F[A], fb: F[B])(f: (A, B) => C): F[C].
To define it with the unit, map, and product functions so that product[A, B](fa: F[A], fb: F[B]): F[(A, B)].

The apply and map2 methods are equally powerful in the sense that it is possible to implement one in terms of another. The same applies to product, though it is weaker as it needs a map function to be defined.

As these functions are equally powerful, we can implement them directly in the type class definition so that they are available on all type class instances. The map2 method looks good to start with:

trait Applicative[F[_]] extends Functor[F] {
  // ...
  def map2[A,B,C](fa: F[A], fb: F[B])(f: (A, B) => C): F[C] =
    apply(fb)(map(fa)(f.curried))
}

The implementation almost looks disappointing in its simplicity—we just apply fa and fb in succession to the given f we converted to the curried form so that we are able to apply them in two steps.

It is interesting how the map2 method is implemented in terms of map, which in a sense is a map of lower power. The curious readers out there could be asking if it is possible to implement a map with yet another function of lower power. It turns out we can do this! Here is the implementation:

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

All we need to do is lift the given function f into the context of applicative and use the apply function we already have.

This way of defining functions in terms of other functions is common in functional programming. All the way down in the abstraction, there are methods that provide the basis for all other definitions and cannot be defined as a combination of other methods. These are called primitive. The tree flavors of applicative we are talking about are different by their choice of primitive functions. As it turns out, our initial choice was the first of them, that is, the unit and apply methods. Using these primitive functions, we were able to define the Functor in terms of Applicative! It makes sense to do the same and define a Functor.mapC in terms of map:

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

The nice side-effect of deriving implementations this way is that as soon as primitive functions are implemented properly and obey the applicative (or functor) laws, the derived implementations should be lawful as well.

Back to the flavors of applicative—we still need to implement the product method which creates an applicative of a product from two applicatives:

def product[G[_]](G: Applicative[G]): Applicative[({type f[x] = (F[x], G[x])})#f] = {
  val F = this
  new Applicative[({type f[x] = (F[x], G[x])})#f] {
    def unit[A](a: => A) = (F.unit(a), G.unit(a))
    override def apply[A,B](p: (F[A], G[A]))(fs: (F[A => B], G[A => B])) =
      (F.apply(p._1)(fs._1), G.apply(p._2)(fs._2))
  }
}

This time, we had to use a type lambda again to represent a product of two types, F and G, as a single type. We also needed to store the reference to the current instance of the applicative as F so that we're able to call its methods later. The implementation itself is naturally expressed in terms of the unit and apply primitives. For the resulting applicative, the unit is defined as a product of units for F and G, and the apply is just a product of using an apply method on the given arguments.

Unfortunately, we still can't define our pie function in a very readable way. If only we had map3, we could implement it as follows:

def pie3[F[_]: Applicative](fish: F[FreshFish], potato: F[Int], milk: F[Float]): F[FishPie] =
  implicitly[Applicative[F]].map3(fish, potato, milk)(bakePie)

Obviously, this implementation expresses a very clear intent: take three containers full of ingredients, apply a function on these ingredients, and get a container with pies back. This works for any container for which an instance of an Applicative type class is available.

Well, we already know how to derive functions from primitives defined for an abstraction. Why don't we do this again? Here goes:

def map3[A,B,C,D](fa: F[A],
                  fb: F[B],
                  fc: F[C])(f: (A, B, C) => D): F[D] =
  apply(fc)(apply(fb)(apply(fa)(unit(f.curried))))

Hmm, it turned out to be a definition for the map2 function, just extended with one more call for an apply for a third parameter! Needless to say, it is possible to implement the mapN method for any arity like this. We can also define it in an inductive way by calling a map of smaller arity:

def map4[A,B,C,D,E](fa: F[A],
                    fb: F[B],
                    fc: F[C],
                    fd: F[D])(f: (A, B, C, D) => E): F[E] = {
  val ff: (A, B, C) => D => E  = (a,b,c) => d => f(a,b,c,d) 
  apply(fd)(map3(fa, fb, fc)(ff))
}

We just needed to convert the provided function to the form where we can feed it with all but the last parameters and the last parameter separately.

Now, as we have our pie3 implementation, we must stop for a moment. We need to tell you something. Yes, we need to admit that we cheated a bit as we defined the check function. Surely, we can't just return FreshFish every time we have Fish as we did before:

lazy val check: Fish => FreshFish = f => FreshFish(f)

We did this on purpose so that we're able to focus on Applicative. Now, we are ready to improve on this. We are already familiar with the notion of optionality, so we could change this function to return an Option:

lazy val check: Fish => Option[FreshFish]

But let's decide which kind of effect it should be later. Let's call it F for now. We need two possibilities:

To return an empty F in the case that the fish is not fresh
To return an F with a fresh fish otherwise

In terms of abstractions, we have a way to lift a fish into F as soon as we have an applicative for it—the applicative gives this as a unit. All we need is an empty F[FreshFish], which we'll provide as an argument to the function.

Hence, our new definition for the check will look as follows:

def checkHonestly[F[_] : Applicative](noFish: F[FreshFish])(fish: Fish): F[FreshFish] =
  if (scala.util.Random.nextInt(3) == 0) noFish else implicitly[Applicative[F]].unit(FreshFish(fish))

Having empty F as a separate argument list will allow us to partially apply this function later. The preceding implementation returns an empty F in approximately 30% of cases. We're asking the compiler to check that the implicit Applicative is available for F, as discussed. If this is the case, our implementation will delegate to it to create a proper result.

OK, we now have a way to separate fresh fish from the rest, but there is another problem. Our pie3 function expects all of the ingredients to be wrapped in the same type of applicative. This is common in functional programming, and we'll deal with this impediment by lifting other parameters into the same container. We could introduce checks for freshness for potatoes and milk in the same way that we did for fish, but for simplicity, we'll assume they are always fresh (sorry, critical reader):

def freshPotato(count: Int) = List(Some(count))
def freshMilk(gallons: Float) = List(Some(gallons))

val trueFreshFish: List[Option[FreshFish]] = 
  bucketOfFish.map(checkHonestly(Option.empty[FreshFish]))

With all of the ingredients checked for freshness, we can use our existing pie3 function, almost like we did before:

import ch08.Applicative._
def freshPie = pie3[({ type T[x] = Bucket[Option[x]]})#T](trueFreshFish, freshPotato(10), freshMilk(0.2f))

The difference is that we need to help the compiler to recognize the proper type parameter. We do this by using the type lambda to define the type of the container explicitly. There is one missing piece of the puzzle, though. If we try to compile the preceding code, it will fail because we don't have an instance of Applicative[Bucket[Option]] yet.

Ready to roll up your sleeves and implement it? Well, although there is nothing wrong with getting our hands dirty, we don't want to implement a new applicative each time we'd like to have a composition of them. What we'll do instead is define a generic combination of applicatives, which is itself an applicative. The fact that applicatives compose is their most admirable property. Let's see how this works. This is how we can implement it for our Applicative[F]:

  def compose[G[_]](G: Applicative[G]): Applicative[({type f[x] = F[G[x]]})#f] = {
    val F = this

    def fab[A, B]: G[A => B] => G[A] => G[B] = (gf: G[A => B]) => (ga: G[A]) => G.apply(ga)(gf)

    def fg[B, A](f: F[G[A => B]]): F[G[A] => G[B]] = F.map(f)(fab)

    new Applicative[({type f[x] = F[G[x]]})#f] {
      def unit[A](a: => A) = F.unit(G.unit(a))
      override def apply[A, B](a: F[G[A]])(f: F[G[A => B]]): F[G[B]] =
        F.apply(a)(fg(f))
    }
  }

Again, we had to use the type lambda to tell the compiler that this is actually just a single type parameter and not two. The implementation of the unit method is just wrapping one applicative into another. The apply method is more complex and we implemented it as a local function to make it clearer what is happening. The first thing we're doing is converting the internal function of type G[A => B] to the type G[A] => G[B]. We're doing this by applying the applicative G on the "internal" function wrapped inside of f. Now that we have this function, we can call the map function of the outer applicative to wrap the result into F. The last thing we're doing is applying this wrapped composed function on the original function and the resulting function, that is, to the original argument of the apply method.

Now, we can compose these applicatives as we wish:

implicit val bucketOfFresh: ch08.Applicative[({ type T[x] = Bucket[Option[x]]})#T] = 
  bucketApplicative.compose(optionApplicative)

And use this combination to call our original pie-making logic:

scala> println(freshPie)
List(Some(FishPie(40)), None, Some(FishPie(36)))

The beauty of this approach is that it allows us to reuse existing logic with arbitrarily nested applicatives, just like in the following artificial example:

import scala.util._
import ch08.Applicative
def deep[X](x: X) = Success(Right(x))
type DEEP[x] = Bucket[Try[Either[Unit, Option[x]]]]

implicit val deepBucket: Applicative[DEEP] =
 bucketApplicative.compose(tryApplicative.compose(eitherApplicative[Unit].compose(optionApplicative)))

val deeplyPackaged =
  pie3[DEEP](trueFreshFish.map(deep), freshPotato(10).map(deep), freshMilk(0.2f).map(deep))

All that we need in the case that the structure of containers changes is to define a new composite applicative (and a few syntactic helpers like the type alias as a constructor, but these aren't essential). Then, we are able to use the existing logic as we did previously. This is what the result looks like in REPL:

scala> println(deeplyPackaged)
List(Success(Right(Some(FishPie(46)))), Success(Right(Some(FishPie(54)))), Success(Right(None)))

We can easily change the structure of the result by rewiring the composite applicative:

type DEEP[x] = Try[Either[Unit, Bucket[Option[x]]]]

implicit val deepBucket: Applicative[DEEP] = 
 tryApplicative.compose(eitherApplicative[Unit].compose(bucketApplicative.compose(optionApplicative)))

val deeplyPackaged =
  pie3[DEEP](deep(trueFreshFish), deep(freshPotato(10)), deep(freshMilk(0.2f)))

We changed the composition order and now the result looks different:

scala> println(deeplyPackaged)
Success(Right(List(Some(FishPie(45)), Some(FishPie(66)), None)))

Does it feel like combining applicatives leaves no desires unfulfilled? Well, in a sense, it is, except for the case that we want to change the structure of the result at hand. To give you an example, let's recall the result of our baking endeavor for the fresh fish: List(Some(FishPie(45)), Some(FishPie(66)), None). It is a bucket containing either a pie, if the fish was fresh, or nothing if it was not. But what if we hired a new cook and now every single fish in the bucket has to be fresh or the whole bucket is discarded? Our return type would be Option[Bucket[FishPie]] in this case—the bucket is full of pies if we have a bucket of fresh fish, or nothing. We want to keep our kitchen processes, though! This is the time for the Traversable functor to enter the scene.

Table of Contents for Applicative

Create new playlist

Sign In

Sign Up

Table of Contents for
Applicative