Grokking Monad in Scala

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.

}

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 {
  pending
  // 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]

}

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"}}"""
}

}

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 {
  CatPerson(
    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),
                                                                     Leaf(4))
  Functor[Tree].map(Branch(Leaf(1), Branch(Leaf(3), Leaf(4))))(_ * 3) shouldBe Branch(
    Leaf(3),
    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)))
}

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"
}

}

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
}

}

package monad

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

class `3.3.ReaderWriter` extends AsyncFlatSpec with Matchers {

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

behavior of "Writer"

it should "logs are not interleave" in {
  Future.sequence(
    Vector(
      Future(Writers.factorial(3).run),
      Future(Writers.factorial(6).run)
    )) 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"),
       720)
    )
  }
}

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

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
}

}

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
}

}

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"
}

}

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 {
  SemiNAppli.createCatFromFuture(Future("Garfield"),
                                 Future(1978),
                                 Future("Lasagne")) map { cat =>
    cat shouldBe Cat("Garfield", 1978, "Lasagne")
  }
}

}

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(
  "alpha.example.com",
  "beta.example.com",
  "gamma.demo.com"
)

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.

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:

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

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] = ???

middleware andThen passThrough.choice(routes)