What's Ap?

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.

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.

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.

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

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)

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.

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)

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))

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.

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.