Monads - Functional Programming with Scala - 101 Series!

This will be a series to introduce you to the world of Functional Programming and fall in love with it as I did. I will be using Scala as the tool to explain as I use it for day-to-day development at my work. So for this article, we will talk about - Monads!

What is Monad?

Anything in the functional paradigm which supports identity and bind operations and follows Monad Laws is a Monad. I know you didn't get a bit of it, let me explain.

Identity

Identity aka pure is like a constructor of a Monad. In vanilla Scala, there is no class or trait named Monad but if you use some library like Cats, it's an altogether a different case.

def pure[A](x: A): M[A]

So if you look at the def pure, it has a return type of M[A] or Monad of type A. Yes, Monads take type parameters. Here, pure wraps A-type object and gives you an A-type Monad. As we have been talking that in scala, there is no out of the box class or trait named Monad, so how do they exist in scala? In scala, apply() comes to your rescue, yes, for an example, List which is a popular Monad has an apply() method or it's simply invoked when you create a List.

scala> val l = List(5,10)
l: List[Int] = List(5, 10)

scala> val list = List.apply(1,2,3)
list: List[Int] = List(1, 2, 3)

Set/Tuple(Just anything but a collection! 😝) of Integers[Int] when apply()[pure], it gives a Monad[List] of type Int.

Bind

Bind is also widely accepted as flatMap, a transformation operation which is nothing but a mapping an object of type A ⇒ B via a lambda or expression.

def flatMap[A, B](fa: M[A])(f: (A) ⇒ M[B]): M[B]

In def flatMap, it transforms Monad of type A to Monad of type B via lambda/expression f.

Now you may ask me, "Hey Pranay! Why don't you just map it? Why flatMap?". Well, my friend, the map is just a subset of flatMap, where the later is much powerful. To give you a perspective, let's take an example of a list of Integers.

scala> val l = List(5,10)
l: List[Int] = List(5, 10)

scala> val f: Int => List[Int] = x => List(x-5,x,x+5)
f: Int => List[Int]

scala> l.map(f)
res0: List[List[Int]] = List(List(0, 5, 10), List(5, 10, 15))

scala> l.flatMap(f)
res1: List[Int] = List(0, 5, 10, 5, 10, 15)

It's pretty clear from the example, how flatMap is different from the map. Here, lambda f takes an Int and create a List of integers. When you apply just what it actually does:

map: List(5 ⇒ List(0,5,10), 10 ⇒ List(5,10,15))

Once you have mapped, we will flatten the List (take out from their individual List):

flatten: List(List(0,5,10),List(5,10,15)) ⇒ List(0,5,10,5,10,15)

flatMap is map followed by flatten, by the same principle, We can define map using flatMap in a way that the mapped entity is not flattened.

map: flatMap(x ⇒ pure(f(x)))

To realise the same with the help of the previous example:

scala> l.map(f)
res0: List[List[Int]] = List(List(0, 5, 10), List(5, 10, 15))

scala> l.flatMap(x => List.apply(f(x)))
res1: List[List[Int]] = List(List(0, 5, 10), List(5, 10, 15))

But the same can't be achieved for flatMap from the map without flatten.

Monad Laws

Not everything with constructor function like pure/identity/apply and transformation operator as bind/flatMap can be called as Monad, It also needs to obey the Monad Laws.

Monad Laws are quite complicated but bear with me, I will simplify it as much as possible. f and g are expressions of type A ⇒ Monad[A]. There are three Monad Laws:

1) Left Identity: If we apply an Identity followed by bind a lambda/expression, it's same as directly applying the lambda/expression.

pure(x).flatMap(f) == f(x)

List as an example for the law:

scala> val a = 25
a: Int = 25

scala> List.apply(a).flatMap(f)
res0: List[Int] = List(20, 25, 30)

scala> f(a)
res1: List[Int] = List(20, 25, 30)

2) Right Identity: If we bind an Identity to a Monad value, it's same as doing Nothing.

m.flatMap(pure) == m

List as an example for the law:

scala> val list = List(10, 25, 50)
list: List[Int] = List(10, 25, 50)

scala> list.flatMap(x => List(x))
res4: List[Int] = List(10, 25, 50)

3) Associativity: If we bind lambda f to a Monad value and bind lambda g to resultant, it's same as binding lambda f followed by binding lambda g to a Monad value.

m.flatMap(x ⇒ f(x).flatMap(g)) == m.flatMap(f).flatMap(g)

List as an example for the law:

scala> val f: Int => List[Int] = x => List(x - 5, x, x + 5)
f: Int => List[Int]

scala> val g: Int => List[Int] = x => List(x, -x)
g: Int => List[Int]

scala> val list = List(10, 25)
list: List[Int] = List(10, 25)

scala> list.flatMap(x => f(x).flatMap(g))
res2: List[Int] = List(5,-5,10,-10,15,-15,20,-20,25,-25,30,-30)

scala> list.flatMap(f).flatMap(g)
res3: List[Int] = List(5,-5,10,-10,15,-15,20,-20,25,-25,30,-30)

Testing a Monad!

Let's test a known Monad like Option in scala with what we have learnt right now:

{i}   def pure[A](x: A): M[A]
{ii}  def flatMap[A, B](fa: M[A])(f: (A) ⇒ M[B]): M[B]
{iii} pure(x).flatMap(f) == f(x)
{iv}  m.flatMap(pure) == m
{v}   m.flatMap(x ⇒ f(x).flatMap(g)) == m.flatMap(f).flatMap(g)

Corresponding verification for Option in scala, for {i}

scala> val a = Option(2)
a: Option[Int] = Some(2)

scala> val b = Option.apply(2)
b: Option[Int] = Some(2)

for {ii} and {iii}

scala> val f: Int => Option[Int] = x => Option(x*2)
f: Int => Option[Int] 

scala> val g: Int => Option[Int] = x => Option(x*3)
g: Int => Option[Int] 

scala> a.flatMap(f)
res1: Option[Int] = Some(4)

scala> f(2)
res3: Option[Int] = Some(4)

for {iv}

scala> a.flatMap(x => Option(x))
res5: Option[Int] = Some(2)

for {v}

scala> a.flatMap(x => f(x).flatMap(g))
res6: Option[Int] = Some(12)

scala> a.flatMap(f).flatMap(g)
res7: Option[Int] = Some(12)

There are many popular Monads in scala such as Sets, Seq, Lists, Options and many more...

Take this as an exercise to verify the "Monadicity"(Ok! I coined it, It's not legal 😋) of these Monads. Another controversial so-called/claimed Monad is Future. If you have reached till here, then the power vests in your hand to identify any Monad thrown at your path. You will find many resources and debates on the Internet over this, but I would like you to consider forming your own opinion about Future as a Monad and then jump to the discussion, I promise you by the end of this discovery, You will be enlightened!

Why Monad is Awesome?

So what's the hype about the Monads? So we are discussing monads because it's an advanced but easy topic under functional programming and it shows the beauty of the paradigm at its best. Let me give you a glimpse of the power of monads with a simple example.

Problem Statement: Take a set of Integers and give the 90th percentile of the even values for thrice the values of the elements in the set.

Solution:

//Creating a set 0f 50 random integers under 100
scala> val set = Set.fill(50)(scala.util.Random.nextInt(100))
set: scala.collection.immutable.Set[Int] = HashSet(56, 37, 28, 97, 96, 91, 72, 40, 36, 15, 83, 69, 88, 20, 78, 61, 89, 1, 6, 85, 9, 53, 34, 64, 44, 59, 27, 12, 49, 86, 81, 39, 98, 67, 16, 8, 75, 82)

//Created a set of thrice values and kept only even values
scala> val evenSet = set.map(x => x*3).filter(x => x%2 == 0)
evenSet: scala.collection.immutable.Set[Int] = HashSet(234, 120, 132, 192, 264, 108, 258, 246, 294, 24, 288, 216, 84, 60, 102, 48, 18, 36, 168)

//Made a Seq, sorted it, got first 10% elements in Seq and gave last element
scala> evenSet.toSeq.sorted(Ordering.Int.reverse).take(((0.1*evenSet.size).ceil).toInt).last
res0: Int = 288

All that transformation in just two lines of code, take up a task to do it in a single line of code.

So the question is where is so-called Monad's flatMap. The answer is, every lambda that you see here, be it filter, sorted, take, map, fill and etc, are all derivatives of flatMap!

Isn't that Amazing?😀