# Grokking Monad in Scala

This is the literal programming file that generates

`3-*.scala`

files hereyou 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"
}
```

```
}
```

### Variance

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]`

```
}
```

### 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 {
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"}"""
}
```

```
}
```

## Monad

### Functor

```
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)))
}
```

#### 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")
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 {
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)
)
}
}
```

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

```
}
```

### Validated

Hint: There is also a shortcut for

`tupled`

and`map`

–`mapN`

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

```
}
```

### Traverse

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.

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)
}
}
```

```
}
```

## Choice

### Rationale

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]
}
```

### Applied

A very useful case of `Choice`

typeclass would be like middleware in
HTTP server.

Take Http4s for example:

#### HttpRoutes[F]

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

- return
`Unauthorized`

instantly while token is invalid - Pass
`Request[F]`

through if token if valid

So the return type of `middleware`

will be like
`Either[Response[F], Request[F]]`

#### Middleware[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)
```