TL Monads – Introduction

in Scala

IMPORTANT: It is recommended that you clear some time to concentrate in reading this article. You will probably not benefit from just browsing through it.

Before going into what the Monad abstraction means, let’s discuss abstraction in general. We’ll start with an example.

No matter which programming language you use, you’ll probably have a single implementation of your favorite sorting algorithm (e.g., merge sort).

It is outrageous to think about implementing the same algorithm for every data type you use; in other words, you will never write the same sorting logic for numbers, strings, person, etc. You will only provide an implementation of some interface (Ordering in Scala, Comparator in Java) to describe how elements are ordered between themselves.

Ordering/Comparator is the abstraction.

Every abstraction is composed of several aspects:

1. The contract – the abstract methods which an instance of the abstraction should implement.

trait Ordering[A] {
	def compare(a1: A, a2: A): Int
}

NOTE: Abstractions always receive a type parameter (generics/templates).

We are sticking to the popular definition that returns an Int (negative for lower than, zero for equality, and positive for greater-than); however, a good implementation should provide a Sum Type (enum).

2. The laws – what is a good implementation?

Consider the following implementation of Ordering[String]:

     override def compare(s1: String, s2: String) = 
s1.compareTo(s2.toUpperCase)

It will not behave correctly.

This is, for example, because we assume that an element should be equal to itself.

Every abstraction has some implicit laws that restrict the implementations.

Most languages are not strong enough to enable to express these restriction at the compilation level (there is a need for dependent-types support, which are not covered in this post).

Usually, the rules are described in documentation (which most people don’t read); however, it is recommend to put these laws in testable methods. For example:

trait Ordering[A] {
	def compare(a1: A, a2: A): Int
	object Laws {
	  def reflexive(a: A) = compare(a,a) == 0
	  def antisymmetric(a1: A, a2: A) = 
if (compare(a1,a2) > 0) compare(a2,a1) < 0
else if (compare(a1,a2) < 0) compare(a2,a1) > 0
else compare(a2,a1) == 0
	 }
	def transitive(a1 :  A, a2: A, a3 : A) = 
if (compare(a1,a2) >0 && compare(a2, a3) > 0) compare(a1,a3) > 0
else (compare(a1,a2) < 0 && compare(a2,a3) <0) compare(a1,a3) < 0
else true
}
}


Now, in addition to the inherent documentation, we also have the test methods that can be used to perform property-based tests (using, for example, ScalaCheck).

3. The gain – what code can be written for the abstraction without duplications for every specific type?

Regarding Ordering, we can implement, for example, the following:

1. Sorting (all algorithms)

2. Max/min methods

3. Sorted data structures (TreeSet, TreeMap)

4. Select Nth algorithms

So, back to Monads.

Monad is an abstraction. Nothing more.

Let’s first describe its contract:

trait Monad[M[_]] {
   def flatMap[A,B](ma: M[A])(f: A =&amp;gt; M[B]): M[B]
   def pure[A](a: A) : M[A]
}

 

Some things to note:

1. This abstraction can’t be written in Java or C# because it requires language support for high-kinded-types (i.e., the generic argument must accept a single type parameter).

2. Do not confuse with the provided flatMap methods on some types (e.g., Traversable, Option). It’s like the distinction between string1.compareTo(string2) and Ordering[String].

A Monad instance provides an external means to flatMap (usually it will delegate to the provided method when applicable).

A Monad instance can be defined for the familiar Option type:

implicit object OptionMonad extends Monad[Option] {
    override def flatMap[A,B](oa: Option[A])(f: A => Option[B]) = oa.flatMap(f)
    override pure[A](a: A) = Option(a)
}

Pure is wrapping a value with Option (checking the null-ness)
flatMap for Option is best explained in the following code:

val o1 : Option[Int] = ???
val o2 : Option[Int] = ???
val osum : Option[Int] = o1.flatMap(i1 => o2.map(i2 => i1 + i2))


The osum value represents either the sum of both options (if they exist) or None (if one of them, or both, is None).
This uses the built-in flatMap and map methods. It can be rewritten with the OptionMonad instance.
There are also three laws for the Monad abstraction. Although they are important, we will not delve into the fine details here. We’ll just note them:

object Laws {
	def leftIdentity[A](ma: M[A]) = flatMap(ma)(pure) == ma
	def rightIdentity[A,B](a: A)(f: A => M[B]) = flatMap(pure(a))(f) == f(a)
	def assoc[A,B,C](ma: M[A])(f: A => M[B])(g: B => M[C]) =
	flatMap(flatMap(ma)(f), g) == flatMap(ma)(a => flatMap(f(a))(g))
}

And that’s it! The Monad abstraction.
It is not more important or less important than Ordering. Like Ordering, it allows writing code in an abstract way (without duplication for every instance of the abstraction).
Now we’ll see what can be gained from the abstraction and some examples of instances.
Note that there are many more instances to Monad and there are countless methods that we can write that use this abstraction (to free us from duplications).

trait Monad[M[_]] {
	def flatMap …
	def pure …
	object Laws{…}
	def map[A,B](ma: M[A])(f: A => B) = flatMap(ma)(a => pure(f(a)))
	def sequence[A](lma: List[M[A]])  : M[List[A]] = 
lma.foldRight[M[List[A]]](Nil){
		(elem, acc) => flatMap(acc)(la => map(elem)(a => a +: la))
}
}

As you can see, you automatically gained the familiar map method for every Monad instance (no need to duplicate your own).
Also, the sequence method can be very useful. Let’s discuss an example:
Let’s say that we parsed some JSON (represented as Map here), and we want check whether a list of fields exists in the JSON and if so, construct an object from their values.

val json : Map[String, String] = ???
val names = List(“name”, “age”, “gender”)
For each name, we want to read the appropriate value from the JSON:
val values = names.map(json.get)

However, the returned type is: values: List[Option[String]]

It is somewhat inconvenient to work with.

We’ll use the sequence method:

val allValues = OptionMonad.sequence(values)

Now we have a single Option representing whether all fields exist or not.

Usually, developers define this method specifically for Option type. This is like defining a merge sort specifically for Option. With the Monad abstraction, we gain it for free.

Let’s take a look at another instance: Reader.

In this post we’ll not go into the definition of this instance, let’s just say that Reader encapsulates a function of: S => A. In our example, a function from UserDAO => A.

Assuming we have a Monad instance for Reader[UserDAO…] and we have the following function:

def getUserById(id: String) : Reader[UserDao, User] =
	Reader(dao => dao.getUser(id))

Now, we have a list of IDs:

val ids = List(id1, id2, …)

When we have a UserDao (a.k.a Dependency Injection), we want to retrieve all users.
So we’ll do the following:

val readUsers = ids.map(getUserById)

The type that we get is: List[Reader[UserDAO, User]]

But we don’t want to pass the dao to every element of the list.

So, as you may have already guessed, we’ll use sequence:

val usersR = userDaoReaderMonad.sequence(readUsers). 

And the type we got: Reader[UserDao, List[User]]

That is, when given a UserDao, we will get a list of User objects.

The sequence method is just a single example. There are many more methods that can be defined that use the Monad abstraction. More examples can be seen in the scalaz and cats open source projects.

Contact us
You might also like
Share: