Free Applicative and Free Monad

The aim of this blog is to walk through a proper end to end example of a multi domain Free program that combines both sequential and parallel operations. Skip to the section Lets Write our Program if you are already familiar with Applicative and FreeAp.

It is assumed you are familiar with the Free Monad and the benefits of functional programming. If not, please refer to my previous blog which introduces the Free Monad and has many links to much more detailed explanations.

For reference – my github gist has a full working copy of the code here.

Recap on Applicatives

At a high level, the Free Monad gives us the power to express our programs as a sequence of instructions that we can interpret at a later time. The key word here being sequential.

Monads are defined as:

trait Monad[F[_]] {
  def point[A](a: A): F[A]
  def flatMap[A, B](a: F[A])(f: A => F[B]): F[B]
}

The part to notice here is the flatMap. See how in the function f, in order to produce an F[B] we actually need an A first? This is what forces a monad to run sequentially.

The Free Applicative on the other hand is modelled off Applicative Functors and as such allows us to run multiple computations independent of one another.

If we take a look at the definition of applicatives this becomes clear:

trait Applicative[F[_]] {
  def point[A](a: A): F[A]
  def ap[A, B](fa: => F[A])(f: => F[A => B]): F[B]
}

As you can see, the method ap is what is used to apply a function A=>B in the context of F to a value A in the context of F.

In practice this might mean if we had the following:

scala> val f = Option((i: Int) => i.toString)
f: Option[Int => String] = Some($$Lambda$4986/1160677632@6bbe795e)

scala> val fa = Option(4)
fa: Option[Int] = Some(4)

We could apply the function contained in f to the value contained
in fa and end up with a String with value "4".
In this case the F context is Option.

It’s not immediately clear how this lets us run things in parallel.

If you look at the function ap2 in scalaz, you begin to see how this ap function gives us the power or running many things together without them depending on one another.

trait Applicative[F[_]] {
  // point and ap omitted here
  def ap2[A,B,C](fa: => F[A], fb: => F[B])(f: F[(A,B) => C]): F[C]
}

Here we can see that given an F[A] and an F[B] as well as a function that can combine (A, B) into C, we can produce an F[C]. There is no mention of needing any of them to be run in any particular order.

This is implemented in terms of our ap function we saw earlier and lets us express things like:

scala> val fa = Option(4)
fa: Option[Int] = Some(4)

scala> val fb = Option(5)
fb: Option[Int] = Some(5)

scala> val f = Option((i: Int, j: Int) => (i + j).toString)
f: Option[(Int, Int) => String] = Some($$Lambda$4987/1898967014@6b28dafd)

scala> ap2(fa, fb)(f)
res0: Option[String] = Some(9)

Using the same technique we can generalise to running any number of independent of one another.

This becomes really interesting when we execute this in parallel.

Effects such as Future and Task have this ability out of the box and are a great choice for running Async Parallel tasks.

Quick Overview of FreeAp

FreeAp is the scalaz implementation of Free Applicative. In terms of structure of use it is essentially the same as the Free Monad in that you:
– Define your operations
– Lift them into the Free Applicative
– Write your program as a combination of FreeAp instructions
– Write your interpreters
– Execute your program by running your interpreters over you FreeAp instructions

As previously discussed, the problem with the above approach is that we then only get parallel computations and cannot enforce the concept of sequential ordering (which almost all programs want).

As such, we will dive into a simplified real world example of wanting to do things in sequence and in parallel.

Defining our domain

As usual we start by defining a domain. Lets create a User domain and an Analytics domain.

case class User(name: String, age: Int)

sealed trait UserOperation[T]
case class CreateUser(name: String, age: Int) extends UserOperation[User]

sealed trait AnalyticsOperation[T]
case class AnalyseUser(user: User) extends AnalyticsOperation[Int]

Pretty standard stuff so far.

Next, lets lift our operations into the Free Monad and Free Applicative:

// This is a little convenience trait that reduces boilerplate of defining the
// sequential and parallel version for every operation
case class ExecStrategy[F[_], A](fa: F[A]) {
  val seq: Free[F, A] = Free.liftF(fa)
  val par: FreeAp[F, A] = FreeAp.lift(fa)
}

// Lift our operations into the Free contexts
case class UserRepo[F[_]](implicit ev: Inject[UserOperation, F]) {
  def createUser(name: String, age: Int): ExecStrategy[F, User] =
    ExecStrategy[F, User](ev.inj(CreateUser(name, age)))
}

object UserRepo {
  implicit def toUserRepo[F[_]](implicit ev: Inject[UserOperation, F]): UserRepo[F] = new UserRepo[F]()
}

case class AnalyticsRepo[F[_]](implicit ev: Inject[AnalyticsOperation, F]) {
  def analyseUser(user: User): ExecStrategy[F, Int] =
    ExecStrategy[F, Int](ev.inj(AnalyseUser(user)))
}

object AnalyticsRepo {
  implicit def toAnalyticsRepo[F[_]](implicit ev: Inject[AnalyticsOperation, F]): AnalyticsRepo[F] = new AnalyticsRepo[F]()
}

A few things to note at this point:
– The ExecStrategy is an idea I’m messing around with to avoid needing to define every operation twice in your Repos. You do not need to use it if you prefer not to.
– We use the Inject typeclass to allow us to take any operation of type UserOperation and convert it into the type F.
– Finally we provide some implicits to allow us to construct our instances à la carte.

We now have the ability to write some programs in terms of Free and FreeAp.

Combining Free and FreeAp

There are many ways to combine these two abstractions but I will talk through a fairly powerful and general purpose approach.

type Program[F[_], A] = Free[FreeAp[F, ?], A]

This effectively gives us a Free Monad where the effect type is actually a Free Applicative. What this means in practice is that our program is comprised of a sequence of steps where each step has one (or more) parallel computations (embedded in the FreeApplicative).

Now we use this in the following way:
– Sequential operations are simply a FreeAp with a single instruction which is then embedded in the top level free monad.
– Parallel operations are also just a FreeAp but have more than one instruction. This is also then embedded in the top level free monad.

As can be seen all operations live in the same nested level of the Program structure regardless of whether they’re parallel or sequential. The FreeAp container determines how many operations get executed in a single step of the Free Monad.

Now we just need to lift each of our Free or FreeAp operations into the Program structure. For a Free instruction this simply means embedding the single instruction in a nested FreeAp. For a FreeAp instruction, this just means lifting it into Free. Lets see what those definitions might look like:

object ProgramHelpers {
  implicit class RichFree[F[_], A](free: Free[F, A]) {
    def asProgramStep: Program[F, A] = {
      free.foldMap[Program[F, ?]](new NaturalTransformation[F, Program[F, ?]] {
        override def apply[A](fa: F[A]): Program[F, A] = liftFA(fa)
      })(Free.freeMonad[FreeAp[F, ?]])
    }
  }

  implicit class RichFreeAp[F[_], A](freeap: FreeAp[F, A]) {
    def asProgramStep: Program[F, A] = Free.liftF[FreeAp[F, ?], A](freeap)
  }

  def liftFA[F[_], A](fa: F[A]): Program[F, A] =
    Free.liftF[FreeAp[F, ?], A](FreeAp.lift(fa))
}

We define these as implicit classes to make our dsl cleaner to follow.

With this we are ready to define a program using both Free and FreeAp together. Lets start with a simple program that creates two users in sequence then analyses them in parallel:

def program[F[_]](implicit userRepo: UserRepo[F],
                  analyticsRepo: AnalyticsRepo[F]): Program[F, Int] = {
  for {
    user1 <- userRepo.createUser("steve", 23).seq.asProgramStep
    user2 <- userRepo.createUser("harriet", 33).seq.asProgramStep
    sumOfAnalytics <- (analyticsRepo.analyseUser(user1).par |@| analyticsRepo.analyseUser(user2).par)((a, b) => a + b).asProgramStep
  } yield sumOfAnalytics
}

And another example that creates users in parallel and also analyses them in parallel:

def program2[F[_]](implicit userRepo: UserRepo[F],
                   analyticsRepo: AnalyticsRepo[F]): Program[F, Int] = {
  for {
    users <- (userRepo.createUser("steve", 23).par |@| userRepo.createUser("harriet", 33).par)((u1, u2) => (u1, u2)).asProgramStep
    (user1, user2) <- users
    sumOfAnalytics <- (analyticsRepo.analyseUser(user1).par |@| analyticsRepo.analyseUser(user2).par)((a, b) => a + b).asProgramStep
  } yield sumOfAnalytics
}

As we can see – each operation is created as either a sequential operation (Free) or as a parallel operation (FreeAp) and is then subsequently lifted into our combined Program structure. Note that we combine our parallel steps using applicative syntax |@| as usual.

Interpreting the Program

As with Free Monads, we need to define interpreters for each of our domains and then interpret the above program with these interpreters.

Lets define some simple implementations with timeouts so that we can confirm our
domain is running the right steps in parallel as expected.

case class SlowUserInterpreter(delay: Long) extends (UserOperation ~> Task) {
  override def apply[A](fa: UserOperation[A]): Task[A] = fa match {
    case CreateUser(name, age) =>
      Task {
        println(s"Creating user $name")
        Thread.sleep(delay)
        println(s"Finished creating user $name")
        User(name, age)
      }
  }
}

case class SlowAnalyticsInterpreter(delay: Long) extends (AnalyticsOperation ~> Task) {
  override def apply[A](fa: AnalyticsOperation[A]): Task[A] = fa match {
    case AnalyseUser(user) =>
      Task {
        println(s"Analysing user $user")
        Thread.sleep(delay)
        println(s"Finished analysing user $user")
        if (user.name == "steve") 50 else 20
      }
  }
}

In order to interpret our various domain algebras, we need a way to label each step as its specific domain such that the correct interpreter can be used. This is typically solved with Coproducts. e.g.

type ProgramInstructions[A] = Coproduct[UserOperation, AnalyticsOperation, A]

This is simply saying “for each step in our program, we either have a UserOperation or an AnalyticsOperation“. This is implemented using disjunctions in scalaz. The simplest way to visualise what is happening here is for each operation we either go Left or Right based on its type. Left leads us to UserOperation and right leads us to AnalyticsOperation. If you have more than two domain algebras, you simply nest further so that right is just another Coproduct. Keep in mind that every new domain algebra you add will incur the cost of traversing this tree of Coproduct to find the correct interpreter. If this becomes an issue for your project, there are libraries out there such as
iota which provide constant time lookups for arbitrarily large lists of instruction sets.

Now we need to define the following interpreter in order to interpret our program that was defined earlier:

val programInterpreter: ProgramInstructions ~>Task = ???

As discussed, we need to define a way to find the correct interpreter for an instruction set given the Coproduct. Here are a few simple helpers to allow us to do so:

object InterpreterHelpers {
  def combineInterpreters[F[_], G[_], H[_]](f: F ~> H, g: G ~> H): Coproduct[F, G, ?] ~> H =
    new (Coproduct[F, G, ?] ~> H) {
      override def apply[A](fa: Coproduct[F, G, A]): H[A] = fa.run match {
        case -\/(ff) => f(ff)
        case \/-(gg) => g(gg)
      }
    }

  implicit class RichNaturalTransformation[F[_], H[_]](val f: F ~> H) {
    def or[G[_]](g: G ~> H): Coproduct[F, G, ?] ~> H = combineInterpreters[F, G, H](f, g)
  }
}

This now allows us to combine interpreters using or (much like in cats).

Now we are almost there. The last issue we need to solve is that our program doesn’t actually require an interpreter of the form ProgramInstructions ~>Task. This is because we actually embedded our FreeAp in the Free instruction slot. As such, we actually need to transform a FreeAp into a Task, i.e.
FreeAp[ProgramInstruction, ?] ~>Task. To do this, we define a helper class:

case class ParallelInterpreter[G[_]](f: ProgramInstructions ~> G)(implicit ev: Applicative[G]) extends (FreeAp[ProgramInstructions, ?] ~> G) {
  override def apply[A](fa: FreeAp[ProgramInstructions, A]): G[A] = fa.foldMap(f)
}

As can be seen, given our known interpreter stack (ProgramInstructions ~>Task) this produces a way to go from FreeAp[ProgramInstruction, ?] ~>Task as required.

Now we have all the machinery we need to run our program:

import InterpreterHelpers._
val programInterpreter: ProgramInstructions ~> Task = SlowUserInterpreter(delay = 5000) or SlowAnalyticsInterpreter(delay = 2000)
program[ProgramInstructions].foldMap(ParallelInterpreter(programInterpreter)).unsafePerformSync

This will construct an interpreter which is the Coproduct of our two individual interpreters where the User creation will take 5 seconds and the analysing of a single user will take 2 seconds.

If we recall, our program created two users in sequence then analysed them both in parallel. As such we expect this program to run in ~12 seconds.

If you try this yourself you will find that it actually takes closer to 14 seconds.

Wait. What gives?!

Well if we take a close look at how this is being executed, we actually don’t explicitly run anything in parallel. We defer that to the Applicative instance of our target Applicative. In this case it is Applicative[Task]. If you look at the applicative instance provided out of the box for Task, you will see that its actually a sequential implementation as it is derived form the Monad[Task] instance which is necessarily sequential.

Task actually provides a parallel implementation called Task.taskParallelApplicativeInstance which is actually a Task that has been tagged as Parallel and must be explicitly used in place of Task. I find this to be a bit tedious and simply opted to define my own applicative instance for task to keep things simple for now. (Thanks to pchiusano for the example).

val parallelTaskApplicative = new Applicative[Task] {
  def point[A](a: => A) = Task.now(a)
  def ap[A,B](a: => Task[A])(f: => Task[A => B]): Task[B] = apply2(f,a)(_(_))
  override def apply2[A,B,C](a: => Task[A], b: => Task[B])(f: (A,B) => C): Task[C] =
    Nondeterminism[Task].mapBoth(a, b)(f)
}

Now we simply run our program from before passing in the parallel applicative for Task and our program runs in 12 seconds as expected!

val programInterpreter: ProgramInstructions ~> Task = SlowUserInterpreter(delay = 5000) or SlowAnalyticsInterpreter(delay = 2000)
program[ProgramInstructions].foldMap(ParallelInterpreter(programInterpreter)(parallelTaskApplicative)).unsafePerformSync

And voila! Our program can now run both sequential AND parallel operations in a single Free Structure.

Closing Thoughts

Once the boilerplate has been set up, this is a really clean and powerful way to express programs. I personally really like expressing programs with these constructs as it helps you to focus on clean domain design due to the clear separation of domain from effects.

I’d also highly recommend you to take a look at the following talks by John de Goes as they helped me better understand the details of some of this stuff:
– Beyond Free Monads
– Move Over Free Monads: Make Way for Free Applicatives

Its also worth noting that there is a library called Freestyle which automated away a lot of this boilerplate however comes at the cost of code generation via macros – which I personally find harder to use in the development cycle.

Free vs. Finally Tagless

1. The Path to Finally Tagless

When modelling a domain, most people are probably quite
familiar with code that looks something like this:

trait UserRepository {
  def createUser(name: String, age: Int): User
  def getUserById(id: String): Option[User]
  def listUsers(): List[User]
}

A common pattern is to create subclasses of this UserRepository
trait with concrete implementations.

class MyUserRepository() extends UserRepository {
  def createUser(name: String, age: Int): User = ???
  def getUserById(id: String): Option[User] = ???
  def listUsers(): List[User] = ???
}

Pretty quickly we decide that we want our user repository to be
backed by a database. The moment we do this, we realise that
things can fail (e.g. network problems, database constraints etc).

As such, being well behaved programmers, we model this failure
with something like Either (I’ll use Throwable as the error for now
but you should use a sealed ADT of the domain errors in practice).

trait UserRepository {
  def createUser(name: String, age: Int): Either[Throwable, User]
  def getUserById(id: String): Either[Throwable, Option[User]]
  def listUsers(): Either[Throwable, List[User]]
}

Now we can subclass the UserRepository with something that can
hit the database and return either our result or the failures
explicitly.

The next thing we realise is that this is a really slow way to
talk to a database. We don’t want to block threads while we wait
for the response. Futures to the rescue.

trait UserRepository {
  def createUser(name: String, age: Int): Future[Either[Throwable, User]]
  def getUserById(id: String): Future[Either[Throwable, Option[User]]]
  def listUsers(): Future[Either[Throwable, List[User]]]
}

Bleargh.

There are a few problems with this. First of all we now have a stack
of monads which makes working with this type quite ugly.
Monad Transformers can solve this problem (but we won’t delve into those right now)
as there is an even bigger problem staring us right in the face.

We just changed our base domain trait to be aware of the fact
that its subclass can deal with errors and asynchronous effects.

This should be ringing alarm bells in that “good design” part of
your brains right now.

Lets try and abstract out this tight coupling of effect from domain.

trait UserRepository[F[_]] {
  def createUser(name: String, age: Int): F[User]
  def getUserById(id: String): F[Option[User]]
  def listUsers(): F[List[User]]
}

Ah much nicer. Now our base trait simply acknowledges that there
is some effect F without actually specifying what that effect is.
Our base domain is once again pure from implementation details.

Now we are free to write our subclasses and make those effectful
concerns concrete at the time of subclassing e.g.

trait FutureUserRepository extends UserRepository[Future] {
  def createUser(name: String, age: Int): Future[User] = ???
  def getUserById(id: String): Future[Option[User]] = ???
  def listUsers(): Future[List[User]] = ???
}

We have successfully decoupled the domain from the effects of
implementing the domain.

This representation is called finally tagless.

2. The Free Representation

The free monad is very similar to finally tagless in a lot of ways.
It allows us to encode our domain completely decoupled from
the effects of implementation using a slightly different encoding.

It also allows us to interpret our programs independent of their
definitions (though it uses Natural Transformations rather than
subclassing to achieve this).

When we create free programs, we describe each of our domain operations
as data rather than methods. We then lift each of these operations
into the Free context as instructions and use these instructions
to create our programs. We then write interpreters to turn these
instructions into actual effects – effectively decoupling our
domain from its effects.

Here is a simple example of our above code:

// Our Domain Algebra (Domain Operations)
sealed trait UserOperation[T]
case class CreateUser(name: String, age: Int) extends UserOperation[User]
case class GetUserById(id: String) extends UserOperation[Option[User]]
case class ListUsers() extends UserOperation[List[User]]

// Lifting out operations into the Free Context as "instructions"
object UserRepository {
  import scalaz.Free 

  def createUser(name: String, age: Int): Free[UserOperation, User] = 
    Free.liftF(CreateUser(name, age))

  def getUserById(id: String): Free[UserOperation, Option[User]] = 
      Free.liftF(GetUserById(id: String))

  def listUsers(): Free[UserOperation, List[User]] = 
      Free.liftF(ListUsers())
}

// Writing out interpreter to turn the data into effects
object FutureUserRepoInterpreter extends (UserOperation ~> Future) {
  override def apply[A](fa: UserOperation[A]): Future[A] = fa match {
    case CreateUser(name: String, age: Int) => ???
    case GetUserById(id: String) => ???
    case ListUsers() => ???
  }
}

We can then write our program without any effects and interpret
it with our effectful interpreters:

val program = for {
  user1 <- UserRepository.createUser("Jerry", 38)
  allUsers <- UserRepository.listUsers()
} (user1, allUsers)

val result = program.foldMap(FutureUserRepoInterpreter)
// result: Future[(User, List[User])]

Delving beyond a basic example of Free is beyond the scope of this
blog. There are many good writeups on the details of implementing a
program with the free monad such as:
– http://underscore.io/blog/posts/2017/03/29/free-inject.html
– http://underscore.io/blog/posts/2015/04/14/free-monads-are-simple.html
– https://blog.scalac.io/2016/06/02/overview-of-free-monad-in-cats.html
– http://typelevel.org/cats/datatypes/freemonad.html
– http://perevillega.com/understanding-free-monads

Free vs. Finally Tagless

Both of the Free Monad and Finally Tagless are based off the interpreter pattern
as you are effectively building a dsl of operations and deferring
the interpretation until later. In the case of finally tagless
this happens when we create concrete subclasses. With the free monad
this happens when we run our interpreter across our program.

There are several differences between the two representations
but the primary one is that the free monad reifies our dsl.
Put simply our program instructions become data. Our programs
simply become a list of data (case classes lifted into the Free context)
that we are free (no pun intended) to interpret however we want.
In this way it is a very powerful and elegant abstraction.

The price we pay for this abstraction is that we actually have
to pass over our program an instruction at a time and interpret it.
For performance sensitive code this may be unacceptable however,
many programs are constrained by IO rather than application code
so this concern is not worth worrying too much about. As always,
if performance matters, measure before you optimise!

Whats Next?

Once you become more familiar with the Free Monad and start to use
it in anger you will very likely run into some issues. The biggest
one is that it is by nature – a monad. For starters, this means
that it is necessarily sequential in its usage. Often we
want a less specific abstraction such as an applicative which
would let us run operations in parallel.

The next article will look at the Free Applicative and delve into
how we can combine it with the Free Monad to allow us to express
both sequential and parallel programs in a single structure.

Monads and scalaz – What, When, Why and How? (Part 2 – The Writer Monad)

This is part 2 of a multipart blog series on a bunch of useful monads that
scalaz offers that the scala standard library doesn’t have.

It is assumed that you have read part 1 for this blog. You can find it here if you haven’t checked it out yet.

Now for the next exhilarating installment…

Writer

What

The Writer monad is effectively a wrapper around a tuple

(W, A)

Put simply, it is a way to return a value A along with some extra written information. W typically stands for the written value and A stands for the result.

In scalaz it is Writer[W, A] and is actually a type alias for WriterT[Id.Id, W, A] but we won’t concern ourselves with what that means until the blog on monad transformers.

I have found that a nice intuition for this monad is to imagine it is a log W attached to a value A. If we assume that W can be combined, then we can work with the value A like we always would have, and combine our W value as we go. We will see the details of how this works shortly.

Why

Much like the motivation for the state monad, we want to avoid side effects in our code. Lets consider the standard writer example of logging.

def add(a: Int, b: Int): Int = {
  println(s"Adding $a and $b")
  a + b
}

def multiply(a: Int, b: Int): Int = {
  println(s"Multiplying $a and $b")
  a * b
}

multiply(add(3, 4), 6)  // Also triggers two println side effects
// res0: Int = 42

We want to be able to capture these side effects explicitly and handle them rather than compose our program out of side effecting functions.

If we try this naively we might get the following

def add(a: Int, b: Int): (String, Int) = {
  (s"Adding $a and $b", a + b)
}

def multiply(a: Int, b: Int): (String, Int) = {
  (s"Multiplying $a and $b", a * b)
}

multiply(add(3, 4), 6)    // Does not compile

// We are forced to do the following kind of thing
val (w1, a1) = add(3, 4)
// w1: String = Adding 3 and 4
// a1: Int = 7
val (w2, a2) = multiply(a1, 6)
// w2: String = Multiplying 7 and 6
// a2: Int = 42

// Do something with w1 and w2

This is an improvement since our functions add and multiply no longer contain side effects, however dealing with these functions is no longer very nice. What would be great is if we had a way to accumulate those w1, w2 values whilst only worrying about working with the a1, a2 values.

In comes the writer monad.

How

Since the writer monad effectively acts as a wrapper for (W, A) our simple math functions fit the bill perfectly.

We can rewrite the above as

import scalaz._
import Scalaz._

def add(a: Int, b: Int): Writer[String, Int] = {
  (a + b).set(s"Adding $a and $b")
}

def multiply(a: Int, b: Int): Writer[String, Int] = {
  (a * b).set(s"Multiplying $a and $b")
}

val res0 = for {
  x <- add(3, 4)
  y <- multiply(x, 6)
} yield y
// res0: Writer[String,Int] = Writer((Adding 3 and 4Multiplying 7 and 6,42))

res0.written
// res1: String = Adding 3 and 4Multiplying 7 and 6
res0.value
// res2: Int = 42

There is a lot going on here so lets have a look.

Firstly we have rewritten our method signatures to contain the writer monad: Writer[String, Int]. As we said before, lets think of this as simply being a wrapper around a tuple (W, A) which in this case is (String, Int).

We constructed this writer using set. Set simply takes a value for the left side of the tuple W and writes it next to the value you call it on. So in the case of add it is creating a tuple (s"Adding $a and $b", a + b).

It may not seem immediately obvious why this is better than just a straight tuple, but if we look at the for comprehension, we see something quite interesting. Much like our State monad, we only have to worry about the value we care about. In this case that is the A value. Our W value is dealt with as part of the flatmap/map/filter chains inside the for comprehension.

But how is W being “dealt with”?

To answer this question properly, we need to understand what a Semigroup is. Put simply, it is something that is combineable with other values of the same type.

e.g.
– An int semigroup for addition would have a combine of _ + _.
– An int semigroup for multiplication would have a combine of _ * _.

(This is a simplification to aid understanding. If you want to understand the details, refer to my previous blog).

When we have a combinable value for W, we can safely let our flatmaps combine them. So if our W type was Int and we provided an implicit evidence for the Semigroup[Int] implemented as the addition described above, our W values would simply add together. If we instead provided the implicit envidence for Semigroup[Int] as multiplication, we would get W as the product of the logs.

import scalaz._
import Scalaz._

implicit def intAdditionEv = new Semigroup[Int] {
  override def append(f1: Int, f2: => Int): Int = f1 + f2
}

val v1: Writer[Int, String] = "value 1".set(5)
val v2: Writer[Int, String] = "value 2".set(6)

v1.flatMap(x =>
  v2.map(y => x + y)
)(implicitly[Bind[Id.Id]], intAdditionEv)
// res0: Writer[Int, String] = (11,value 1value 2)

// This is the same as the following for comprehension (since scalaz already
// provides the addition semigroup.
for {
  x <- v1
  y <- v2
} yield x + y
// res1: Writer[Int, String] = (11,value 1value 2)

// If we want to explicitly force it to use our new multiplication semigroup,
// we need to directly provide it

implicit def intMultiplicationEv = new Semigroup[Int] {
  override def append(f1: Int, f2: => Int): Int = f1 * f2
}

v1.flatMap(x =>
  v2.map(y => x + y)
)(implicitly[Bind[Id.Id]], intMultiplicationEv)
// res2: Writer[Int, String] = (30,value 1value 2)

Finally we can run our monad just like the state and it will return our (W, A) tuple. We can alternatively access the written value or the value by calling written and value respectively.

When

Even though it is essentially a restricted version of the state monad, it should be preferred when it is powerful enough to do the job at hand. In general you should use the least general abstraction necessary and this fits a lot of problems quite nicely.

The most common usage of the Writer monad that I am familiar with is for logging as we showed above. There are more sophisticated ways of doing this than simply returning a String (or more commonly List[String] or Vector[String]) such as treelog.

In our final example, we also saw that it can be used with any type so long as we know how we want to combine the values. We could for example update our wallet as we spend money with its new total Writer[Total, Unit].

We can use it in general to catch side effects that can be combined.

Much like any other abstractions, it is simply another tool to get the job done. Becoming familiar with it will provide a good intuition for when a problem would be better solved with the Writer monad.

Stay tuned for part 3 on the Reader monad.

Monads and scalaz – What, When, Why and How? (Part 1 – The State Monad)

This is part 1 of a multipart blog series on a bunch of useful monads that
scalaz offers that the scala standard library doesn’t have. I found some of
these concepts quite hard to learn initially because there isn’t much
clear content explaining the what, when, why and how. In this series I will
attempt to remedy this and help to demystify these monads and help you
understand where they can be applied, rather than just what they are.

I will finish the series with an example that pieces all these parts together
so you can see how using these monads in reality actually looks.

This series assumes that you are familiar with the basics of monads and the
scala language.

Now without further ado…

The State Monad

What

The state monad is a simple wrapper around the following function:

S => (S, A)

In short, given some state S1, it produces a new state S2 along with a
value A associated with the state change.

In scalaz you use it as State[S, A] which is simply a monad that wraps
the above behaviour.

Why

In order to see why we would bother using this, lets consider how we
might typically deal with mutable state. As a simple example to illustrate
the concepts, say we have a Generator that simply generates a
new Int every time a function is called.

case class Generator(private var seed: Int) {
  def generateRandomInt(): Int = {
    val rand = seed + 5
    seed = seed + 1
    rand
  }
}

val gen = Generator(30)
gen.generateRandomInt()
// res0: Int = 36
gen.generateRandomInt()
// res1: Int = 37
gen.generateRandomInt()
// res2: Int = 38

This all looks quite simple, however every time you call the
function generateRandomInt(), you get a different value. Calling the
same function with the same value and getting a different result every time
not only breaks referential transparency of that function, but it also means
our code is harder to reason about since we need to know the state of an object
to know what it is going to do.

So how can we improve this situation?

If we follow common functional programming wisdom, we would know that we should
create a new object every time something changes to maintain immutability.
In the above example, we might consider doing this by returning a new
Generator that has a different internal state, along with the value
it produced.

case class Generator(private val seed: Int) {
  def generateRandomInt(): (Generator, Int) = {
    (Generator(seed + 1), seed + 5)
  }
}

val g = Generator(30)
val (g2, res0) = g.generateRandomInt()
// g2: Generator = Generator(31)
// res0: Int = 35
val (g3, res1) = g2.generateRandomInt()
// g3: Generator = Generator(32)
// res1: Int = 36
val (g4, res2) = g3.generateRandomInt()
// g4: Generator = Generator(33)
// res2: Int = 37

What have we done here?

As you can see, we have removed the internal state of the Generator. It now
always returns the same value no matter how many times we call it. We only
have two issues left to deal with.

1. We currently have an object that taken an Int with a method that returns
   a (Generator, Int) pair. What we really want is a method that takes a
   Generator and returns a (Generator, Int) (You’ll see why this is important
   shortly).
2. We now need to explicitly capture the new Generator that is output
   and use it instead of the old one to get a new random value.

Lets rearrange our code to deal with the first point.

case class Generator(seed: Int)

object Generator {
  def generateRandomInt(g: Generator): (Generator, Int) = {
    (Generator(g.seed + 1), g.seed + 5)
  }
}

import Generator._

val g = Generator(30)
val (g2, res0) = generateRandomInt(g)
// g2: Generator = Generator(31)
// res0: Int = 35
val (g3, res1) = generateRandomInt(g2)
// g3: Generator = Generator(32)
// res1: Int = 36
val (g4, res2) = generateRandomInt(g3)
// g4: Generator = Generator(33)
// res2: Int = 37

Now we have a Generator which is effectively our input data, and a
function with the signature Generator =>(Generator, Int). This looks
exactly like the definition of the state monad from earlier: S =>(S, A).
It is still really tedious to use though because we have to capture the
new generator and feed it through the computation for every step.

This is where the state monad comes in.

Since we have a function generateRandomInt(g: Generator): (Generator, Int)
that effectively models a state change of the Generator object passed in
without any side effects, it is a perfect candidate for the State monad.

We can rewrite our function signature now as
generateRandomInt(): State[Generator, Int].

The meaning of our function remains the same, but since the computation is
now a monad, it makes working with the changing state really simple.

We can now write code like this:

import scalaz._
import Scalaz._

case class Generator(seed: Int)

object Generator {
  def generateRandomInt(): State[Generator, Int] = ???  // We will come back to this
}

import Generator._

val computation = for {
  x <- generateRandomInt()
  y <- generateRandomInt()
} yield (x, y)

val (newGenerator, (xOutput, yOutput)) = computation.run(Generator(57))
// newGenerator: Generator = Generator(59)
// xOutput: Int = 62
// yOutput: Int = 63

As you can see we now have a side effect free, stateful computation that has
very little change when compared to the initial mutable version.

How

The last part of this is to understand how we implement the function:
def generateRandomInt(): State[Generator, Int].

Scalaz defines a bunch of helper functions to work with State monads in
StateOps. The two we are going to use here are get and put.

def get[S]: State[S, S] = State(s => (s, s))

def put[S](s: S): State[S, Unit] = State(_ => (s, ()))

Before we use them, lets quickly have a look at what they do.

get[S] returns a state monad of type State[S, S]. In doing this, it passes
the current state into both the new state AND the output value. This means that
in our generator case, we would have State[Generator, Generator] which
would allow us to actually extract the generator in our for comprehension.

(A simple way to think about it is that the for comprehension plucks out the
value A from a state monad, and updates the state S without you having
to explicitly deal with it like we were before).

So if we had:

  for {
    x <- ourState: State[Generator, A]
  } yield ()

The value of x would be of type A. Since get creates State[S, S], that means
the value of x above would be of the same type as the state i.e. Generator.

So in the following snippit, x would be of type Generator.

  for {
    x <- get[Generator]
  } yield ()

One important bit of intuition that I initially struggled with here is that
get[Generator] appears to pluck some Generator state out of thin air.
The reason this works is that we aren’t actually doing any computation yet here.
Recall that State wraps S =>(S, A). We are actually saying that “when we
have an S, get it”. It is not until later when you actually invoke this method
that you will provide that state S and thus have it available to you.
This is more clear when you realise that the type of this for comprehension is
actually State[Generator, Unit]. We are simply describing a stateful
computation. To run the actual computation we have to call the run method
on a state monad. We will see an example of this shortly.

Now the other function we mentioned we were going to use was put.
We can see that put(s: S) creates a new State monad of type State[S, Unit].
To do this, it actually ignores the current state, and simply creates a new
state using the value s we pass in.

So for example, if we wanted to update our State to hold a new Generator
we might be able to leverage this.

Putting this all together, I encourage the reader to try and implement
def getRandomInt(): State[Generator, Int] before looking at the
implementation below.

object Generator {
  def generateRandomInt(): State[Generator, Int] = {
    for {
      g <- get[Generator]             // Get the current state
      _ <- put(Generator(g.seed + 1)) // Update the state with the new generator
    } yield g.seed + 5                // return the "randomly" generated number
  }
}

As you can see, we simply get the state of the current Generator, create
a new one with a new seed and return our “random” number.

This is a simplified example of how you can use the state monad to produce
side effect free state changes. In order to get there, aside from the State
monad usage, it should be noted that we restructured our code to follow
more of a functional paradigm which consists of Data and functions. The
generator was converted from a stateful object, into a simple data type
and our generateRandomInt() became a stateless function. This is quite
a powerful paradigm but takes a while to become comfortable with when starting
with functional programming.

When

The final question is when do I use this?

In general, the state monad can be used anywhere you have stateful or side
effecting computations. We saw a simple example above with our Generator,
but we can extend this for anything. For example, we often use side effecting
log statements to log things in production. Instead of modelling this as simple
side effecting statements in our functions, we would treat it as a stateful
computation where the state is the statements to log and the value returned
is the value normally returned by the function.

e.g.

def add(a: Int, b: Int): Int = {
  log.info(s"Adding $a and $b")
  a + b
}

add(5, 3)  // Produces a side effect

can be rewritten as:

def add(a: Int, b: Int): State[List[String], Int] = {
  for {
    curr <- get[List[Sting]]
    _ <- put(curr +: s"Adding $a and $b")
  } yield a + b
}

add(5, 3) // explicitly captures the side effect

We will actually see in a later blog that this particular use case of the
state monad is called the Writer monad.

As another example (since I love concrete examples), consider a Robot that
has two buttons, a light and an (x,y) position. Instead of having the robot
mutate its own internal state whilst moving around and responding to button
presses, we can do a similar thing we did with the generator example above
and define functions that transform the robot “data”. (Note that I use the word
data since the robot has a fixed internal state and is thus effectively just
data).

import scalaz._
import Scalaz._

// Lets create a few types of buttons to push
sealed trait Button
case object Button1 extends Button
case object Button2 extends Button

// And represent our different light states
sealed trait LightStatus
case object On extends LightStatus
case object Off extends LightStatus

// Our simple robot has a position and a light that is in a particular state
case class Robot(x: Int, y: Int, lightStatus: LightStatus)

// When we press a button, we want to turn on the light and move the robot
// Since the state of the robot will change, we can model this as a
// State monad.
// You can read the type signature State[Robot, Unit] as Robot => (Robot, Unit)
// This essentially mean "Given some robot state R1, this operation will return
// a new robot state R2 and a value associated with that state change".
// In this case, the value returned is a Unit since moving a robot doesn't
// create an actual value (simply a side effect in the real world).
// (There are ways to deal with this side effect more explicitly using the
// IO monad, but for now lets not worry about that.
def pressButton(b: Button): State[Robot, Unit] = {
  for {
    currS <- get[Robot]
    _ <- turnOnLight()
    moveSideEffect <- move(b)
  } yield moveSideEffect
}

def turnOnLight(): State[Robot, Unit] = {
  for {
    currS <- get[Robot]
    producedValue <- put(currS.copy(lightStatus = On))  // Create a new robot with the changed state
  } yield producedValue                                 // This could be () but I've made it explicit
                                                        // for clarity of whats going on
}

def move(button: Button): State[Robot, Unit] = {
  for {
    currS <- get[Robot]
    producedValue <- put {
      button match {
        case Button1 =>
          // pressing button 1 moves the robot forward
          currS.copy(y = currS.y + 1)
        case Button2 =>
          // pressing button 2 moves the robot backward
          currS.copy(y = currS.y - 1)
      }
    }
  } yield producedValue
}

pressButton(Button1).run(Robot(3, 4, Off))
// res0: (Robot(3,5,On),())

As can be seen, the state monad can lead to really nice composable programs
that model mutable problems without actually mutating the objects we’re working
with.

Stay tuned for the next installment where we will be investigating the Writer
monad.

Logging within for comprehensions: A cleaner way to get visibility into errors

It is quite common in Scala to use the Try monad to deal with computations that can fail in a functional manner. Essentially its used the same way that you would use a try/catch block in java,

e.g.

In java you would have something like

ResultType result = null
try {
  result = someComputationThatCanFail()
} catch (Exception e) {
  // deal with failure
}
doSomethingWith(result)

In Scala this would look like:

Try(someComputationThatCanFail()).map(doSomethingWith)

The main difference here is that in scala you have an expression which will evaluate to either a Success or a Failure. This lets you deal with the results and failures using all the awesome FP approaches like pattern matching, map/flatmap and so on. Since Try is a Monad, we can also compose our computations that may fail with a convenient for comprehension syntax. For example:

for {
  result1 <- Try(someComputationThatCanFail())
  result2 <- Try(someOtherComputationThatCanFail())
} yield doSomethingWith(result1 + result2)

This is really nice as if either of the steps fail, you end up with this whole block evaluating to the Throwable that failed first, otherwise you get a Successful computation from the yield clause. Yet this is exactly where the problem arises that this post will aim to address.

Say both someComputationThatCanFail() and someOtherComputationThatCanFail() can both fail with a RuntimeException(). We can deal with the runtime exception after the try block but we have no idea whether it was caused by the first or second result computation. In a production environment, it is generally useful to capture the context of a failure or the lineage of a computation. In this scenario for example, we would want to know that it was the second calculation that failed and that the first one was successfully completed.

There are a few simple ways of doing this:

Firstly we could unwrap the for comprehension and log each computation that is performed. e.g.:

Try(someComputationThatCanFail()).flatMap(result1 => {
  log.info("Computed result 1")
  Try(someOtherComputationThatCanFail()).map(result2 => {
    log.info("Computed result 2")
    doSomethingWith(result1 + result2)
  })
})

If our second operation fails we will have in our logs “Computed result 1” but not “Computed result 2”. However, this no longer lets us use the beautiful syntax Scala provides in its for comprehensions. (Yes I know, I know…. Get a room).

How can achieve a similar result whilst still using for comprehensions?

One possible way could be to use the pimp my library pattern to write a PimpedTry and add a method which (transparently to the computation) allows logging like so:

class PimpedTry[T](underlying: Try[T]) {

  def onSuccess(f: T => Unit): Try[T] = underlying match {
    case Success(s) => 
      f(s)
      underlying
    case Failure(e) => 
      underlying 
  }
}

object PimpedTry {
  implicit def pimp[T](t: Try[T]): PimpedTry[T] = new PimpedTry(t)
}

This allows us to write things like this:

import PimpedTry._

for {
  a <- Try(3) onSuccess (n => log.info(s"Successfully retrieved $n"))
} yield a

This gives us a much cleaner way to log each step but it breaks that fundamental principle of FP to avoid side effects. We have a side effecting computation on every step in our for comprehension. The issue is that we were modelling the unwrapped for comprehension which by design logs each step as a side effect. It also doesn’t group logs into logical chunks but eagerly dumps them to output. But what if instead of performing side effecting computations, you instead accumulate the logged values within the for comprehension? This would solve both of our problems here.

In comes the writer monad. I like to think of the writer monad as one which “writes” something along with a value. A very simple practical use case for this might be to write a description of a computation being performed, effectively making it a log of that computation. The reality of it is that the writer can deal with any monoid attached to a value. If you’re not sure what a monoid is, check out my previous blog. Scalaz provides a writer implementation in the form of Writer (which is actually implemented a monad transformer lifted into the Id type (a more advanced idea we will get to shortly)). This Writer essentially wraps a tuple (w: W, a: A) where W is the “write” type and A is the value type. In our for comprehensions we will be using the A as our extracted value. Anyway enough explaining, here is a very simple example using syntax you probably won’t see too often in the wild just to make things a bit more explicit.

val result = for {
  a <- Writer[String, Int]("Using 4", 4)
  b <- Writer[String, Int]("Using 5", 5)
} yield a * b

// result: scalaz.WriterT[scalaz.Id.Id,String,Int] = WriterT((Using 4Using 5,20))

As can be seen this uses the implicit monoid instance for string to add the strings without us needing to explicitly handle that, whilst letting us extract the actual values and act upon them as we would expect to normally. If we wanted to track the Strings in an array we could change the String type to List[String] and they would once again combine into List[String] with each element referring to a single line of the computation.

This is starting to look quite promising. We can now write for comprehensions with their logs as we go without creating side effects. The side effects can be dealt with in one spot after the actual computations have taken place. We can access the written text by running the Writer monad and extracting the left hand side of the tuple (and likewise get the computed value from the right hand side).

result.run._1 // Contains the "logged" value: "Using 4Using 5"
result.run._2 // Contains the result of the computation: 20

This seems ideal. We can separate out description of the computation from the actual computation and then deal with the side effecting logging operation in one go in a central location rather than scattered throughout our for comprehension.

Now… Getting to the title of this blog post. How do we log errors using the above approach?

Lets try substituting our Writer[String, Int] for a Writer[String, Try[Int]]

val res2 = for {
  a <- Writer[String, Try[Int]]("Using 4", Try(4))
  b <- Writer[String, Try[Int]]("Using 5", Try(5))
} yield a * b

// Doesn't compile.

Why doesn’t this compile? Well… we are extracting the value of the writer into a and b, which happens to be a Try[Int]. Trying to multiple Try[Int] makes no sense clearly so we need to do a further layer of unwrapping:

val res2 = for {
  a <- Writer[String, Try[Int]]("Using 4", Try(4))
  b <- Writer[String, Try[Int]]("Using 5", Try(5))
} yield {
    for {
      c <- a
      d <- b
    } yield c * d
  }

// res2: scalaz.WriterT[scalaz.Id.Id,String,scala.util.Try[Int]] = WriterT((Using 4Using 5,Success(20)))

This gives us the type we are expecting. What about if we have a computation that fails?

val res2 = for {
  a <- Writer[String, Try[Int]]("Using 4", Try(4))
  b <- Writer[String, Try[Int]]("Using 5", Try(throw new Exception("Failed")))
  c <- Writer[String, Try[Int]]("Using 4", Try(4))
} yield {
    for {
      d <- a
      e <- b
      f <- c
    } yield d * e * f
  }

// res2: scalaz.WriterT[scalaz.Id.Id,String,scala.util.Try[Int]] = WriterT((Using 4Using 5Using 4,Failure(java.lang.Exception: Failed)))

It looks like it correctly captured the failure, but notice what has been logged: “Using 4Using 5Using 4”. This is because our writer monad treats the value as Try[Int] rather than Int like we want it to. What we would really like is to be able to deal directly with the Int and ignore the fact that its two layers of monad deep. We also would like if the Try and the Writer monads still retained their effects (i.e. unwrapping is not an option). This is where that “transformer” thing I mentioned before comes in.

A monad transformer does EXACTLY the job that we want here. It lets us focus on the wrapped up value whilst still keeping the effects of the monad.

Here is the way that a wrapped monad would transform into a Transformer:

Monad1[Monad2[Type]]

becomes

Monad2T[Monad1, Type]

So lets look at the type we constructed before (remember how I said Writer in scalaz actually creates a WriterT?).

WriterT[scalaz.Id.Id,String,scala.util.Try[Int]] 

becomes

Id[Writer[String, Try[Int]]]

Id in this case is effectively the identity monad (meaning we technically a Writer[String, Try[Int]] that is technically expressed wrapped in the Id monad to use WriterT).
As we discovered however, this is not actually the type that we want…. With that type, it logged every operation regardless of whether the operation succeeded and failed. What we actually want is for the operation to only log the steps that have actually been run (much like the unrolled example from earlier).

To get there we need to consider what type we want and then work out what transformer(s) we will need to get there.
As discussed previously, We know that we want Writer[String, Try[Int]] however we haven’t yet had to deal with a transformer that has two Type parameters.
Unfortunately most Transformers expect a single type and so we need to convert out Writer[String, Int] into a Type with only one parameter. This is exactly what type lambdas are used for in type level programming:

TryT[({type L(T) = Writer[String, T]})#L, Int]

This is the same as a regular lambda but its now in the type system. It’s saying that given some type “T”, we want to convert it into a Writer[String, T]. We now have a Type with a single Type parameter (using out little type lambda trick) however this is horrible to look at (especially if you aren’t comfortable type level programming).

A common strategy to make this much nicer to work with is to create a parameterized type alias:

type Log[T] = Writer[String, T]

then we can create out TryT as:

TryT[Log, Int]

Now scalaz doesn’t actually provide us with a TryT transformer (for reasons I am yet to discover, though I’m sure a more savvy scalaz mind can reason this out to me) so I will use an EitherT in its place for demonstration purposes since this is provided (perhaps I will explain how to create a TryT transformer in a future blog).

We can thus encode our type as:

EitherT[Log, Throwable, Int]

This expands to

Writer[String, \/[Throwable, Int]]

which is essentially the same thing as

Writer[String, Try[Int]]

Now using our EitherT, lets see how our for comprehensions work.

First we construct a few functions that produce our type in both success and failure states:

type TextWriter[T] = Writer[String, T]
val e = EitherT[TextWriter, Throwable, Int](Writer[String, TryE[Int]]("Using 4", 4.right))
val e2 = EitherT[TextWriter, Throwable, Int](Writer[String, TryE[Int]]("Using 5", 5.right))
val e3 = EitherT[TextWriter, Throwable, Int](Writer[String, TryE[Int]]("Attempting 6", new Exception("6 failed").left))

Both e and e2 are clearly the success cases and e3 is a failure case.
First lets check how the success case works:

val res3 = for {
  a <- e
  b <- e2
} yield a + b

// res3: scalaz.EitherT[TextWriter,Throwable,Int] = EitherT(WriterT((Using 4Using 5,\/-(9))))

Exactly as we expected it logged each step and performed the calculation without us having to first unwrap the Either from the Writer since we were using EitherT.

Now lets check the failure cases. Recall that we wanted it to act the same way it would in a normal failure case for the inner monad (rather than the writer monad). i.e. We want it to short circuit the logging if the actual value fails (in this case if the either returns a left (-\/)).

val res4 = for {
  a <- e
  b <- e2
  c <- e3
  d <- e
} yield a + b + c + d

// res4: scalaz.EitherT[TextWriter,Throwable,Int] = EitherT(WriterT((Using 4Using 5Attempting 6,-\/(java.lang.Exception: 6 failed))))

This looks like the exact result we expected. It logged all the steps that were attempted and when step 3 failed, it captured the failure and didn’t log step 4 since it was never actually run. The only catch here is that we’ve had to convert all our plain old scala Trys to scalaz Eithers for this trick to work. As mentioned previously one option to fix this is to write our own transformer TryT. This isn’t exactly straightforward as there are a lot of implicits at play in scalaz and you will likely bang your head against the wall a lot if you aren’t comfortable with scalaz.

There is however a more straightforward and simpler approach (though purists would argue less elegant). We need to get from a Try to a loggable Either type. Since implicits can’t be chained in Scala but we don’t want to have to write Try().toEither ~> “” for every for comprehension. We need a more clever way of doing this conversion and then we can do things exactly as we did above.

View bounds are perfectly suited to this task. They essentially say “Give me a way to convert from A => B and I will apply it if I need a B but only have an A”. Here is how something like this might look:

import scalaz.{EitherT, Writer, \/}

object Logger {
  type Logger[A] = Writer[String, A]
}

class PimpedTry[T](underlying: Try[T]) {
  import Logger._
  
  def ~>(msg: String)(implicit ev: Try[T] => Throwable \/ T) = withLog(msg)
  def withLog(msg: String)(implicit ev: Try[T] => Throwable \/ T) = EitherT[Logger, Throwable, T](Writer(msg, ev.apply(underlying)))
}

object PimpedTry {
  implicit def pimp[T](t: Try[T]): PimpedTry[T] = new PimpedTry(t)
  implicit def pimpToEither[T](t: Try[T]): Throwable \/ T = t.transform(s => Try(s.right), f => Try(f.left)).get
}

import PimpedTry._

for {
  a <- Try(4) ~> "Getting 4"
  b <- Try(5) ~> "Getting 5"
  c <- Try[Int](throw new Exception("Failed 1")) ~> "Getting 6"
  d <- Try[Int](throw new Exception("Failed 2")) ~> "Getting 7"
} yield a + b + c + d

// res3: scalaz.EitherT[Logger.Logger,Throwable,Int] = EitherT(WriterT((Getting 4Getting 5Getting 6,-\/(java.lang.Exception: Failed 1))))

And voila. We can now annotate our Try for comprehensions with “~>” to log the process of the computation. We can then deal with the logs in a single place rather than every line of the computation.

The next logical step is to start thinking about how to generalise this concept to run on any monads (likely a future post). Additionally, we would want to be able to be able to deal with nested computations? (Technically computation paths are trees and should be logged as such is possible). There is a great library called Treelog which tackles this problem (https://github.com/lancewalton/treelog) however I found that for my use of requiring dealing with Monads more generally it didn’t quite fit. YMMV. It certainly solves the problem it sets out to solve quite nicely.

But for now, hopefully this given you some insight into some practical uses for scalaz, monad transformers and specifically the writer monad!

Functional sorting algorithms

I was recently revisiting a bunch of sorting algorithms and I wanted to have a crack at implementing them in Scala in a functional manner. The last time I went to do this, I found it a lot more difficult than I thought it would be. Now that I’m feeling pretty comfortable with writing functional styled algorithms I figured I’d write a little blog post just explaining a few simple algorithms and how to approach them functionally. I’ll also dive into the time and space complexities of doing so. I will assume you have a basic knowledge of the various algorithms and how to code them iteratively in a language like Java or C.

First of all, lets look at insertion sort. Insertion sort is a pretty simple algorithm that sorts an array by taking an element at a time and “inserting” it into sorted order. When writing this in place (mutably) you typically will keep a pointer at the front of your list and sort things to the left of it whilst moving the “front” along. This gives a best case time complexity of O(n) if all the elements are already sorted but a worst case of O(n^2) in the pathological case. Obviously the space requirements are O(1) since its an in place algorithm and uses no transient memory in the process.

If we were to write this in a functional manner how would we go about it? What tradeoffs would we have to make to avoid mutability? First of all, we can reason that in order to do an insertion, we would need to make a new copy of the array every time the insertion occurs to avoid mutating the array. Naively this would imply that for an array of size n, we would have n insertions into a list of size n which means O(n^2) space complexity. This seems pretty horrible.

Lets have a look at an implementation in Scala and see if the situation is really as dire as it seems.

@tailrec
def insertionSort(list: Seq[Int], acc: Seq[Int] = Seq.empty[Int]): Seq[Int] = {
  list match {
    case Seq() => acc
    case x +: xs =>
      val (less, more) = acc.span(_ < x)
      insertionSort(xs, (less :+ x) ++ more)
  }
}

First thing to notice is that this is a tail recursive method. In Scala, annotating these kinds of methods with @tailrec allows you to signal to the compiler that you want it to optimise the tail call, which it will do by attempting to convert the function into a while loop. This means that the overhead of a recursive call is no longer used as the values are passed straight to the next call rather than held on the stack at each call. So we know that we don’t have any extra memory being used on the stack. This lets us assume that any space usage is going to be in the second case statement.

First thing we do is a span, which splits the data into the longest prefix that matches the predicate and the “rest”. Since acc holds only the sorted elements so far (the “accumulator”), this will always split right where the element we are considering needs to fit in. The time complexity in the worst case is O(n) if the source list is in sorted order to begin with since each element will be appended to acc by first scanning through all the elements that are already smaller than it. This is in contrast to the iterative version of this algorithm which typically searches backwards through the sorted part of the array (effectively “acc”) and has a worst case time complexity of O(n) when the elements are in reverse sorted order to begin with. Note that these are actually equivalent average complexities when averaged across all possible array combinations.

Finally, it performs a recursive call with the tail of the list, and inserts the head of the list into the accumulator. This is specifically the part we need to investigate.

We have a prepend operation and a concat operation which creates a new copy of the acc array element with this new element inserted in sorted order. At this point we must concede that depending on the type of Seq used, the performance will vary quite dramatically. If you aren’t familiar with the various performance characteristics of scala collections I highly recommend having a thorough read of this link.

http://docs.scala-lang.org/overviews/collections/performance-characteristics.html

We need to know one more piece of information before continuing with this investigation. Namely that scala utilised a technique called structural sharing to avoid making copies of immutable data structures when it doesn’t need to. A simple example of this can be found on this wiki page:

https://en.wikipedia.org/wiki/Persistent_data_structure.

In a nutshell, only copy the bits of the data structure that actually change and leave the rest as is and just point to the old version. Since we are treating everything immutably, we can safely do this without worrying about the previous version of the data structure changing from some other external operation. This may seem massively inefficient when you first hear about it, but that is where the JVM garbage collector comes in. It cleans up all of these temporary data structures that are no longer being referenced.

So armed with the knowledge what can we deduce the space complexity might be?

Firstly lets consider the time complexity.

Clearly a List would be a poor choice of a concrete implementation here since it has linear appends which is exactly what we do twice here, meaning that we have an extra linear operation within the sort. This maintains the asymptotic properties of the algorithm but clearly is quite inefficient. Looking at the various collections, we see that Vectors have effectively constant time appends which is exactly what we want. This means that our update of the acc array on each iteration is actually effectively constant time as we would have had in the mutable version.

Now what about the space complexity?

Again, List would be a poor choice here since prepending to a List would require a copy of all the elements to put a single one at the end. It is fairly safe to say that Vector is going to be the best performing collection to use for both time and space complexity, so lets continue under the assumption that we are using a Vector.

It appears that we make a copy of the “acc” array every time we update it, however due to structural sharing this is not the case. Using a Vector, we only need to change the elements in the path to the root from the new element. This leads to a much more efficient update of the array. It is obviously not constant space but due to Vectors huge branching factor of 32, we don’t need to do much copying until our array starts getting well over 1 million elements, which is remarkable.

So it seems that these algorithms aren’t actually as bad as they initially appeared. They maintain the asymptotic time complexity of the mutable version and use more transient storage space but this is likely not in the order of O(n^2) as we initially feared. This is obviously only the case if we use the right immutable data structure as an implementation however.

It is at this point that I will make it very clear that you should NEVER use a functional sorting algorithm unless you need intermediate results for some reason. It is wasted overhead in 99.9% of cases. Even the scala standard library implements sorting by copying the array and the sorting it mutably using java’s Arrays.sort method. This has the benefit of only using mutability such that it is never exposed to the caller, nor is the original array mutated, but we still get the speed and efficiency of a mutable sort. This is how you should implement these sorts of algorithms in a language like Scala when you have this option. This obviously uses O(n) space due to the copy, but since we are doing FP there is no way around this without introducing mutability.

You might be wondering what the real world difference between a mutable and immutable sort is. In the case of insertion sort, as a test, I wrote a mutable version and and tested it against the version shown above. With 100,000 elements, the mutable one finished in around 1 – 2 seconds. The immutable one however, was taking so long that I had time to put on a pot of coffee, take a shower, remember that I don’t drink coffee, then give up and cancel the run. In a nutshell…. asymptotic analysis means very little when your constant multiplier is big enough to make the algorithm infeasible for real use in the first place.

 

Now lets have a look at a few more sorting algorithms. I won’t go into as much detail for these ones since the principles are largely the same, but I think its quite interesting to see how some common algorithms look when written functionally.

@tailrec
def selectionSort(list: Seq[Int], acc: Seq[Int] = Seq.empty[Int]): Seq[Int] = {
  list match {
    case Seq() => acc
    case li =>
      val min = li.min
      val (h, _ +: t) = li.span(_ != min)
      selectionSort(h ++ t, acc :+ min)
  }
}

def mergeSort(list: Seq[Int]): Seq[Int] = {

  @tailrec
  def merge(l1: Seq[Int], l2: Seq[Int], acc: Seq[Int] = Nil): Seq[Int] = (l1, l2) match {
    case (a @ x :: xs, b @ y :: ys) => if (x <= y) merge(xs, b, acc :+ x) else merge(a, ys, acc :+ y)
    case (rest, Nil) => acc ++ rest
    case (Nil, rest) => acc ++ rest
  }

  def sort(xs: Seq[Int]): Seq[Int] = {
    val n = xs.length / 2
    if (n == 0) xs
    else {
      val (left, right) = xs splitAt n
      merge(sort(left), sort(right))
    }
  }
  sort(list)
}

def quickSort(list: Seq[Int]): Seq[Int] = {
  if (list.length <= 1) list
  else {
    val pivot = list(list.length / 2)
    quickSort(list filter (pivot > _)) ++ (list filter (pivot == _)) ++ quickSort(list filter (pivot < _))
  }
}

I will point out that these may not be the most efficient way to write these algorithms functionally, but its the best I could come up with quickly as examples. I thought that Quicksort in particular was quite concise. It is much less efficient than its mutable cousin due to the triple scan of the array on the recursion step. Additionally, the random access selection of the pivot is only going to be efficient with Vectors since Lists have O(n) random access time complexity,  however it describes the algorithm exactly as it works. This is a great example of why I love functional programming so much. You can focus on the “what” much more than the “how”. Keeping track of pointers and indexes and temporary variables (whilst performant) is a lot of unnecessary noise for most things in my opinion.

You should spend a moment to convince yourself that these algorithms keep the same asymptotic time complexity as their mutable counterparts (even if they are some constant less efficient).

 

I hope this has been a useful dive into the implementation and performance characteristics of some common sorting algorithms when written functionally in Scala. I will look at selection algorithms, and search algorithms in my next post so stay tuned!

Some clarity on the useful bits of category theory in relation to FP

When coming from an imperative background, learning Scala and Functional Programming in general is initially quite difficult. I found that it’s not as simple as matching things you know into a new syntax, but rather requires a fundamental change in the way you think about writing code. There are plenty of amazing resources online to do this if you are willing to put in the time and effort such as the coursera courses: Functional Programming Principles in Scala and follow up: Principles of Reactive Programming.

For this reason, it’s quite easy to skip over the mathematical underpinnings of FP just so that you can get to writing real code quickly. After a decent amount of time coding in Scala, you will be hard pressed to avoid coming across the concept of Monads. The Scala standard library offers a lot of incredibly useful monads such as Future, Option, Try and so on. If you have spent enough time second guessing your sanity to understand monads properly, you’re in the minority. Most people end up with “It’s some kind of burrito container thing. Aw who cares, I can map and flatMap them and it does stuff for me”.

It turns out there is a whole branch of mathematics behind abstract concepts like monads, and I set out to try and get my head around the fundamentals. After reading a lot of bad explanations of things like Functors, Semigroups and Applicatives, I feel as though I’ve finally wrapped my head around the essence and usefulness of these concepts enough to explain it in a relative straightforward way. (As always, relevant xkcd).

To begin, I will refer to an incredibly useful diagram from Typeclassopedia on a simplified heirachy of the fundamental concepts from a presentation on scalaz’s motivations and uses. I’m only going to focus on Functors, Applicative Functors, Semigroups, Monoids and then touch on Monads at the end of the blog. It would be useful to refer back to this with each new concept I introduce to get a feel for where it fits into the heirachy.

I will assume that you are at least superficially familiar with monads or have at least used them in Scala or haskell, but for the most part will avoid referring to them until we get up to the discussion on them.

 

First of all, lets look at Functors.

According to wikipedia: “In mathematics, a functor is a type of mapping between categories which is applied in category theory. Functors can be thought of as homomorphisms between categories. In the category of small categories, functors can be thought of more generally as morphisms.”

My GOD. No wonder people don’t bother learning this stuff properly. Explanations are littered with incredibly precise definitions and assume that you already understand what “categories”, “homomorphisms”, “small categories”, “morphisms” before you can even begin to understand what a functor even is.

I’m going to take a step back and give you a simplified understanding using Scala as a reference. This will sacrifice a bit of precision of the definition to improve the clarity. So lets take a look at the Functor definition in Scala.

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

This simply means that a functor is parameterised by some type F[T] where we don’t care what T is. It also defined a map method. So what does this mean? From the looks of it, we can deduce that a functor is something we can map, but what does that actually imply?

Quick detour – If we consider two sets A and B with elements a∈A and b∈B. We need a total function (which just means that every a∈A produces some b∈B) that maps from A => B. This is contrasted with a Partial Function which maps from a subset of A to B. In Scala A => B implies a total function – every input value has an output value.

So we can say based off the definition of Functor that it is some parameterised container whose value can be mapped from A => B. It would be a reasonable generalisation to say anything that can “map”, (though functions are technically functors as well and they don’t technically “map”, but they do transform some value from some set A to some set B (A => B)).

The more correct way of defining it is that a functor allows the application of a pure function (A => B) to occur within a context (F[_]).

(Don’t worry if that made as much sense american patent law, I’ll come back to this notion of a “context” in the discussion about Applicative Functors).

Now you might be thinking at this point “I get it, but why is that useful?”. The obvious answer is that it’s a really fundamental abstraction that lets you know that the thing you’re dealing with is “mappable”. It would be much like in java, defining a base interface with “map” on it and then having all the subclasses define their version of map. If you deal with these classes at the interface level, you know that they are mappable. It also means that you can pick the right level of abstraction for different concepts. e.g. instead of using a monad because it lets you “map stuff”, you can choose a Functor because that is actually the contract you expect.

 

Now that we have a reasonable understanding of functors, lets take a look at Applicative Functors.

We saw before that a functor “allows the application of a pure function (A => B) to occur within a context (the context of F[_])”. An applicative functor is for the cases where you need to apply a function within a context to a value within a context. If this doesn’t make sense yet, don’t worry, we will go into a bit more detail. Once again lets start by looking at the definition:

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

I’ve invented the name funcMap because I find <*> (from haskell) an incredibly unintuitive thing to name a function. As we can see, as with Functor, an Applicative Functor defines some kind of mapping between two spaces A and B. The difference is in the function f: F[A => B] that is applied.

So a Functor maps from A => B whereas an applicative functor has a mapping from A => B as the type parameter for some F such that F[A => B]. What does this mean?

It simply means that you have a mapping from A => B within the context of F[_]. But what is meant by “context” and how does that apply?

val opt: Option[Int] = Option(3)
val optFunc: Option[Int => Int] = Option((x: Int) => x + 5)

We can see here that we have a value “3” and that value is within an Optional context. The optional context is such that, until we look inside, we don’t know if it is a Some or a None, and thus the context of the Optional value determines the way we interact with it. The same thing can happen with a function. Above we have optFunc which defines a function “(x: Int) => x + 5” in the context of an Option[_]. If we try to apply the contents of the Option, and its a None, it will behave differently to if it had been a Some. This is what is meant by “within a context”.

So what an applicative lets us do is apply something like optFunc to opt, whilst taking their contexts into account. If we had tried to do this with a Functor directly, we would not have been able to compile the code. In Scala, Option is in fact a Monad, so it is quite trivial to do the above operation, however when we are only dealing with Functors, this new level of abstraction is needed.

Truth be told, I haven’t really come across many real world uses of Applicative Functors other than scalaz Validation. This is quite a useful use case as monads have a concept of ordering of operations that applicative functors do not, and as such do not really model the intention of validation. For example if you want to validate that 5 properties meet some predicate and are not dependent on one another, we would ideally use applicative functors because they impose no sequential ordering like monads do.

 

Next lets take a look at SemiGroups:

A semigroup is a very simple concept and much like a Functor, can allow us to reason about our underlying code. I’ve found in particular that semigroups and monoids (which we’ll get to shortly) are very useful when considering things like Map Reduce pipelines. But lets first take a look at what they are.

A semigroup is simply a set S with elements of type T combined with a binary operation that acts on two elements s1,s2∈S such that (s1 operation s2) produces some output of type T. Note here that the output may or may not be present in the set S.

So we could define a trait as we have before to look something like this:

trait Semigroup[T] {
  def operation(s1: T, s2: T): T
}

A simple example of a semigroup is multiplication where T = Int. e.g.

class IntegerSemigroup extends Semigroup[Int] {
  override def operation(s1: Int, s2: Int): Int = s1 * s2
}

The last important part to understand about a semigroup is that its associative. This means that for some values s1,s2,s3∈S, the equation (s1 operation s2) operation s3 == s1 operation (s2 operation s3) holds true. I mentioned earlier that building map reduce pipelines can benefit from knowing when you are dealing with semi groups. The reason for this is that if you know something is a semigroup, you instantly know what you can parallelise it so long as you maintain relative ordering. When you combine the results from each parallel operation execution, they will be the same as if you did them sequentially.

 

Next up lets take a look at Monoids:

A monoid is very easy to understand once you understand a semigroup. A monoid is very literally a semigroup that has what is referred to as “identity”. Identity is formally defined as:

for a set S, i ∈ S such that for any s ∈ S, (i operation s) == (s operation i) == s

I think this is best explained with an example. Given a simple Monoid definition:

trait Monoid[F] extends Semigroup[F] {
  def identity: F
}

we can define a Monoid on type Int, with the operation of multiplication. (Always remember that a Monoid is a type + operation. Integer addition for example is a different monoid to integer multiplication). To be “correct” the types in scala represent a mathematical set of values. Integer for example represents the set of all integers (within the bounds of what can be represented by the Integer type).

To define integer multiplication, we need only to define an identity element. Lets take some Int “3” and multiply it by “1”. We know quite obviously that this returns “3”. Furthermore we can show that the previous definition for identity holds with the number 3 and the operation * and the identity element 1, since 3 * 1 == 1 * 3 == 3. I am not going to prove that this holds for the entire set of possible integers but you should (at least empirically) be quite confident that that case is true.

As such, we would define a monoid with multiplication operation over Integers to have an identity of “1”. Can you think what the identity element might be for addition over integers? (Hint: It’s not the same as multiplication).

So as you can see, the semigroup and monoid abstractions are quite powerful and let us reason about things in very useful way. One thing to keep in mind is that there are lots of implicit things you need to consider when defining the set of values that a monoid is valid over. As I mentioned before for example, integer multiplication is obviously a monoid mathematically, but its technically not realisable when using Int type since we cannot represent INT_MAX * INT_MAX using an Int (due to overflow). These are obviously edge cases that apply to lots of different things in software engineering but its worth keeping in mind when applying these mathematical concepts to the real world.

 

Congratulations if you’ve made it this far! We only have the big bad Monad left to discuss. Now that we have all of these fundamental concepts under our belt though, it should be much easier to follow the more involved parts of the monad definitions.

Monads:

At a high level there are plenty of very useful tutorials on monads, and how to conceptualise them such as “monads are burritos”, “monads are programmable semicolons”, “monads are containers”, so I won’t try and reinvent the wheel there. I personally think of them as all of these depending on the context. A monad is certainly a container, but thats not all it is. It can be though of as a programmable semicolon, but thats not all it is. It can be though of as a burrito, but that just makes me hungry, and its hard to program when I’m hungry. It turns out that wikipedia actually has a reasonably good definition of a monad that whilst incomplete actually covers the crux of what it is. “A monad is a structure that represents computations defined as a sequence of steps: a type with a monad structure defines what it means to chain operations or nest functions of that type together”.

Hopefully if you’ve followed the rest of this blog thus far, you will be able to find a lot of excellent discussions of what monads are that are written by people much smarter than me. I will defer to them, but whilst reading their explanations, keep in mind where it fits in the heirachy we have discussed.

I hope this has been of use to people.

 

A functional typescript library

As you may have picked up by now, I’m a big fan of Scala and its particular brand of FP. At my current job, I use Typescript for front end development. It’s a pretty solid language and gets better with every version, but I feel like it is really lacking in built in FP constructs. To be fair, it doesn’t claim to be a functional language in the first place so I see as less of an issue with the language and more of a potential area for improvement.

One of my colleagues got the ball rolling on building a simple functional library by building an Option type much like you see in scala which I then extended. The basic idea being that a value either exists or it doesn’t. Values that exist can be dealt with indirectly via map/flatMap etc and values that don’t exist will not be touched when these operations are called.

A simple implementation of this looks something like this: (Note that I have removed a bunch of methods from this code for brevity. For the full source code, check out the github page (Edit: Removed project.))

export interface Option<T> {
    getOrElse(f: () => T): T;
    map<S>(f: (t: T) => S): Option<S>;
    flatMap<S>(f: (t: T) => Option<S>): Option<S>;
}

export function Option<T>(t: T): Option<T> {
    return !!t ? new Some<T>(t) : None;
}

export class Some<T> implements Option<T> {
    constructor(private val: T) {}

    getOrElse(f: () => T): T {
        return this.get();
    }

    map<S>(f: (t: T) => S): Option<S> {
        return Option<S>(f(this.get()));
    }

    flatMap<S>(f: (t: T) => Option<S>): Option<S> {
        return f(this.get());
    }
}

export var None: Option<any> = {
    getOrElse: (f: () => any) => {
        return f();
    },
    map: (f: (t: any) => any) => {
        return None;
    },
    flatMap: (f: (t: any) => Option<any>) => {
        return None;
    }
};

As can be seen here, the Some type is implemented as a class since it can hold more than one distinct value between instances. The None value is implemented as a var as there is only a single instance of this in the system. Sadly, I’ve been forced to use a var here for backwards compatibility reasons, but I would ideally like to change this to “const” or the “let” keyword in the latest versions of typescript.

This Option construct now lets you explicitly deal with values that may or may not exist in a typesafe and predictable manner. For example if you are accepting a number which may or may not be null or undefined you can do something like the following:

Option(maybeNumber).map(n => n + 4).getOrElse(() => 7);

You no longer need to worry about doing the

if (!!maybeNumber) { // do something }

pattern that litters so much javascript/typescript code. The other major win here is that anywhere you pass this value, the receiver now knows that the value may not exist and can deal with that explicitly, rather than needing to implicitly know this condition.

You might be wondering about interaction with libraries or other parts of code that can’t have this optional type weaved through. The full github source has a method called orNull() which will either produce the value contained inside the option or null. This lets you deal with unknown values within your system boundaries in a safe and predictable way, whilst still allowing for interactivity with external components who haven’t got the same idea.

So all this is well and good, but what if you have a few of these Option values and you want to combine them?

The standard way to do this in scala is with flatMap. e.g. say you want to add two values that may or may not exist:

var value1 = Option(5);
var value2 = Option(6);
value1.flatMap(a => value2.map(b => a + b));

As you have probably guessed, this syntax can get a little bit tedious as you have more and more Optional things you need to deal with.

Scala has a really nice syntactic sugar for this called a for comprehension which lets you write things like this:

for {
  a <- Option(5)
  b <- Option(6)
} yield a + b

This will yield a Some(11).

I really like this syntax and use it a lot when writing scala code so I set out to replicate it in typescript. Taking a step back, I wanted this generic syntactic sugar to work across any monads that i defined. (Don’t freak out if this is gibberish to you, you can skim over it and still see how its all used afterwards).

To do this, I needed to define a base monad interface that all the monad implementations could implement. ***Warning. The following code is not what I would consider “pure” and may shock and/or offend the more mathematically inclined***. Now that I’ve gotten that out of the way, I should mention that I would like to make these definitions more “pure” and build them up in a similar fashion to how scalaz does, but for now the aim is to get it working.

export interface Monad<M> {
    map<S>(f: (t: M) => S): Monad<S>;
    flatMap<S>(f: (t: M) => Monad<S>): Monad<S>;
}

This is a simple interface that all monad implementations need to extend. The reason I said this isn’t pure for those who are unsure is that this is not actually the contract of a monad. It does however make the building of for comprehensions much easier in typescript.

So now we can define our Option type as:

export interface Option<T> extends Monad<T> {
    getOrElse(f: () => T): T;
    map<S>(f: (t: T) => S): Option<S>;
    flatMap<S>(f: (t: T) => Option<S>): Option<S>;
}

Now how do we turn all this into a for comprehension?

We want to be able to call it in the same (or similar) way to how we do in scala. After a fair bit of trial and error and arguing loudly with the typescript compiler, I finally got the following code:

export function For<T extends Monad<any>, M, R>(m1: Monad<M>, m2: Monad<M>, ...mx: Monad<M>[]) {
    var result: {Yield: any} = {Yield: () => null};
    switch (mx.length) {
        case 0:
            result = For2(m1, m2);
            break;
        case 1:
            result = For3(m1, m2, mx[0]);
            break;
        case 2:
            result = For4(m1, m2, mx[0], mx[1]);
            break;
    }
    return result;
}

function For2<T extends Monad<any>, M, R>(m1: Monad<M>, m2: Monad<M>) {
    return {
        Yield: (f: (f1: M, f2: M) => R) => <T>m1.flatMap(x => m2.map(y => f(x, y)))
    }
}

function For3<M, T extends Monad<any>>(m1: Monad<M>, m2: Monad<M>, m3: Monad<M>) {
    return {
        Yield: (f: (f1: M, f2: M, f3: M) => M) => For(m1, m2).Yield((a, b) => m3.map(x => f(a, b, x))).flatMap(x => x)
    }
}

function For4<M, T extends Monad<any>>(m1: Monad<M>, m2: Monad<M>, m3: Monad<M>, m4: Monad<M>) {
    return {
        Yield: (f: (f1: M, f2: M, f3: M, f4: M) => M) => For(m1, m2, m3).Yield((a, b, c) => m4.map(x => f(a, b, c, x))).flatMap(x => x)
    }
}

I’m aware that this isn’t the prettiest thing to look at but I haven’t worked out how to make it any cleaner and still actually compile *breathes deeply*. Perhaps one of the astute readers can help out here.

Regardless, this provides the desired effect of being able to do the following:

it("should For comprehend", () => {
    var result = For(
        Util.Option(4),
        Util.Option(5)
    ).Yield((x, y) => x + y);
    expect(result).toEqual(new Some(9));
});

it("should For comprehend with failures", () => {
    var result = For(
        Util.Option(4),
        Util.Option(null)
    ).Yield((x, y) => x + y);
    expect(result).toEqual(None);
});

it("should For comprehend with 3 values", () => {
    var result = For(
        Util.Option(4),
        Util.Option(5),
        Util.Option(6)
    ).Yield((x, y, z) => x + y + z);
    expect(result).toEqual(new Some(15));
});

it("should For comprehend across a different type", () => {
    var result = For(
        Util.Option(4),
        Util.Option(5)
    ).Yield((x, y) => "Different Type");
    expect(result).toEqual(new Some("Different Type"));
});

Now you can combine Monadic types in simple and predictable ways that don’t involve 10 layers of indecipherable flatMaps.

Once again, check out the library for more monads such as Future<T> and Try<T>.

Writing Iterative Algorithms in a Functional Manner

I’ve taken several algorithms courses and they have all taught algorithms using an imperative language and mindset. Whilst I totally understand the reasoning behind this, it made the transition into writing functional algorithms a little bit murky. I thought that I might share some thoughts and revelations that I’ve had in how to write some basic iterative algorithms in a clean and functional manner.

I use scala for my day to day, so I’ll write up my examples in that. The syntax should hopefully be clear enough to follow even if you’re not overly familiar with scala.

Take a simple example of list intersection. The problem here is to take two lists, with n and m elements in them respectively and return a list of all the common elements. The efficient way to do this is using skip pointers, but lets for now assume that we don’t care too much about optimisations and just want a simple linear O(n + m) approach.

If we were to approach this in an iterative manner, we would maintain a pointer on each list and iterate through the lists, advancing the pointer with the lower value at each step and advancing them both if a common element is found. This isn’t overly complex but the implementation can quickly become tedious. You have to maintain the state of two separate pointers and ensure that they aren’t going beyond the length of their array.

Note at this point that I am not claiming that functional algorithms are “better” in any way. I just want to show how to approach them.

Now how would you do this functionally?

The first step I used to take was to recognise that it would need to be recursive. So you set up something like this:

def intersect(list1: Seq[Int], list2: Seq[Int]): Seq[Int] = {
  def loop(l1: Seq[Int], l2: Seq[Int], acc: Seq[Int]): Seq[Int] = {
    // do recursion
  }
  loop(list1, list2, Nil)
}

This is a common template for recursive algorithms in scala. A similar thing can be found in java where you will have a public facing method to accept the lists and then pass it off to a private method that does the actual recursion and state management.

Those who are familiar with scala would recognise that there is an even easier way to encode the above structure.

def intersect(list1: Seq[Int], list2: Seq[Int], acc: Seq[Int] = Nil): Seq[Int] = {
}

Now the caller can still call

intersect(l1, l2)

without needing to worry about the list of matches thus far being set to Nil on initial invocation.

The next step is to think about the possible cases. We want to look at the head of both list 1 and list 2, and then do something with those values. We also need to consider what to do if either list 1 or 2 or both are empty.

This leaves us with four cases:

case 1 = both lists have one or more elements
case 2 = list 1 has 1 or more, and list 2 is empty
case 3 = list 2 has 1 or more and list 1 is empty
case 4 = both lists are empty

In scala:

(list1, list2) match {
  case (h1 :: t1, h2 :: t2) =>
  case (h1 :: t1, Nil) =>
  case (Nil, h2 :: t2) =>
  case (Nil, Nil) =>
}

Now with the intersect, its quite clear that if we only have one or less lists that we cant do any actual intersection, so we can stop the algorithm early and return our list of intersected points. This compresses our above cases into:

case (h1 :: t1, h2 :: t2) =>
case _ => acc

So now we have a template for our recursion that deals with all the base cases of this algorithm:

def intersect(list1: Seq[Int], list2: Seq[Int], acc: Seq[Int] = Nil): Seq[Int] = (list1, list2) match {
  case (h1 :: t1, h2 :: t2) => // do something
  case _ => acc
}

Now all thats left is to finish our main recursive case. The conditions as mentioned earlier can be encoded with a simple if else block, though there is one new thing to introduce at this point.

Scala has a nifty pattern matching functionality that lets you refer to an entire matched section using an “@” symbol.

so for example matching on (a @ h1 :: t1) will match a list and bind the head to “h1” and the tail to “t1”, but it will also bind the entire list to “a”.

Using this, we can finish the algorithm in a very clean manner.

@tailrec
def intersect(l1: Seq[Int], l2: Seq[Int], acc: Seq[Int] = Nil): Seq[Int] = (l1, l2) match {
  case (a @ h1 :: t1, b @ h2 :: t2) =>
    if (h1 == h2) intersect(t1, t2, acc :+ h1)
    else if (h1 <= h2) intersect(t1, b, acc)
    else intersect(a, t2, acc)
  case _ => acc
}

Note here that all the recursive cases end with a call to the same function. This is called tail recursion and is the idiomatic way in scala to write recursive algorithms that don’t overflow the stack. The reason for this is that the compiler can recognise the structure and convert it into a while loop at the byte code level (which is far more efficient that using a new stack frame on each recurse). The @tailrec annotation is just a way to let the compiler know that we intend for this structure to be the case, and it won’t let us compile unless it agrees.

And voila. We have written a purely functional version of the intersect function.

For those of you more familiar with scala, you may be wondering why we don’t just use the intersect method that is built into the collections library. Obviously in real world code that would be the thing to do, but I wanted to cover a functional take on it in this post.

For fun, we could convert the above code which only works on Int into a nice generic version.

@tailrec
def intersect[A](l1: Seq[A], l2: Seq[A], acc: Seq[A] = Nil)
                (implicit ordering: Ordering[A]): Seq[A] = (l1, l2) match {
  case (a @ h1 :: t1, b @ h2 :: t2) =>
    if (h1 == h2) intersect(t1, t2, acc :+ h1)
    else if (ordering.compare(h1, h2) < 0) intersect(t1, b, acc)
    else intersect(a, t2, acc)
  case _ => acc
}

The only difference here is that we need to define an ordering between elements since we don’t know how to compare two A’s. Scala lets you do this implicitly so that you don’t need to pass in an ordering function for things that have an ordering defined in scope. This means that the generic version will immediately work with common types like String, Int and Double.

Hopefully this has helped understand one of the many ways to think about how to write your iterative algorithms in a more functional way.

Setting up a secure social cluster and auth server + CORS support

I’ve been using secure social recently to set up a user authentication scheme. I had two requirements. Firstly I needed an auth server that was able to handle user signup and user login via ajax from a rich client app, and secondly I needed to be able to run secure social on a cluster of nodes.

I found this excellent resource to get the newest version of secure social set up since there is no real documentation for it yet:

http://www.filtercode.com/play/play-scala-securesocial

There were still a few things that weren’t immediately obvious to meet my requirements.

• Secure social authenticators are stored in plays cache by default which means that it wouldn’t work across more than one node by default.
• Ajax isn’t supported out of the box.
• Calling an auth server from my web server would violate the single origin policy.

Since I couldn’t find any solutions to the first two of these problems online (presumably because I’m using 3.0-M3 which isn’t officially a full release yet), I figured I’d write up how I got around them to hopefully help others get going.

First of all the authenticators.

Setting up a secure social cluster

Secure Social uses typed authenticators to authenticate users (duh). The issue is that it stores these authenticators in play’s cache. This is perfectly fine if you are only running a single node but as soon as a request is sent to a second node, it was not aware that the user had already authenticated, causing them to log in again. There are a few ways around this but the main two that suited my use case involved:

• Set up a memcache (or otherwise) to effectively share the cache across multiple servers
• Persist authenticators in a shared data store

I went with the second option for several reasons though there is no issue with going down the former path.

The basic approach I took was as follows:

• Override the default AuthenticatorStore to create a custom authenticator storage mechanism
• Inject my custom AuthenticatorStore into the runtime environment
• Set up a periodic job to expire the authenticators when appropriate

Here is a bit of simple sample code to get you going (mine was a bit more involved but the basic approach should be as simple as this).

<pre>class DbAuthenticatorStore[A <: Authenticator[User]](authenticatorService: AuthenticatorService)
                                                    (implicit executionContext: ExecutionContext)
  extends AuthenticatorStore[A] {

  val log = Logger("your.package.name.here")

  /**
   * Retrieves an Authenticator from the data store
   *
   * @param id the authenticator id
   * @param ct the class tag for the Authenticator type
   * @return an optional future Authenticator
   */
  override def find(id: String)(implicit ct: ClassTag[A]): Future[Option[A]] = {
    authenticatorService.findById(id).map(_.map(_.asInstanceOf[A]))
  }

  /**
   * Saves/updates an authenticator into the data store
   *
   * @param authenticator the instance to save
   * @param timeoutInSeconds the timeout.
   * @return the saved authenticator
   */
  override def save(authenticator: A, timeoutInSeconds: Int): Future[A] = {
    authenticatorService.persist(authenticator).map(res => {
      log.debug(s"Saving of token with id ${if (res == 1) "succeeded" else "failed"}")
      authenticator
    })
  }

  /**
   * Deletes an Authenticator from the data store
   *
   * @param id the authenticator id
   * @return a future of Unit
   */
  override def delete(id: String): Future[Unit] = {
    authenticatorService.delete(AuthenticatorId(id)).map {
      case res => log.debug(s"Removal of token with id $id ${if (res == 1) "succeeded" else "failed"}")
    }
  }
}</pre>

This is a quick and dirty version of the generic solution (its coupled to the User type etc) but it should give you the idea.

The second step is to override the authenticatorService in global.scala

<pre>object MyRuntimeEnvironment extends RuntimeEnvironment.Default[User] {
  // A custom AuthenticatorService that is used to persist authenticators in the database rather than plays cache.
  override lazy val authenticatorService = new AuthenticatorService(
    new CookieAuthenticatorBuilder[User](new DbAuthenticatorStore[CookieAuthenticator[User]](Authenticators), idGenerator),
    new HttpHeaderAuthenticatorBuilder[User](new DbAuthenticatorStore[HttpHeaderAuthenticator[User]](Authenticators), idGenerator)
  )
}</pre>

Finally you need to set up a way to periodically remove the expired authenticators from the database. There are many different ways you can do this depending on your requirements and infrastructure. I went for a simple akka scheduled message approach:

<pre>class AuthenticatorExpiryActor(authenticatorService: AuthenticatorService)
  extends Actor with ActorLogging {

  override def receive: Receive = {
    case RemoveExpired() =>
      log.debug("Removing expired authenticators")
      authenticatorService.deleteExpired()
  }
}</pre>

and set up in global:

<pre>lazy val authenticatorExpiryActor = Akka.system().actorOf(Props(new AuthenticatorExpiryActor(Authenticators)), "authenticatorExpiryActor")
Akka.system().scheduler.schedule(Duration.Zero, Duration(1, TimeUnit.MINUTES), authenticatorExpiryActor, RemoveExpired())</pre>

This is obviously a naiive solution however it should give you the idea of what you need to do to meet the requirements of your system. (I personally extended this solution a fair bit to address certain requirements that many people may not have, so the sample code is very bare bones as more of a guide than a comprehensive solution).

Now you should be able to cluster your secure social authenticators across multiple nodes.

Setting up an auth server

The astute reader might notice that whilst this solves the issue of clustering secure social, it doesn’t address the same origin problem I mentioned initially that you will get if trying to call an auth server from another domain.

Heres a quick explanation if you’re not familiar with it:

http://en.wikipedia.org/wiki/Same-origin_policy

The basic idea is that you need to send requests from the same origin as the requested site. There are two ways around this requirement. One is CORS and the other is jsonp. I solved the problem with CORS since its pretty straightforward to set up with play.

In play 2.4 its as easy as adding the cors filter:

https://www.playframework.com/documentation/2.4.x/CorsFilter

For those of us using secure social however, play 2.4 isnt yet supported (at the time of writing). As such we need to set up cors support manually. Thankfully this is a pretty easy thing to do and there are a few good examples of how to do this online. I set it up as follows:

Add the filters dependency in build.sbt

<pre>libraryDependencies ++= Seq(
  filters
)</pre>

Create a CORS filter

<pre>object CorsFilter extends Filter {

  def apply (nextFilter: (RequestHeader) => Future[Result])(requestHeader: RequestHeader): Future[Result] = {

    def fromConfig(propertyName: String): String = Play.current.configuration.getString(propertyName).get

    nextFilter(requestHeader).map { result =>
      result.withHeaders(
        HeaderNames.ACCESS_CONTROL_ALLOW_ORIGIN -> fromConfig("cors.access-control-allow-origin"),
        HeaderNames.ACCESS_CONTROL_ALLOW_CREDENTIALS -> fromConfig("cors.access-control-allow-credentials"),
        HeaderNames.ALLOW -> fromConfig("cors.allow"),
        HeaderNames.ACCESS_CONTROL_ALLOW_METHODS -> fromConfig("cors.access-control-allow-methods"),
        HeaderNames.ACCESS_CONTROL_ALLOW_HEADERS -> fromConfig("cors.access-control-allow-headers")
      )
    }
  }
}</pre>

Pass it into the Global config:

<pre>object Global extends WithFilters(CorsFilter) with play.api.GlobalSettings</pre>

Create a CORS controller

<pre>trait CorsController extends Controller {
  def options(path: String) = CorsAction {
    Action { request =>
      Ok.withHeaders(ACCESS_CONTROL_ALLOW_HEADERS -> Seq(AUTHORIZATION, CONTENT_TYPE, "Target-URL").mkString(","))
    }
  }
}

// Adds the CORS header
case class CorsAction[A](action: Action[A]) extends Action[A] {

  def apply(request: Request[A]): Future[Result] = {
    action(request).map(result => result.withHeaders(
      HeaderNames.ACCESS_CONTROL_ALLOW_ORIGIN -> "*",
      HeaderNames.ALLOW -> "*",
      HeaderNames.ACCESS_CONTROL_ALLOW_METHODS -> "POST, GET, PUT, DELETE, OPTIONS",
      HeaderNames.ACCESS_CONTROL_ALLOW_HEADERS -> "Origin, X-Requested-With, Content-Type, Accept, Referer, User-Agent"
    ))
  }

  lazy val parser = action.parser
}

object CorsController extends CorsController</pre>

and override the authenticate provider urls in your routes file:

<pre># Providers entry points
GET     /authenticate/:provider     @controllers.auth.AjaxProviderController.authenticate(provider)
POST    /authenticate/:provider     @controllers.auth.AjaxProviderController.authenticateByPost(provider)</pre>

Finally, set up the configuration file to allow specific domains (in application.conf):

<pre>
# CORS SUPPORT
cors = {
  access-control-allow-origin = "http://supported.url.here"
  access-control-allow-credentials = "true"
  allow = "*"
  access-control-allow-methods = "POST, GET, PUT, DELETE, OPTIONS"
  access-control-allow-headers = "Origin, X-Requested-With, Content-Type, Accept, Referer, User-Agent"
}</pre>

The final issue I had was getting ajax working. This used to be supported out of the box with an ajax=true flag on controller actions, but the most recent versions of secure social have removed this. I will address how to set up ajax calls for login etc in my next blog post. Stay tuned.

I hope this has been helpful to people using secure social. If I’ve made any mistakes in the code I posted or my approach, please let me know.