A cow is transformed to four cows

Introduction

This post is aimed at the Scala programmer who is familiar with the basics of the language and ideally becoming interested, or already deeply entrenched, in pure functional programming and curious about Applicative Functors. We’ll delve into the original paper in which they were introduced, converting the Haskell code to modern Scala, both custom code and using Cats, Cats Effect and Zio. Finally, we’ll look at an efficient implementation of blending two images using Applicative programming.

Functor and Monad

As a Scala programmer, you will be no doubt be familiar with the map and flatMap functions, which you will find in some of the collections and other data types in the standard Scala library. If you’re interested in pure functional programming, and have used the Cats or Scalaz libraries, you may know that these two functions are part of the Functor and Monad type classes respectively.

Before looking at Apply and Applicative let’s review what you can do Functors and Monads.

Remember, the goal of functional programming is to do most of our work using pure functions. We use structures like Functors and Monads to manage effects (things that are not pure); letting us use pure functions in an effectful world. The Functor type class gives us the power to take a pure function like a => a + 1 and apply it to the value inside an effect. Here are a couple of examples of using Functor’s map on two data types…

List(1,2,3).map(a => a + 1)
// res: List[Int] = List(2, 3, 4)

Option(1).map(a => a + 1)
// res: Option[Int] = Some(2)

Functor gives you the ability to reach inside an effect, apply a pure function to the value inside there, and wrap it up inside an effect of the same type. The type signature of map is map[A,B](fa: F[A], f: A => B): F[B].

Monad instances have two functions. The first, pure or unit, gives us a way to lift pure values into an effectful context. pure[A](a: A) F[A] and you can think of it as being a type constructor…

import cats._
import cats.implicits._

1.pure[List]
// res: List[Int] = List(1)

1.pure[Option]
// res: Option[Int] = Some(1)

Pure isn’t really giving us something we didn’t already have; we could make a list and an option before. But the pure function is useful as a building block when building code that uses Monad instances. We’ll see it in use later.

Finally, Monad has the flatMap function. The signature is flatMap[A,B](fa: F[A], f: A => [B]): F[B]. flatMap comes in handy when we compose two effects together. It let’s you get the result from the first and pass it as a (pure) parameter to the next. For example, imagine we have two calls that go out over the network to a database or external service and we use map to chain them together…

def getUser(email: String): Future[User] = ???

def getAccountStatus(id: String): Future[AccountStatus] = ???

val accountStatus = getUser("bob@google.com")
  .map(user => getAccountStatus(user.accountId))
// accountStatus has type Future[Future[AccountStatus]]

Dealing with nested effects like Future[Future[_]] creates a burden on us to reach inside the layers one at a time. If we used flatMap instead it would take care of flattening the result for us…

val accountStatus = getUser("bob@google.com")
  .flatMap(user => getAccountStatus(user.accountId))
// accountStatus has type Future[AccountStatus]

That is the essence of Monads; being able to compose effects together. Note that the second call is dependent on the first. It would make no sense to call getAccountStatus before we called getUser because we need the user’s account ID. In fact, even if these two effects were completely independent, we would still have to wait for the first one before calling the second. That’s not an ideal situation because these calls may take tens or even a few hundred milliseconds. If we want the service to be low latency, we would like to run these calls concurrently instead of in sequence.

What’s Ap?

Now we’re caught up Functors and Monads, let’s look at the Applicative typeclass. It is defined as follows in Cats, with some details removed…

trait Applicative[F[_]] extends Apply[F] {
  def pure[A](x: A): F[A]
}

If you make an instance of Applicative then you need to supply an implementation of pure which is exactly the same as pure found in Monads. You also need to implement Apply which looks like this…

trait Apply[F[_]] extends Functor[F] {
  def ap[A, B](ff: F[A => B])(fa: F[A]): F[B]
}

You can see that Apply extends Functor which means it has map. Also it has the function ap which is, of course, the main subject of this post. What a curious type signature! Just like with map we are dealing with an effect type F, and a parameter F[A]. The difference is the function we want to apply (ff: F[A => B]) is also inside the effect.

Before talking about what this is useful for, let’s look at what it actually does for various implementations.

Applicative instance for Option

Option((a:Int) => a + 10).ap(Option(20))
// res: Option[Int] = Some(30)

Option((a:Int) => a + 10).ap(None)
// res: Option[Int] = None

Option.empty[Int => Int].ap(Option(20))
// res: Option[Int] = None

Option.empty[Int => Int].ap(Option.empty[Int])
// res: Option[Int] = None

The ap function for Option, then, behaves probably as you’d expect. When you apply the function, if the ff argument is None then there’s nothing to apply and we get the result None. If there is a function in there, we extract it so that we have a pure function that we can apply to the effectful argument F[A]. Again, if that is empty we get None, otherwise, we get the value f(a) which will be wrapped back up in the effect giving Some(30).

Applicative instance for List

List((a:Int) => a + 1,
     (a:Int) => a - 10,
     (a:Int) => a + 22).ap(List(1,2,3))
// res: List[Int] = List(2, 3, 4, -9, -8, -7, 23, 24, 25)

For List the input value for ff has the signature List[A => B], and each function in the list is applied to each argument in the input list.

Idomaticly apply all the things

All data types that have instances of Applicative have a way to apply a function wrapped in an effect of that type, and the way that it is applied is idomatic to that effect. In fact, before the name Applicative Functor stuck, they were called Idioms.

You may be scratching your head at this point, for it’s not often in programming that you want to apply a list of functions to a list (although I’m sure you can probably come up with some ways to use it), and how often do you have functions in Options? It gets weirder in the case of other data types. With Future, or IO, for example, do you ever remember writing a function that returns a function from a Future? It’s certainly rare. Still more strange would be a function inside a State monad, but that is perfectly valid too…

import cats.data.State

// Create a function in a State
val fs = State[Int, (Int => Int)]
  (s => (s, (a: Int) => a + s))

// Now to apply it to an appropriate State
val applied = fs.ap(State[Int, Int](s => (s,10)))

// Finally run the Applicative State and grab the value
applied.run(10).value
//res: (Int, Int) = (10, 20)

I don’t think you can get the answer to “What’s Ap” just by looking at type signatures and examples. To really understand applicative style in depth I thought I would walk through the seminal paper on the subject and get it from the originators…

Applicative Programming with Effects

Let’s Apply ourselves

Applicative Functors first saw the light of day in the 2008 paper by McBride and Patterson, “Applicative Programming with Effects” which you can find here…

https://www.staff.city.ac.uk/~ross/papers/Applicative.pdf

The paper begins with three motivating examples for the use of Applicative style…

This is the story of a pattern that popped up time and again in our daily work, programming in Haskell (Peyton Jones, 2003), until the temptation to abstract it became irresistible. Let us illustrate with some examples.

We’ll walk through each of these examples and convert them to use Scala…

Sequencing Commands

One often wants to execute a sequence of commands and collect the sequence of their responses, and indeed there is such a function in the Haskell Prelude (here specialised to IO)

sequence :: [IO a ]  IO [a ]
sequence [ ] = return [ ]
sequence (c : cs) = do
  x  c
  xs  sequence cs

Before we get started, if you’re following along in your Scala IDE or REPL you will need some imports listed below. You can also clone the Github repository.

import zio._
import zio.console._
import zio.clock._
import zio.duration._
import cats.Applicative
import cats.implicits._

… and the following libraries …

libraryDependencies ++= Seq(
 "org.typelevel" %% "cats-core" % "2.1.1",
 "dev.zio" %% "zio" % "1.0.0-RC18")

I am using ZIO in place of Haskell’s IO Monad, and bringing in Cats to use its Applicative.

Converting the sequence function from Haskell to Scala…

  def monadicSequence[Z,E,A](ios: List[ZIO[Z, E, A]]): ZIO[Z, E, List[A]] = {
    ios match {
      case Nil =>
        zioApplicative.pure(List.empty[A])
      case c :: cs =>
        for (
          x <- c;
          xs <- monadicSequence(cs)
        ) yield (x +: xs)
    }
  }

If you’re not familiar with ZIO you can think of it as a replacement for the standard library Scala Future, but it has better performance and a lot more features. It is also not eagerly evaluated like Future. To explain, when you create a future it runs immediately and you cannot run it again. You can create a ZIO and run it when you decide to and as many times as you want.

To demonstrate this sequence running let’s write an implementation of a silly algorithm called Sleep Sort. Sleep Sort works by waiting an amount of time based on the value of the number. Emitting the numbers in this way sorts them (assuming your scheduler is accurate enough). Let’s be clear, this is a stupid way to sort numbers, but it’s handy as a way to illustrate our monadicSequence function.

def delayedPrintNumber(s: Int): ZIO[Console with Clock,String,Int] = {
    putStrLn(s"Preparing to say number in $s seconds") *>
    putStrLn(s"$s").delay(s.seconds) *>
    ZIO.succeed(s)
}
val ios1 = List(6,5,2,1,3,8,4,7).map(delayedPrintNumber)
// ios1: List[ZIO[Console with Clock,String,Int]]

The function creates an IO effect, which when run will immediately print a message and then wait s seconds before printing the number. We map the function across a list of numbers to generate a list of IO effects, which we can then run.

You may be surprised that this does not work. Instead of running all the effects at once and printing them out in order it just executes the first IO (wait 6 seconds), then the second (wait 5 seconds).

Monadic version

Preparing to say number in 6 seconds
6
Preparing to say number in 5 seconds
5
// ... and so on for a while

If you were not surprised maybe you’re ahead of me, and know that our monadicSequence function cannot possibly run all the effects at once by virtue of it being monadic in the first place.

That for comprehension is really hiding that we are calling flatMap on each successive IO, and flatMap sequences things together. You must wait for the result of the first effect before you can evaluate the second. So whilst the first implementation of sequence in the paper will absolutely work, it will not let us implement our sleep sort, nor let us parallelize the IO’s in general.

Back to the paper, at this point the authors observe…

In the (c : cs) case, we collect the values of some effectful computations, which we then use as the arguments to a pure function (:). We could avoid the need for names to wire these values through to their point of usage if we had a kind of ‘effectful application’.

By effectful application they are talking about the ap function, and they go on to say that it lives in the Haskell Monad library. Given that function they rewrite the sequence function as follows…

sequence :: [IO a ]  IO [a ]
sequence [ ] = return [ ]
sequence (c : cs) = return (:) ‘ap‘ c ‘ap‘ sequence cs

Except for the noise of the returns and aps, this definition is in a fairly standard applicative style, even though effects are present.

Note that the ap they are using here is in the Monad library, and implemented using flatMap, so it will not yet allow our sleep sort to work. However, I’ve implemented an Applicative instance for ZIO which does not have that limitation…

implicit def zioApplicative[Z,E] = new Applicative[ZIO[Z,E,?]] {
    def pure[A](x: A) = ZIO.succeed(x)
    def ap[A, B](ff: ZIO[Z,E,A => B])(fa: ZIO[Z,E,A]) = {
      map2(ff, fa){
        (f,a) =>
          f(a)
      }
    }
    override def map2[A, B, C](fa: ZIO[Z,E,A], fb: ZIO[Z,E,B])(f: (A, B) => C) :
      ZIO[Z,E,C] = {
        fa.zipPar(fb).map{case (a,b) => f(a,b)}
    }
  }

It’s not important to understand all the details here, all you need understand is we now have an ap that we can apply to ZIO effects that is truly parallel, so if you’re not interested then skip to the next paragraph.

The pure function is straightforward, it just wraps a pure value in a succeeded ZIO. The ap function is more interesting. Whilst it’s not obvious how you would implement ap in for ZIO, it is really easy to implement map2. map2 comes in handy because it lets you take the results of two effects and pass them to a pure function. The function has the signature f: (A, B) => C. We use the ZIO function zipPar to execute the two effects in parallel, and if both fa and fb yield values then they are mapped with the pure function giving us a ZIO with the final result inside. Happily, you can implement ap in terms of map2, so that solves our problem.

Here’s the conversion of the applicative version of sequence to Scala…

def applicativeSequence[Z,E,A](ios: List[ZIO[Z, E, A]]): ZIO[Z, E, List[A]] = {
    ios match {
      case Nil =>
        ZIO.succeed(List.empty[A])
      case c :: cs =>
        val ff: ZIO[Z,E, A => (List[A] => List[A])] =
          zioApplicative.pure(((a: A) => (listA: List[A]) => a +: listA))
        val p1 = ff.ap(c)
        p1.ap(applicativeSequence(cs))
    }
  }

It’s a little bit noisier than the Haskell code, but most of that is having to be more verbose about the types to keep the type checker happy. In fact the parts of each implementation match up together.

Now we can run that and you will see that the effects are now parellelised and our sleep sort works!

Applicative version

Preparing to say number in 6 seconds
Preparing to say number in 2 seconds
Preparing to say number in 1 seconds
Preparing to say number in 3 seconds
Preparing to say number in 8 seconds
Preparing to say number in 4 seconds
Preparing to say number in 7 seconds
Preparing to say number in 5 seconds
1
2
3
4
5
6
7
8

Note that the point the authors were making here was just to show that the sequence function is a pattern that came up often, that could be more succinctly expressed with ap. Showing that it also enables our effects to run in parallel, given the correct implementation, was just to show one of the benefits of avoiding Monad when effects are not dependent on each other.

Matrix Transposition

The second example in the paper is that of Matrix transposition, which takes a matrix and flips it along a diagonal. For example…

Original matrix
 1  2  3  4  5
 6  7  8  9 10
11 12 13 14 15

Transposed matrix
 1  6 11
 2  7 12
 3  8 13
 4  9 14
 5 10 15

In Haskell, we first see this implememtation of transpose…

transpose :: [[a ]]  [[a ]]
transpose [ ] = repeat [ ]
transpose (xs : xss) = zipWith (:) xs (transpose xss)

repeat :: a  [a ]
repeat x = x : repeat x

Let’s translate this to Scala. The algorithm works by taking each row in turn and zipping it with each subsequent row.

First, we need to be careful about the function repeat which returns an infinite number of whatever x is. This is used in the transpose for the last row of the matrix where we want a number of empty lists to finish our recursion but we don’t know how many, so we want to just keep taking them. Since Haskell is by default lazily evaluated this will work fine. In Scala as soon as we evaluate repeat we will run into an infinite loop. That’s easily fixed by switching to LazyList which is part of the standard library. (Before Scala 2.13 it was called Stream).

def repeat[A](a: A): LazyList[A] = a #:: repeat(a)

The function zipWith has the following type signature…

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]

In other words, it takes two lists and a pure function of two arguments, and creates a new list by applying the function to each element. It will stop once it runs out of elements in one of the lists. Here’s the Scala version.

def zipWith[A, B, C](as: LazyList[A], bs: LazyList[B])(
      f: (A, B) => C): LazyList[C] = {
    as.zip(bs).map { case (a, b) => f(a, b) }
  }

With the pieces in place I can now implement the transpose as follows…

def transpose[A](matrix: LazyList[LazyList[A]]): LazyList[LazyList[A]] = {
  matrix match {
    case LazyList() => repeat(LazyList.empty)
    case xs #:: xss =>
      zipWith(xs, transpose(xss)) {
        case (a, as) =>
          a +: as
      }
  }
}

The next step in the paper is to make this look a bit more applicative by using a combination of repeat and zapp

zapp :: [a  b ]  [a ]  [b ]
zapp (f : fs) (x : xs) = f x : zapp fs xs
zapp = [ ]

transpose :: [[a ]]  [[a ]]
transpose [ ] = repeat [ ]
transpose (xs : xss) = repeat (:) ‘zapp‘ xs ‘zapp‘ transpose xss

Except for the noise of the repeats and zapps, this definition is in a fairly standard applicative style, even though we are working with vectors.

Evaluating Expressions

The third example of applicative style is an expression evaluator that can add numbers, both literals and numbers bound to strings and stored in an environment.

When implementing an evaluator for a language of expressions, it is customary to pass around an environment, giving values to the free variables.

The Haskell code looks like this…

data Exp v = Var v
  | Val Int
  | Add (Exp v) (Exp v)

eval :: Exp v  Env v  Int
eval (Var x ) γ = fetch x γ
eval (Val i) γ = i
eval (Add p q) γ = eval p γ + eval q γ

Converting to Scala is straightforward…

sealed trait Exp
case class Val(value: Int) extends Exp
case class Add(left: Exp, right: Exp) extends Exp
case class Var(key: String) extends Exp

case class Env[K](kv: Map[K,Int])

def fetch(key: String)(env: Env[String]) : Int =
  env.kv.getOrElse(key, 0)

def eval(exp: Exp, env: Env[String]) : Int = {
  exp match {
    case Val(value) => value
    case Var(key) => fetch(key)(env)
    case Add(left, right) =>
      eval(left, env) + eval(right, env)
  }
}

Here I’ve made the environment a simple key value store, and, to avoid complicating the example with error handling, if a variable is not present in the environment I just default to returning zero.

Following the pattern of the previous two examples, the authors then pull some magic to make the applicative pattern more noticeable…

We can eliminate the clutter of the explicitly threaded environment with a little help from some very old friends, designed for this purpose

eval :: Exp v  Env v  Int
eval (Var x ) = fetch x
eval (Val i) = K i
eval (Add p q) = K (+) ‘S‘ eval p ‘S‘ eval q

where
K :: a  env  a
K x γ = x

S :: (env  a  b)  (env  a)  (env  b)
S ef es γ = (ef γ) (es γ)

So this all looks a bit cryptic. Who are the old friends? Well, if you look at the type signature of K it is actually the pure function, and S is the ap function. This is in fact what we’d call the Reader Monad in Scala.

By old friends, the authors are referring to the SKI Combinator Calculus.

Let’s reimplement in Scala using the Reader.

def fetchR(key: String) = Reader[Map[String,Int], Int](env => env.getOrElse(key, 0))
def pureR(value: Int) = Reader[Map[String,Int], Int](env => value)

def evalR(exp: Exp): Reader[Map[String,Int], Int] = {
  exp match {
    case Val(value) => pureR(value)
    case Var(key) => fetchR(key)
    case Add(left, right) =>
      val f = Reader((env:Map[String,Int]) =>
        (a:Int) => (b:Int) => a + b)
      val leftEval = evalR(left).ap(f)
      evalR(right).ap(leftEval)
  }
}

And take it for a test drive…

val env1 = Env(Map("x" -> 3, "y" -> 10))
val exp1 = Add(Val(10), Add(Var("x"), Var("y")))

println(s"Eval : ${eval(exp1, env1)}")
// Eval : 23

The Applicative Type class

To summarize, we’ve seen three different effects used in applicative style; IO (or ZIO), List and Reader. Now you can see why it makes sense to be able to apply a function that is wrapped in these effects. What we needed, and got with ap, is a way to lift a pure function so we can apply it to a chain of effects of the same effect type.

Next in the paper, the authors describe the laws which an instance of the Applicative type class must adhere to, which is out of scope for this post but is put succinctly in English as follows…

The idea is that pure embeds pure computations into the pure fragment of an effectful world—the resulting computations may thus be shunted around freely, as long as the order of the genuinely effectful computations is preserved.

For more detail on the applicative laws check out chapter 12, section 5 of The Red Book

Applicatives are all Functors (hence the name Applicative Functors), because you can implement the map operation as follows…

// Declare map in terms of pure and ap
def map[A,B,F[_]: Applicative](fa: F[A], f: A => B): F[B] = {
  Applicative[F].pure(f).ap(fa)
}

// Map a function over a list
map(List(1,2,3,4,5), (a:Int) => a + 1)
// res: List[Int] = List(2, 3, 4, 5, 6)

Note that you don’t have to do this with Cats instances because all Applicatives have their Functor instance taken care of too.

The paper then notes that all uses of Applicatives follow this pattern of lifting a pure function and applying it to a chain of effects, and suggests a new syntax for shifting into the Idiom of the applicative functor. The syntax is a special pair of brackets…

[[ ff f1 f2 f3 ... fn ]]

Although this has not been widely adopted in either Haskell or Scala as far as I can tell, you can try it yourself using this delightfully named (and implemented) Scala library: Idiom Ears. This will let you closely match the syntax from the paper; for example…

val f = (a: Int) => (b: Int) => a * b
⊏| (f) (List(1, 2)) (List(3, 4)) |⊐
// List(3, 4, 6, 8)

// Which is equivalent to
Applicative[List].pure(f).ap(List(1,2)).ap(List(3,4))

If you do fall in love with the idiom brackets of McBride and Patterson then knock yourself out, but you may have to invest some time bringing the project back to life as it has suffered some bitrot since 2016. There is a demo of IdiomEars in the Github repository accompanying this post, but I simply copied the code into my project rather than spend time updating it.

Moving right along to Traverse

Have you noticed that sequence and transpose now look rather alike? The details that distinguish the two programs are inferred by the compiler from their types. Both are instances of the applicative distributor for lists.

At this point in the paper we have seen the birth of the Applicative type class which encapsulates the ap and pure functions needed to implement the patterns above. Next, the authors describe another new type class, Traverse, which lets us generalize the pattern further…

dist :: Applicative f  [f a ]  f [a ]
dist [ ] = ⊏| [ ] |⊐
dist (v : vs) = ⊏| (:) v (dist vs) |⊐

Note that I’m using the unicode from Idiom Ears to replace the fancy brackets from the paper which I cannot reproduce here, but you get the idea. Let’s rewrite in Scala…

// applicative distributor for lists
def dist[A, F[_]](fs: List[F[A]])(implicit app: Applicative[F]): F[List[A]] = {
  fs match {
    case Nil =>
      app.pure(List.empty[A])
    case c :: cs =>
      val w1 = app.pure((a: A) => (listA: List[A]) => a +: listA)
      val w2 = w1.ap(c)
      w2.ap(dist(cs))
  }
}

// dist a list of options
println(dist(List(Option(10), Option(10), Option(3), Option(4))))
// Some(List(10, 10, 3, 4))

// Note that we have short circuiting
println(dist(List(None, Option(10), Option(3), Option(4))))
// None

Note that this short-circuits. We fail as soon as a single None shows up. Why? It’s because although applicative allows us to avoid the enforced sequencing of Monad’s flatMap, many types have instances of ap implemented in terms of flatMap anyway, because that matches the expectation of users for that type.

We could override the Cats instance for Option with our own. What we do instead is create Applicative versions of type classes. For example, our monadic friend Either (which represents an error or a success value) has an applicative alter-ego Validated. Rather than short-circuit on failure, Validated allows us to accumulate errors so we can provide valuable feeback ot the caller. That is one of the super-powers of Applicatives!

val someValidateds: List[Validated[NonEmptyList[String],Int]] =
  (List("Had some error".invalidNel, 10.valid, "Another error".invalidNel, 4.valid))

// Try the same with Validated that has an Applicative instance
println("Validated failure example: " + dist(someValidateds))
// Validated failure example: Invalid(NonEmptyList(Had some error, Another error))

Just by changing data types we have completely changed the behaviour from short-circuiting to being able to accumulate the errors. Just imagine that these are expensive computations or slow network calls, and you can see how avoiding sequencing can really save us in computing costs, and thereby save us money. Furthermore, we can improve user experience. We can validate a whole form from the user at once and send all the corrections needed rather than necessitate a painful back and forth until the whole form is valid. Now get back to dist.

Distribution is often used together with ‘map’.

Fair enough. The dist function we developed above would be enhanced in usefulness if it could map a list of pure values into some effect type first. Let’s take a look at a poor way to implement that…

flakyMap :: (a  Maybe b)  [a ]  Maybe [b ]
flakyMap f ss = dist (fmap f ss)

We can translate pretty much directly to Scala…

def flakyMap[A,B](f: A => Option[B], as: List[A]): Option[List[B]] = {
  dist(as.map(f))
}

println("Flakymap success: " + flakyMap((n: Int) => Option(n * 2), List(1,2,3)))
// Flakymap success: Some(List(2, 4, 6))
println("Flakymap failure: " + flakyMap((n: Int) => if(n%2==1) Some(n) else None, List(1,2,3)))
// Flakymap failure: None

That’s clearly useful, and it works, but it’s flaky because we have to process the list twice. First we map over the list to transform it, then we do it again with the dist function. How about we do both at once? That’s Traverse

traverse :: Applicative f  (a  f b)  [a ]  f [b ]
traverse f [ ] = ⊏| [ ] |⊐
traverse f (x : xs) = ⊏| (:) (f x ) (traverse f xs) |⊐

And a Scala version…

def listTraverse[A, B, F[_]](f: A => F[B], fs: List[A])
     (implicit app: Applicative[F]): F[List[B]] = {
  fs match {
    case Nil =>
      app.pure(List.empty[B])
    case c :: cs =>
      val w1 = app.pure((b: B) => (listB: List[B]) => b +: listB)
      val w2 = w1.ap(f(c))
      w2.ap(listTraverse(f, cs))
  }
}
// Output is the same as flakyMap

By providing the identity function for f we get the sequence function back in terms of traverse…

def sequence[A, F[_]](fs: List[F[A]])
    (implicit app: Applicative[F]): F[List[A]] = {
  listTraverse((fa: F[A]) => fa, fs)
}

Finally, we get to the Traverse type class, which gives us an interface to write traverse for two effect types rather than just List and another effect. We have two functions, traverse and dist, which are represented in Scala today as traverse and sequence.

class Traversable t where
traverse :: Applicative f  (a  f b)  t a  f (t b)
dist :: Applicative f  t (f a)  f (t a)
dist = traverse id

There’s no need to show the Scala because we can rely on the implementations in the Cats library, but the instance implementations for list are as above. In the paper we see that you can also traverse more complex structures such as a tree…

sealed trait Tree[+A]
case object Leaf extends Tree[Nothing]
case class Node[A](left: Tree[A], a: A, right: Tree[A]) extends Tree[A]

def treeTraverse[A, B, F[_]](f: A => F[B], fs: Tree[A])
                (implicit app: Applicative[F]): F[Tree[B]] = {
  fs match {
    case Leaf =>
      app.pure(Leaf)
    case Node(left, a, right) =>
      val w1 = app.pure((l: Tree[B]) =>
        (v: B) =>
        (r: Tree[B]) => Node(l,v,r))
      val w2 = w1.ap(treeTraverse(f,left))
      val w3 = w2.ap(f(a))
      w3.ap(treeTraverse(f,right))
  }
}

val tree1 = Node(Leaf, 10, Node(Leaf, 5, Node(Leaf, 10, Leaf)))
println("treeTraverse: " + treeTraverse((n: Int) => Option(n + 1), tree1))
// treeTraverse: Some(Node(Leaf,11,Node(Leaf,6,Node(Leaf,11,Leaf))))

Note that in your own code you would usually lean on the Traverse type class and override some methods to provide your own implementations.

Another thing to highlight the expressive power of traverse is that we can use it to do a map just like a ~Functor by using the Id (identity) Monad as our effect type. The Id monad simply wraps a pure value and has no other effect, so we can use it to use traverse as a functor as follows…

@ List[Int](1,2,3).traverse((a: Int) => (1 + a): Id[Int])
// Id[List[Int]] = List(2, 3, 4)

Monoids are phantom Applicative functors

This section of the paper, part four if you are reading along, has an intriguing title. Whilst short, there is a lot of information in a small space on how we can use Monoids, Applicatives and Traverse to do some cool things. I will go much slower than the paper as some of the concepts take some time to get your head around.

Monoids are a type class that provides an interface to join things together such as appending strings or adding numbers. In addition, they give us a way to represent a zero value for the data type, which will be useful in a moment. If you want to dig into Monoids in more detail I have written a couple of posts on the subject…

Every Applicative is a Monoid

It’s possible to implement a Monoid instance that works for any Applicative. In Scala it looks like this…

implicit def appMonoid[A: Monoid, F[_]: Applicative] = new Monoid[F[A]] {
  def empty: F[A] = Applicative[F].pure((Monoid[A].empty))
  def combine(x: F[A], y: F[A]): F[A] =
    Applicative[F].map2(x,y)(Monoid[A].combine)
}

What does this give us? We can join Applicative Effects togther, and when we do so they are joined in the idiom of the effect type. So for example when combining a list with its default Monoid instance it will simply append the lists like this…

List(1,2,3) |+| List(4,5,6)
// res: List[Int] = List(1, 2, 3, 4, 5, 6)

But if instead we bring into scope a monoid for List we get the applicative application instead…

implicit val m = appMonoid[Int, List]
List(1,2,3) |+| List(4,5,6)
// res: List[Int] = List(5, 6, 7, 6, 7, 8, 7, 8, 9)

Magical Folding with Traverse

It does not work the other way around, but some types with Monoid instances can use those instances in their Applicative implementation. For example Tuple2 in the Cats library does just that. The actual implementation is split into two because of the way the Cats class hierarchy is organized, so here’s a simplified version where it is more clear what’s going on…

implicit def appTuple2[X: Monoid] = new Applicative[Tuple2[X,?]] {
  def pure[A](a: A): (X, A) = (Monoid[X].empty, a)

  def ap[A, B](ff: (X, A => B))(fa: (X, A)): (X, B) = {
    (ff._1.combine(fa._1),
     ff._2(fa._2))
  }
}

You can see how the fact that Monoids have an empty (or zero) value is useful here because when we implement pure we need a value of type X to build the response but we only have an A. By using the Monoid.empty function we can fulfil the contract.

The implementation of ap is also interesting. What happens is that the X values (which have a Monoid instance), are simply combined. The new value B is created by applying the function in ff to the value in fa and now we have our new Tuple2.

Recall the function signature for traverse on a List…

def traverse[G[_]: Applicative, A, B](fa: List[A])(f: A => G[B]): G[List[B]]

The G in traverse is used to apply the function f to each element of our collection, and so when we traverse and use Tuple2 as our G, it will use that Monoid implementation we see above. Take a list and reducing it to a single value is called various names including folding, reducing, crushing. In Scala we’d typically fold a list of elements with a Monadic structure. We can now do the same thing with traverse.

Traverse[List].traverse(List[Int](1,2,3))((n: Int) => Tuple2(n,n))
// res: (Int, List[Int]) = (6, List(1, 2, 3))

You can see that the resulting tuple consists of two things, the sum of the integers in the list (6) and second element is the list of results. That gives us the ability to transform a collection into a an aggregated (folded) value, and map it to a new collection at the same time!

Now often you may want to just fold the values and you don’t care about the other collection. In that case you could just drop it by calling ._2 on the result.

There’s a better way, and we can now move onto finding out about Phantom types and how they can help us here.

Phantom types

Now we can rejoin the paper. We are introduced the Accy type which is called Const in Cats.

newtype Accy o a = Acc{acc :: o }

In Scala the Const type can be implemented like this…

final case class MyConst[A,B](unConst: A)

If it helps, this is a type level version of a function that takes two parameters; an A and a B, and just drops the B returning the A…

def const[A, B](a: A)(b: => B): A = a

Const, or Accy, is a strange-looking data type that takes two type parameters, and in fact takes two values, but we only store the first. This is why the second parameter is called a phantom. We can create a Const with any crazy type we want for the B parameter because it won’t be used at all…

import com.oracle.webservices.internal.api.message.MessageContext
Const[Int,MessageContext](12).getConst
// res: Int = 12

So what use is Const? For one, we can create an applicative functor for it just like we did with Tuple, but now we can drop the pretense that we cared about the second value and just get the folded value, saving us CPU time and memory as the computation progresses…

Traverse[List].traverse(List(1,2,3,4,5))(a => Const[Int, String](a)).getConst
// res: Int = 15

Let’s convert the examples in the paper of using this technique into Scala…

accumulate :: (Traversable t, Monoid o)  (a  o)  t a  o
accumulate f = acc · traverse (Acc · f )
reduce :: (Traversable t, Monoid o)  t o  o
reduce = accumulate id
def accumulate[A,F[_]: Traverse, B: Monoid](f: A => B)(fa: F[A]): B = {
  Traverse[F].traverse(fa)((a: A) => Const.of[B](f(a))).getConst
}
def reduce[F[_]: Traverse, A: Monoid](fa: F[A]): A = {
  Traverse[F].traverse(fa)((a: A) => Const.of[A](a)).getConst
}
// Accumulate
println("accumulate: " + accumulate((s: String) => s.size)(List("ten", "twenty", "thirty")))
// 15

// Reduce
println("reduce: " + reduce(List("ten", "twenty", "thirty")))
// tentwentythirty

Note that we could implement reduce with accumulate as follows…

def reduceWithAccumulate[F[_]: Traverse, A: Monoid](fa: F[A]): A = {
  accumulate[A, F, A](identity)(fa)
}

We can also convert the following without much difficulty…

flatten :: Tree a  [a ]
flatten = accumulate (:[ ])
concat :: [[a ]]  [a ]
concat = reduce

Scala versions…

def treeFlatten[A](tree: Tree[A]): List[A] = {
  accumulate((a: A) => List(a))(tree)
}

def concatLists[A](fa: List[List[A]]): List[A] = {
  reduce(fa)
}

// Tree flattening
println("treeFlatten: " + treeFlatten(tree1))
// treeFlatten: List(10, 5, 10)

// Concat lists (flatten)
println("concatLists: " + concatLists(List(List(1,2,3), List(4,5,6))))
// concatLists: List(1, 2, 3, 4, 5, 6)

The last thing in this section is an example of how to find if a an element in a list (or really anything we can Traverse) matches some predicate…

newtype Mighty = Might{might :: Bool}

instance Monoid Mighty where
 = Might False
Might x  Might y = Might (x  y)

any :: Traversable t  (a  Bool)  t a  Bool
any p = might · accumulate (Might · p)

What’s going on here is that we get a new type called Mighty which has a Monoid instance for it representing disjunction (boolean or). There is no default Monoid for boolean in Cats so we have to define one first.

implicit val mightyBoolean = new Monoid[Boolean] {
  def empty = false
  def combine(a: Boolean, b: Boolean) = a || b
}

Traverse[List].traverse(List(1,2,3,4,5))(a =>
  if(a > 2) Const.of[Any](true)
  else Const.of[Any](false))
// res: Const[Boolean, List[Any]] = Const(true)

Traverse[List].traverse(List(1,2,3,4,5))(a =>
  if(a > 5) Const.of[Any](true)
  else Const.of[Any](false))
// res: Const[Boolean, List[Any]] = Const(false)

Instead of using boolean we can rely on the Integer addition boolean to count how many times a predicate is matched in a traversable structure…

Traverse[List].traverse(List(1,2,3,4,5))(a => if(a > 2) Const.of[Any](1) else Const.of[Any](0))
// res: Const[Int, List[Any]] = Const(3)

Comparing Monad with Applicative

We know that all Monads are Applicatives. Why? Because all Monads implement pure and they can also implement ap as follows…

def ap[A, B](ff: List[A => B])(fa: List[A]) = {
  ff.flatMap(f =>
    fa.map(f))
}

But all Applicatives are not Monads. For example you cannot implement flatMap for Const…

def flatMap[A,B](fa: MyConst[X,A])(f: A => MyConst[X,B]): MyConst[X,B] = {
  val x = fa.unConst
  val a = ???
  // f(a)
  ???
}

We need an A to apply the function f, but there’s no way to get one. Therefore Const is no Monad.

So now we know: there are strictly more Applicative functors than Monads. Should we just throw the Monad class away and use Applicative instead? Of course not! The reason there are fewer monads is just that the Monad structure is more powerful.

Next we contrast how Monad and Applicative differ in terms of a function called miffy (for doing a monadic if) and iffy (an applicative if)…

def miffy[A, F[_]: Monad](mb: F[Boolean], fa: F[A], fb: F[A]): F[A] = {
  mb.flatMap{
    b =>
    if(b) fa
    else fb
  }
}

def iffy[A, F[_]: Applicative](mb: F[Boolean], fa: F[A], fb: F[A]): F[A] = {
  Applicative[F].map3(mb, fa, fb){
    case (cond, a, b) =>
      if(cond) a else b
  }
}

// miffy(Option(true), Option(1), None)
// res: Option[Int] = Some(1)

// iffy(Option(true), Option(1), None)
// res: Option[Int] = None

Here you can see that whilst miffy will succeed if the input is true even though the else effect failed (it was None). But with the applicative version we have to evaluate all the effects first, and if one of them fails they all fail.

The moral is this: if you’ve got an Applicative functor, that’s good; if you’ve also got a Monad, that’s even better! And the dual of the moral is this: if you want a Monad, that’s good; if you only want an Applicative functor, that’s even better!

Composing Applicatives

Not all Monads compose but all Applicatives do; the Applicative class is closed under composition.

instance (Applicative f ,Applicative g)  Applicative (f  g) where
pure x = Comp J (pure x ) K
Comp fs ~ Comp xs = Comp J (~) fs xs K

What does it mean to compose an Applicative? It means that we get the effects of both. For example we can use the full suite of Applicative functionality on a List of Options…

val x: List[Option[Int]] = List(10.some, 9.some, 8.some)
val y: List[Option[Int]] = List(7.some, 6.some, 5.some)

Applicative[List].compose[Option].map2(x, y)(_ + _)
// List[Option[Int]] = List(Some(17), Some(16), Some(15),
//   Some(16), Some(15), Some(14),
//   Some(15), Some(14), Some(13))

Accumulating Exceptions

In this section, it’s noted that we could accumulate errors from computations using a type such as…

data Except err a = OK a | Failed err

You may recognize this as Scala’s Either, which stores with an error or a success in its Left and Right sides.

This could be used to collect errors by using the list monoid (as in unpublished work by Duncan Coutts), or to summarise them in some way.

This is in fact exactly what we did when looking at the Validated type above.

Applicative functors and Arrows

In this section, the paper discusses arrows which have some similarities with the Applicative interface, but it’s out of scope for purposes of this blog post. I may come back to it in a future post.

Applicative functors, categorically

We now see a different, but equivalent way to define the Applicative class. Take a look at this Haskell code…

class Functor f  Monoidal f where
unit :: f ()
(*) :: f a  f b  f (a, b)

This means given a type f with a Functor instance, we can define the class Monoidal. unit is the same as pure, whilst the * function takes two effects and returns a new effect with the result tupled. This is implemented in Cats for Applicative’s and known as product.

Applicative[Option].product(Option(22),Option(20))
// res: Option[(Int, Int)] = Some((22, 20))

Let’s show that we can implement Applicative if we have the product function (assuming product is not implemented in terms of ap)…

override def ap[F[_], A, B](ff: F[A => B])(fa: F[A]) = {
  product(ff,fa).map {
    case (f, a) =>
      f(a)
  }
}

Applicative can be implemented with ap and pure, or pure and product. We’ll see another choice later. Next in this section is some category theory which I’ll also skip for now, leaving only this quote for your interest…

Fans of category theory will recognise the above laws as the properties of a lax monoidal functor for the monoidal structure given by products.

We applied ourselves!

That’s the end of McBride and Patterson’s paper; here are some conclusions they made…

  • Applicative Functors have been identified
  • They lie between Functor and Monad in power
  • Unlike Monads, Applicatives are closed under composition
  • Traverable Functors thread Applicative Applications and form a useful toolkit

The paper ends with a great quote that is both positive about borrowing ideas from category theory…

The explosion of categorical structure in functional programming: monads, comonads, arrows and now applicative functors should not, we suggest, be a cause for alarm. Why should we not profit from whatever structure we can sniff out, abstract and re-use? The challenge is to avoid a chaotic proliferation of peculiar and incompatible notations.

Plug for idiom brackets was snipped.

Back to Ap

So far in this post, we’ve seen lots of code that uses ap in various ways. We’ll wrap it up with some implementation notes on the useful function map2, and how we can arrive at needing the ap function to do so. Then we’ll look at a practical example of using Applicative in image processing.

Let’s start with a problem. We have two functions that return IO’s as output. We want to call a pure function that takes two values as input. In short we need map2…

case class User(email: String, name: String, blocked: Boolean)
case class Account(email: String, balance: Long)

def getUser(email: String) =
  IO.sleep(10 seconds) *> IO(User("bob@gmail.com", "Bob Jones", false))

def getAccount(email: String) =
  IO.sleep(10 seconds) *> IO(Account("bob@gmail.com", 100))

def goodStanding(user: User, account: Account): Boolean = {
  user.blocked == false &&
  account.balance >= 0
}

val email = "bob@gmail.com"

val checkBob = Applicative[IO.Par].map2(
  Par(getUser(email)),
  Par(getAccount(email)))(goodStanding)

println("run bank check: " + Par.unwrap(checkBob).unsafeRunSync)
// run bank check: true

So this motivating example works, it runs the (simulated) slow network calls in parallel and passes them to our function. (Note that this example is using Cats Effect and in order to select Applicative rather than Monadic operation we need to wrap the IO in the Par wrapper and then unwrap it at the end).

Given that map2 is a useful function how would we implement it? Just like we saw at the start of the paper, we can use flatMap and map to implement it quite easily…

def map2[A,B,C,F[_]: Monad](fa: F[A], fb: F[B])(f: (A,B) => C): F[C] =
  fa.flatMap { a =>
    fb.map(b => f(a,b))
  }

That works fine, but sadly it requires that we complete fa before starting and we want to allow independent effects. So we can’t use Monad’s flatMap. Let’s build the function without it…

def applicativeMap2[A,B,C,F[_]: Applicative](fa: F[A], fb: F[B])(f: (A,B) => C)
    : F[C] = {
  val ffb = fa.map {
    a => (b: B) => f(a,b)
  }
  Applicative[F].ap(ffb)(fb)
}

Obviously, there’s no need to implement map2 because the Applicative instances already have it, but it helps understand further the motivation for ap. The value ffb is actually the result of currying the function f. What we get back is of the form F[B => C]. We can then call that function using Applicative’s ap giving the correct response F[C].

By successively currying we can use the same trick to write map3, map4 and so on.

Map2… does it blend?

So far we’ve seen some interesting uses of Applicative; accumulating errors from network calls, managing multiple concurrent effects, transposing matrices, evaluating expressions. In 2019 I wrote a blog post about Comonads that used the coflatMap operation to do image processing. One of the takeaways from that post is that one of the great advantages of functional programming is composability. One thing I’d like to be able to do is to do operations on two images then blend them together. In my original code images are stored represented as a FocusedGrid which is just an array of pixels and a focus point, which works nicely for the coflatMap. The blend operation just needs a function to average out the pixels and a map2…

def blend(a: (Int, Int, Int), b: (Int, Int, Int)): (Int, Int, Int) =
  ((a._1 + b._1) / 2, (a._2 + b._2) / 2, (a._3 + b._3) / 2)

val leftImage = originalImage2
val rightImage = originalImage2.coflatMap(mirrorHorizontal)
val upImage = originalImage2.coflatMap(mirrorVertical)
val downImage = rightImage.coflatMap(mirrorVertical)

val leftAndRight = Applicative[FocusedGrid].map2(leftImage, rightImage)(blend _)
val upAndDown = Applicative[FocusedGrid].map2(upImage, downImage)(
val finalImage = leftAndRight.map2(upAndDown)(blend _))

These few lines are all that is needed in user code to create the cows image at the top of this post. If you want to know what the coflatMap is all about please checkout my earlier post Comonads for Life or the related talk at Scale by the Bay 2020 A gentle introduction to comonads.

But in the background we also need to implement an Applicative instance for the FocusedGrid datatype. Let’s start with pure…

def pure[A](a: A): FocusedGrid[A] = FocusedGrid((0,0), Vector(Vector(a)))

Just like with the pure function for a List Applicative (or Monad), all we do is lift a pure value into a FocusedGrid with a singe row and column.

def ap[A, B](ff: FocusedGrid[A => B])(fa: FocusedGrid[A]): FocusedGrid[B] = {
  val newGrid = ff.grid.mapWithIndex {
    (row, i) =>
    row.zip(fa.grid(i)).map {
      case (f, a) =>
        f(a)
    }
  }
  FocusedGrid(ff.focus, newGrid)
}

Remember that with List we implemented an Applicative instance that took all the functions in the input list and applied them in turn to each element in the list of parameters. Ap for FocusedGrid iterates over a grid of functions and applies them to the target row and column in the input parameter.

Our work is done; with pure and ap implemented we now have a fully working Applicative instance and that means map2 will work.

Post-mature optimisation

Most of the time, solving day to day business problems, we don’t have to worry to much about performance, but when it comes to things like image processing when we are dealing with large numbers of pixels it can be more important to know what is going on under the hood, and when to step in and improve it. Profiling should be your guide, but if you look at the default implementation of map2 in Cats you can see that it is doing a lot of work that is not needed …

map(product(fa, fb))(f.tupled)

And product is …

ap(map(fa)(a => (b: B) => (a, b)))(fb)

So with a square image of size 2000 pixels (4 million total), to perform a map2 we are going to map of the image twice; once to create an image of curried functions and a second time to apply them. In addition, we’re going to create a lot temporary data that we don’t need.

Fortunately there’s nothing to stop you from instead of using the default implementation of map2 we can implement our own…

override def map2[A, B, Z](fa: FocusedGrid[A], fb: FocusedGrid[B])(f: (A, B) => Z): FocusedGrid[Z] = {
  val faRowIter = fa.grid.iterator
  val fbRowIter = fb.grid.iterator
  val rowBuilder = Vector.newBuilder[Vector[Z]]

  while(faRowIter.hasNext && fbRowIter.hasNext) {
    val faColIter = faRowIter.next.iterator
    val fbColIter = fbRowIter.next.iterator
    val colBuilder = Vector.newBuilder[Z]

    while(faColIter.hasNext && fbColIter.hasNext) {
      colBuilder.addOne(f(faColIter.next, fbColIter.next))
    }
    rowBuilder.addOne(colBuilder.result)
  }
  FocusedGrid(fa.focus, rowBuilder.result)
}

Here we make a much more efficient implementation that instead of creating temporary data structures will use an iterator on each input grid and a Vector builder to efficiently build the output. This is maybe not the fastest implementation but it’s certainly doing a lot less work. Of course optimizing without profiling is a waste of time. I had heard that Array is much faster than Vector for this kind of use case, so the sample code also includes an Array implementation. The code is somewhat ugly due to some technical constraints around Array, and turned out not to be any faster!

In any case, should you want to explore this further, the instructions are all in the accompanying code to do you run your own benchmarks using jmh.

Here’s the results from my own benchmarking…

Benchmark Mode Cnt Score Error Units  
FocusedGridArrayBench.withMap2Large avgt 5 171099.587 ± 65471.687 us/op
FocusedGridArrayBench.withMap2Small avgt 5 54.418 ± 25.669 us/op
FocusedGridBench.withMap2Large avgt 5 152831.655 ± 40709.521 us/op
FocusedGridBench.withMap2Small avgt 5 59.168 ± 15.346 us/op
FocusedGridBench.withSlowApLarge avgt 5 649442.291 ± 215248.298 us/op
FocusedGridBench.withSlowApSmall avgt 5 141.025 ± 78.928 us/op

What is notable that optimized map2 is 4x faster on the large image than slowAp and the array version is actually slower than the vector version. Just goes to show, if performance matters then always benchmark your original code and your solution to make sure your assumptions are correct. There’s also a balance between opimised code keeping your code easy to read and reason about.

Conclusion

You made it to the end! Congratulations, and I hope it made sense. Please feel free to contact me if you have any notes, corrections, improvements or suggestions!

This post was going to be a five-minute thing but blew up into a monster and there are still things that I didn’t get to. Some things I may visit in the future:

  • Composition - examples of composing Functors and Applicatives
  • Arrows
  • Laws of Applicatives (although they are covered nicely elsewhere)
  • Category theory (esp. of lax monoidal functors in more depth)

References

Code

  • applicatives (Scala conversion from the paper and lots of Applicative stuff)
  • comonad (Image processing example with new Applicative demo)
  • Scala Benchmarks (How to benchmark Scala by Colin Woodbury)
  • Idiom Ears (Get those fancy ears in your applicative programming)
  • Scala Workflow (A full on system for Monadic and Applicative programming)

Acknowledgements

  • Thank you to the welcoming members of the Scala community who generously share their knowledge and libraries
  • Thank you to Hermann Hueck for his suggestions and improvements on this post

© 2020 Justin Heyes-Jones. All Rights Reserved.