Grokking Monad in Scala

This is the literal programming file that generates 3-*.scala files here

you can actually run sbt testOnly *<className> to finish these exercises

Type classes

Type classes is somewhat like an FP design pattern, with type classes you can extend new functionality without touch any of your existing code or 3rd party library. Type classes vs OO classes

  Add new method Add new data
OO Change existing code Existing code unchanged
FP Existing code unchanged Change existing code

But FP has pretty elegant [way](https://oleksandrmanzyuk.wordpress.com/2014/06/18/from-object-algebras-to-finally-tagless-interpreters-2/) or [ways](http://www.cs.ru.nl/~W.Swierstra/Publications/DataTypesALaCarte.pdf) to walk around this issue.

Algebraic Data Type

package typeclass

import org.scalatest._

class `2.1.ADT` extends FlatSpec with Matchers {

We all familiar with how to implement traffic light in OO with class and interface. Simply 3 classes Red Green Yellow extend a TrafficLight interface, and implement next method in each of the 3 classes.

But how can we do differently with Scala trait and pattern matching?

behavior of "TrafficLight"

it should "follow the rules" in {
  Red.next shouldBe Green
  Green.next shouldBe Yellow
  Yellow.next shouldBe Red

The type of TrafficLight you've just implemented is call Algebraic Data Type(ADT), which means the type is algebra of Red + Green + Yellow, type of algebra of + is called Sum or Coproduct type. The other algebra is x, we've already tried case class in Scala, which is a Product Type. e.g. Cat is product type because it's String x String. You also can simply translate + as or and x as and then it will make more sense.


Recursive Data Type

package typeclass

import org.scalatest._

class `2.2.RecursiveDataType` extends FlatSpec with Matchers {

with ADT it's very easy to implement a linked list in Scala as well. Try using sum and product type to implement a LinkedList. Type can be recursive as well.

behavior of "LinkedList of 2 elements"

it should "be able to get first" in {
  Pair(1, Pair(2, End()))(0) shouldBe 1

it should "be able to get second element" in {
  Pair(1, Pair(2, End()))(1) shouldBe 2

it should "throw error Out of Boundary exception if try to get 3rd" in {
  the[Exception] thrownBy Pair(1, Pair(2, End()))(2) should have message "Out of Boundary"


You may realize that End does not have to be a case class, it doesn't have any value in it, and we just need one instance of End.

Try changing it into case object, uncomment the following case and fix the compiler errors.

package typeclass

import org.scalatest._

class `2.3.Variance` extends FlatSpec with Matchers {

behavior of "Covarian LinkedList"

it should "have the same behaviors as LinkedList" in {
  // CoPair(1, CoPair(2, CoEnd))(0) shouldBe 1
  // CoPair(1, CoPair(2, CoEnd))(1) shouldBe 2
  // the [Exception] thrownBy CoPair(1, CoPair(2, CoEnd))(2) should have message "Out of Boundary"

The way you fix the compiler error is called Covarian, which means if B is A's subtype, CoLinkedList[B] is then CoLinkedList[A]'s subtype

Here Nothing is subtype of any type, since A is covariance, End of type CoLinkedList[Nothing] become subtype of CoLinkedList[A]


Type classes

Person is a simple case class, when we want to print it nicely as JSON format, what we usually does is to create a interface e.g. JsonWriter with method toJson and implements it in Person. But if you think about it, if we need Person to have another ability e.g. HtmlWriter, you need to open Person class and implement a new interface.

However, FP does it completely different, with type classes, we can leave Person completely untouched and define it's behavior in type class, and then implicitly implement the type class for Person anywhere.

Now try not touching class Person and let it able to print as JSON and sortable by name.

package typeclass

import org.scalatest._

class `2.4.TypeClasses` extends FlatSpec with Matchers {
behavior of "Person"

it should "able to convert to JSON" in {
  JsonWriter.write(Person("o", "oyanglulu@gmail.com")) shouldBe """{"name": "o", "email": "oyanglulu@gmail.com"}"""

it should "able to sort by name" in {
  List(Person("a", "d"), Person("b", "c")).sorted shouldEqual List(
    Person("a", "d"),
    Person("b", "c"))
  List(Person("b", "c"), Person("a", "d")).sorted shouldEqual List(
    Person("a", "d"),
    Person("b", "c"))

It's easy to add the same behavior to any other type as well.

behavior of "Cat"
it should "able to convert to JSON" in {
  JsonWriter.write(Cat("Garfield", "coke")) shouldBe """{"name": "Garfield", "food": "coke"}"""

behavior of "CatPerson"

it should "be very easy to convert to JSON" in {
  JsonWriter.write(CatPerson(Person("a", "b"), Cat("Garfield", "chips"))) shouldBe """{"person":{"name": "a", "email": "b"},"cat":{"name": "Garfield", "food": "chips"}}"""

Type enrichment

With implicit class, you can magically add methods to any Type

package typeclass

import org.scalatest._

class `2.5.TypeEnrichment` extends FlatSpec with Matchers {

For example to add a new method numberOfVowels to String type, we can simply define a implicit class, and add the method there

implicit class ExtraStringMethods(str: String) {
  val vowels = Seq('a', 'e', 'i', 'o', 'u')

  def numberOfVowels =
    str.toList.filter(vowels contains _).length

When you do "the quick brown fox".numberOfVowels, Scala compiler can't find numberOfVowels in String type, but it will try to find an implicit class which has a numberOfVowels, if it can find one. Here compiler found ExtraStringMethods, then it will implicitly create an instance of ExtraStringMethods from string "the quick brown fox", so calling numberOfVowels will just work like it's builtin implemented method of String type.

it should "able to use `writeJson` method" in {
    Person("oyjc", "oyanglulu@gmail.com"),
    Cat("Hello Kitty", "rainbow")).writeJson shouldBe """{"person":{"name": "oyjc", "email": "oyanglulu@gmail.com"},"cat":{"name": "Hello Kitty", "food": "rainbow"}}"""

But, it's not generic enough, we still need to implement Cat.writeJson and Person.writeJson. How can we have a generic writeJson method which automatically works for all JsonWrite[_] type

"Cat and Person" should "also be able to use `writeJson` without any changes" in {
  import JsonWriter.Ops
  Cat("Garfield", "chips").writeJson shouldBe """{"name": "Garfield", "food": "chips"}"""
  Person("Philip", "Fry").writeJson shouldBe """{"name": "Philip", "email": "Fry"}"""



package monad

import cats.Functor
import cats.syntax.functor._
import org.scalatest._

class `3.1.Functor` extends AsyncFlatSpec with Matchers {

Function is a Typeclass that generic abstract the map behavior.

If we map a function to a List, it will apply the function to each of it's element, and return a new List. What if we need to map a function to our own custom data type, for example: Tree

behavior of "Tree"

it should "able to be map" in {
  Functor[Tree].map(Branch(Leaf(1), Leaf(2)))(_ * 2) shouldBe Branch(Leaf(2),
  Functor[Tree].map(Branch(Leaf(1), Branch(Leaf(3), Leaf(4))))(_ * 3) shouldBe Branch(
    Branch(Leaf(9), Leaf(12)))

it should "have implicit map method automatically" in {
  import Tree._
  branch(leaf(1), branch(leaf(3), leaf(4)))
    .map(_ * 3) shouldBe Branch(Leaf(3), Branch(Leaf(9), Leaf(12)))

Contravariant Functor

There's another variant of Functor with a reverse "arrow" of map, which we call it contramap

for a Functor, we have map[A, B](fa: F[A])(A=>B): F[B], contrat map reverse the "arrow"

contramap[A,B](fa: F[A])(B=>A): F[B]

which means, if you have B=>A function and a F[A], you can get a F[B]

If it's hard to understand why we need a contramap, think about if type A is printable, and you can convert B to A with function B => A, than you can say that B is also printable.

Now please implement boxPrintable using contracmap and the next spec shall pass.

behavior of "Printable"

it should "print anything that can be converted to string or int" in {
  Printable.format(Box("hill")) shouldBe "\"hill\""
  Printable.format(Box(true)) shouldBe "yes"

Identity Monad

package monad

import cats.{Monad, Id}
import cats.instances.future._
import org.scalatest._
import scala.concurrent.Future

class `3.2.IdentityMonad` extends AsyncFlatSpec with Matchers {

Monad is also a Functor, but with two more method pure and flatMap. The simplest Monad is Id Monad, which has type:

type Id[A] = A
val a = Monad[Id].pure(3)
// a: cats.Id[Int] = 3

val b = Monad[Id].flatMap(a)(_ + 1)
// b: cats.Id[Int] = 4

type of a is equal to Int as well

It seems simple but it's actually very powerful and usaful because a is now a Monad, which means you can map or flatMap it just like any Monad.

for {
  x <- a
  y <- b
} yield x + y

Now let's implement a generic sumSquare function to see how useful is Id

behavior of "Id Monad"

it should "able to calculate sum square of Future values" in {
  IdMonad.sumSquare(Future(3), Future(4)) map { result =>
    result shouldBe 25
it should "able to use Id monad to lower the type level and verify the calculation logic much more easier" in {
  IdMonad.sumSquare(Monad[Id].pure(3), Monad[Id].pure(4)) shouldBe 25

Reader Writer Monad

package monad

import org.scalatest._
import scala.concurrent.Future

class `3.3.ReaderWriter` extends AsyncFlatSpec with Matchers {

Writer Monad

Writer monad is very useful for logging, especially in a concurrent system, for example the following factorial may executed concurrently, if it's not implemented in Writer, will be something looks like this:

def factorial(n: Int): Int = {
  val ans = slowly(if(n == 0) 1 else n * factorial(n - 1))
  println(s"fact $n $ans")

if you have 2 thread runs it, the logs of factorial(3) may interleave with factorial(6), then it's hard to tell which log belongs to which calculation.

Please reimplement the factorial to return a Wrtier.

behavior of "Writer"

it should "logs are not interleave" in {
    )) map { logs =>
    logs shouldBe Vector(
      (Vector("fact 0 1", "fact 1 1", "fact 2 2", "fact 3 6"), 6),
      (Vector("fact 0 1",
              "fact 1 1",
              "fact 2 2",
              "fact 3 6",
              "fact 4 24",
              "fact 5 120",
              "fact 6 720"),

Reader Monad

One common use for Readers is dependency injection. If we have a number of operations that all depend on some external configuration.

We can simply create a Reader[A, B] from A => B using Reader.apply

Fun facts:

val catName: Reader[Cat, String] =
  Reader(cat => cat.name)
// catName: cats.data.Reader[Cat,String] = Kleisli(<function1>)

You may found that the value of a Reader is Kleisli instead of Reader, actually, Kleisli more generic form of Reader

Reader[Cat, String] is basically alias of Kleisli[Id, Cat, String]

where Kleisli is generic type represents function A => F[B].

behavior of "Reader"

val config = Readers.Db(
  Map(1 -> "Jichao", 2 -> "Ouyang"),
  Map("Jichao" -> "p4ssw0rd", "Ouyang" -> "dr0wss4p")
it should "find user's name" in {
  Readers.findUsername(1).run(config) shouldBe Some("Jichao")

it should "check password" in {
  Readers.checkPassword("Jichao", "p4ssw0rd").run(config) shouldBe true

it should "check login" in {
  Readers.checkLogin(2, "dr0wss4p").run(config) shouldBe true

State Monad

Same as a Writer Monad providing atomic logging, a State Monad will provide you thread safe atomic state operations.

Regardless it's name is State, it's pure functional, lazy and immutable operations.

Very similar to Reader, you can use State.apply to create a State Monad

State[Int, String](state => (state, "result"))

the differences from Reader is that it return a tuple which includes the new state.

package monad

import org.scalatest._

class `3.4.State` extends AsyncFlatSpec with Matchers {
behavior of "State"

it should "eval Int" in {
  States.evalOne("42").runA(Nil).value shouldBe 42

it should "eval and calculate" in {
  import States._
  val calculator = for {
    _ <- evalOne("1")
    _ <- evalOne("2")
    ans <- evalOne("+")
  } yield ans
  calculator.runA(Nil).value shouldBe 3

it should "eval a list of expr" in {
  import States._
  val calculator = evalAll(List("1", "2", "+", "3", "*"))
  calculator.runA(Nil).value shouldBe 9

it should "be pure and composable" in {
  import States._
  val calculator = for {
    _ <- evalAll(List("1", "2", "+"))
    _ <- evalAll(List("3", "4", "+"))
    ans <- evalOne("*")
  } yield ans
  calculator.runA(Nil).value shouldBe 21

Monad Transformer

package monad

import org.scalatest._

class `3.5.MonadTransformer` extends AsyncFlatSpec with Matchers {
type ErrorOr[A] = Either[String, A]
val ihave10:ErrorOr[Int] = Right(Some(10)

If I just want to map 10 in side Right and Some, I have to map a function and inside which map again

ihave10.map(r => r.map(_ + 1))

If you have a OptionT, which is the Monad Transformer for Option, things will be lot easier

val ihaveOneMore = OptionT[ErrorOr, Int](ihave10).map(_ + 1)

if you map on the OptionT, it will transfer the map to the Option type inside ErrorOr

Please implement getPowerLevel to return a EitherT, you may find companion object EitherT useful to create a EitherT.

it should "get Bumblebee's power lever" in {
  Transformer.getPowerLevel("Bumblebee").value map { level =>
    level shouldEqual Right(8)

it should "not able to reach Smurf" in {
  Transformer.getPowerLevel("Smurf").value map { level =>
    level shouldEqual Left("Smurf unreachable")

Two autobots can perform a special move if their combined power level is greater than 15. Implement canSpecialMove method, you'll find out why we need a Monad Transformer here.

it should "get special move when Bumblebee and Hot Rod together" in {
  Transformer.canSpecialMove("Bumblebee", "Hot Rod").value map { level =>
    level shouldEqual Right(true)

it should "not get special move when Bumblebee and Jazz together" in {
  Transformer.canSpecialMove("Bumblebee", "Jazz").value map { level =>
    level shouldEqual Right(false)

Finally, write a method tacticalReport that takes two ally names and prints a message saying whether they can perform a special move.

it should "return a nice msg when Bumblebee and Hot Rod together" in {
  Transformer.tacticalReport("Bumblebee", "Hot Rod") shouldBe "Bumblebee and Hot Rod are ready to roll out!"

it should "return a nice msg when Bumblebee and Jazz together" in {
  Transformer.tacticalReport("Bumblebee", "Jazz") shouldBe "Bumblebee and Jazz need a recharge."

it should "return a error msg when Bumblebee and Smurf together" in {
  Transformer.tacticalReport("Bumblebee", "Smurf") shouldBe "Comms error: Smurf unreachable"

Semigroupal a.k.a Cartesian

package monad

import cats._
import cats.instances.option._
import org.scalatest._
import scala.concurrent.Future

class `3.6.Semigroupal` extends AsyncFlatSpec with Matchers {

Semigroupal is a type class that allows us to combine contexts with method product

trait Semigroupal[F[_]] {
  def product[A, B](fa: F[A], fb: F[B]): F[(A, B)]

If we have a F[A] and F[B], product method can combine them into F[(A, B)]

behavior of "Semigroupal"

it should "join 2 contexts" in {
  Semigroupal[Option].product(Some(123), Some("abc")) shouldBe Some(
    (123, "abc"))

it should "join 3 contexts" in {
  Semigroupal.tuple3(Option(1), Option(2), Option(3)) shouldBe Some((1, 2, 3))

Semigroupal has predefined up to tuple22, the same size as tuple.

There is also a shortcut syntax for tupleN from cats.syntax.apply

import cats.syntax.apply._
(Option(1), Option(2), Option(3)).tupled

Try create a Cat with some Future value using tupled and map:

it should "create Cat from Future value" in {
                                 Future("Lasagne")) map { cat =>
    cat shouldBe Cat("Garfield", 1978, "Lasagne")


Hint: There is also a shortcut for tupled and mapmapN from cats.syntax.apply

package monad

import cats.data.Validated.{Invalid, Valid}
import org.scalatest._

class `3.7.Validated` extends AsyncFlatSpec with Matchers {

Either is a fail fast data type, which means if something goes wrong, it will skip everything else. But when it comes to a senario of validationg form, we would rather validate everything and return all invalid message at one go.

behavior of "create Cat from form input"
it should "check empty input " in {
  SemiNAppli.createCatFromForm(Map()) shouldBe Invalid(
    List("name field not specified",
         "birth field not specified",
         "food field not specified"))

it should "check birth is a digit" in {
  SemiNAppli.createCatFromForm(Map("birth" -> "not a number")) shouldBe Invalid(
    List("name field not specified",
         "invalid birth For input string: \"not a number\"",
         "food field not specified"))

it should "check blank" in {
  SemiNAppli.createCatFromForm(Map("name" -> "", "birth" -> "not a number")) shouldBe Invalid(
    List("name should not be blank",
         "invalid birth For input string: \"not a number\"",
         "food field not specified"))

it should "create a Cat" in {
  SemiNAppli.createCatFromForm(Map("name" -> "Garfield",
                                   "birth" -> "1978",
                                   "food" -> "Lasagne")) shouldBe Valid(
    Cat("Garfield", 1978, "Lasagne"))

behavior of "Apply.ap"
it should "be the same as mapN" in {
  SemiNAppli.applyCat(Map("name" -> "Garfield",
                          "birth" -> "1978",
                          "food" -> "Lasagne")) shouldBe Valid(
    Cat("Garfield", 1978, "Lasagne"))


All Traversable need to be Foldable, but Traversable provide a more convenient, more powerful pattern for iteration. Let's say we have a list of hosts and we need to check if all of them are up and running well.

package monad

import org.scalatest._

class `3.8.Traverse` extends AsyncFlatSpec with Matchers {
val hostnames = List(
def getUptime(hostname: String): Future[Int] =
  Future(hostname.length * 60)

How would you implement a allUptimes method to fetch each of the server and then return a Future[List[Int]]?

We could fold the list from Future of course

def allUptimes(hosts: List[String]): Future[List[Int]] = {
    hosts.foldLeft(Future(List.empty[Int])) {
      (accum, host) =>
      val uptime = getUptime(host)
      for {
        accum  <- accum
        uptime <- uptime
      } yield accum :+ uptime

If we can traverse the list with String => Future[Int], it would be much more concise and eligant.

Hint: using Future.traverse

behavior of "Uptime robot"

it should "check each host's uptime" in {
  UptimeRobot.allUptimes(hostnames) map { result =>
    result shouldBe List(1020, 960, 840)

With traverse and identity, you can easily just create another very useful function sequence

def sequence[G[_]: Applicative, B](inputs: F[G[B]]): G[F[B]]  = traverse(inputs)(identity)

which is very useful e.g. you want to convert a List[Future[?]] to Future[List[?]]

The Uptime Robot in previous implementation was checking uptime synchronously, let's make it asynchronously

it should "check hosts asynchronously" in {
  UptimeRobot.asyncGetUptimes(hostnames.map(UptimeRobot.getUptime)) map {
    result =>
      result shouldBe List(1020, 960, 840)



usually we deal with function more often, we're so familiar with A => B

says if we have two function A => C and B => C

how can we compose them into a single function that can take either A or B and produce a C?

in Scala the return type will be like Either[A, B] => C

This is exactly Choice typeclass for, replacing => with F, you will get a Choice

trait Choice[F[_, _]] {
  def choice(fac: F[A, C], fbc: F[B, C]): F[Either[A, B], C]


A very useful case of Choice typeclass would be like middleware in HTTP server.

Take Http4s for example:


http4s defined routes using Kleisli

type HttpRoutes[F[_]] = Kleisli[OptionT[F, ?], Request[F], Response[F]]
def routes[F[_]]: HttpRoutes[F] = ???

But before going through routes, most request must pass middleware to ensure the request has correct or not.

A authentication middleware could end up with 2 kinds of result

  1. return Unauthorized instantly while token is invalid
  2. Pass Request[F] through if token if valid

So the return type of middleware will be like Either[Response[F], Request[F]]


if we define middleware like

type Middleware[F[_]] = Kleisli[OptionT[F, ?], Request[F], Either[Response[F], Request[F]]]
val passThrough: Kleisli[OptionT[F, ?], Response[F], Response[F]] = Kleisli.ask[OptionT[F, ?], Response[F]]
def middleware[F[_]]: Middleware[F] = ???

Compose middleware and routes together is now easy thanks to Kleisli has instance of Choice

middleware andThen passThrough.choice(routes)