# Grokking Monad in Scala - Free

This is the literal programming file that generates 4-1-kind.scala and 4-2-free.scala

you can actually run

`sbt "testOnly *Kind"`

and`sbt "testOnly *Free"`

for exercises

## Kind

```
package free
import monad._
import cats._
import org.scalatest._
class `4-1-Kind` extends AsyncFlatSpec with Matchers {
```

Kinds are types for types. Like a function for parameters of type and return a type.
e.g. `List[_]`

is a Kind, it has a `hole`

represented as `_`

in it, which is like parameter in function.
If you fill the hole with a type `String`

, then you will get a type `List[String]`

.

Recall our `Printable[_]`

kind defined in `3.1.Functor`

, we'vecreatede implement of typeclass `Contravariant`

over kind `Printable`

, which means no matter what type you fill into the hole of `Printable[_]`

, it should
fulfill constrain of typeclass `Contravariant`

.

You can also define a function over Kind `F[_] -> G[_]`

, which is called *FunctionK* , just like function over type.

### FunctionK

to define a FuntionK in cats, we can simply use fish arrow `~>`

e.g. a FuntionK from `List`

to `Option`

```
import cats.~>
val first = new (List ~> Option) {
def apply[A](l:List[A]): Option[A] = l.headOption
}
```

### Kind Projector

you'll notice that we've include a compiler plugin `kind-projector`

https://github.com/non/kind-projector
in `build.sbt`

it provides us pretty syntactic suger for such case

```
val first = Lambda[List ~> Option](_.headOption)
```

which will be expanded to exactly the same code as what we defined before.

```
behavior of "FunctionK"
it should "create a FunctionK from Box[_] to Sphere[_]" in {
Printable.format(Sphere("hill")) shouldBe "\"hill\""
}
```

### Rank N Type

But why this is useful than function, the `fnk`

in `spherePrintable`

can be easily replace with a
simple function and it should behave still the same.

```
implicit def spherePrintable[A](implicit p: Printable[Box[A]],
fn: Sphere[A] => Box[A]): Printable[Sphere[A]] = ???
```

let's create another function that use `Sphere ~> Box`

, to make tuple of sphere `(Sphere[String], Sphere[Int])`

printable

```
implicit def tuplePrintable[A, B, C](
implicit p: Printable[Box[String]],
fn: Sphere[C] => Box[C])): Printable[(Sphere[A], Sphere[B])] = {
val tupleOfSphereToBox = (tupleOfSphere: (Sphere[A], Sphere[B])) => {
val box1 = fn(tupleOfSphere._1)
val box2 = fn(tupleOfSphere._2)
Box(s"(${box1.value}, ${box2.value})")
}
Contravariant[Printable].contramap(p)(tupleOfSphereToBox)
}
```

you will get some compile error as such

[error] /Users/jichao.ouyang/Develop/scala-dojo/src/main/scala/Free.scala:21:35: type mismatch; [error] found : free.Sphere[A] [error] required: free.Sphere[C] [error] val box1 = fn(tupleOfSphere._1) [error] ^ [error] /Users/jichao.ouyang/Develop/scala-dojo/src/main/scala/Free.scala:22:35: type mismatch; [error] found : free.Sphere[B] [error] required: free.Sphere[C] [error] val box2 = fn(tupleOfSphere._2) [error] ^

Apparently when your `fn`

is sticked to a `C`

type, it's not convertible to neither A nor B type, even if you stick it
to `A`

type, then the `tupleOfSphere._2`

can't convert to `A`

either.

This is *Rank 1 Type*, because all types A, B, C are fixed in the same rank of `tuplePrintable`

's polymorphism.

To make such code compile, you'll need to make `fn`

as `Rank 2 Type`

, which means `fn`

will not be fixed in the first rank of `tuplePrintable`

polymorphism, it's type polymorphism will be in another rank totally independent from the `tuplePrintable`

```
behavior of "Rank N Type"
it should "able to print a tuple of Sphere" in {
Printable.format((Sphere("hill"), Sphere(1))) shouldBe "\"(hill, 1)\""
}
```

### Natural Transformation

If your kinds are happened to be a Functor, then this functionK becomes *Natural Transformation*

There's nothing different except that Natural Transformation will provide you a property:

applying FunctionK before or after a Functor

`map`

makes no difference

hence `fnk(fa.map(f))`

is exactly the same as `fnk(fa).map(f)`

```
"Natural Transformation" should "satisfy law" in {
implicit val functorBox: Functor[Box] = new Functor[Box] {
def map[A, B](fa: Box[A])(f: A => B) =
Box(f(fa.value))
}
import cats.syntax.functor._
Sphere.sphereToBox(Sphere(100).map(_ + 1)) shouldBe Sphere.sphereToBox(Sphere(100)).map(_ + 1)
}
```

```
}
```

## Free

```
package free
import org.scalatest._
import cats._
import cats.effect.IO
class `4-2-Free` extends AsyncFlatSpec with Matchers {
```

*Free Monad* means you can get a ** free** monad from any

`Functor`

### Free Structure

A Free Structure is basically very similar to `Cons`

and `Nil`

of
`List`

, we call such similarity *Isomorphic*

```
seal trait Free[S[_], A]
final case class Pure[S[_], A](a: A) extends Free[S, A]
final case class Suspend[S[_], A](a: S[Free[S,A]]) extends Free[S, A]
```

`Pure`

is like `Nil`

representing the end of structure, and `Suspend`

to `Cons`

means there is something else left behind.

To make it a Monad, which could be something like

```
implicit def catsFreeMonadForFree[S[_]](implicit F:Functor[S]): Monad[Free[S, ?]] =
new Monad[Free[S, ?]] {
def pure[A](a: A): Free[S, A] = Pure(a)
def map[A, B](fa: Free[S, A])(f: A => B): Free[S, B] = fa.flatMap(a=>Pure(f(a)))
def flatMap[A, B](a: Free[S, A])(f: A => Free[S, B]): Free[S, B] = a match {
case Pure(a) => f(a)
case Suspend(a) => Suspend(F.map(a)(next=>next.flatMap(f)))
}
}
```

while you probably noticed that we need `S`

to be a `Functor`

first, so that we can
`map`

it's next step and continuous `flatMap`

### CoYoneda Lemma (Trick)

The problem becomes "how can we get a free functor from any `S[_]`

?" then

This is when we need to introduce *CoYoneda Lemma*:

A `CoYoneda[F[_], A]`

consists of two things

- a function
`B => A`

- a
`F[B]`

Since `B`

can share the same polymorphism of `A`

and `F`

, they are in the same rank
hope you still remember what "rank" is from 4-1-kind
}
, so we
can simply add `B`

into the type parameter of `CoYoneda`

as well, thus it becomes `CoYoneda[F[_], A, B]`

,
which we could simply represent it as scala case class:

```
case class CoYoneda[F[_], A, B](fb: F[B], f: B => A)
```

And define a functor over CoYoneda is very straightforward:

```
implicit def functorForCoyoneda = new Functor[CoYoneda[F, ?, B]] {
def map[A, C](fa:CoYoneda[F, A, B])(f: A=>C): CoYoneda[F, C, B] {
CoYoneda(fa.fb, (f compose fa.f)) // (f compose fa.f) has type B => C
}
}
```

It's actully very similar to *Continuation Passing Style*, which just continous composing function
`f`

to the function inside CoYoneda.

Now we know how to map over a `CoYoneda`

, but how can we get a `CoYoneda`

from any `F[_]`

?

*CoYoneda Lemma* (Trick)

The trick is to use the magical `identity`

function `A=>A`

, then we'll get a `CoYoneda[F, A, A]`

from any `F[_]`

, and eventually, `F[_]`

become a Functor because any `CoYoneda`

is Functor.

```
def lift[F[_], A](fa: F[A]):CoYoneda[F, A, A] =
CoYoneda(fa, identity:A=>A)
```

To construct a Free Monad, we can use the CoYoneda Trick to lift any `F[_]`

, and put the CoYoneda to Free.

```
def liftF[F[_], A](value: F[A]): Free[F, A] = Suspend(lift(value))
```

### Effects

Let's forget about CoYoneda
it's totally fine if you didn't follow, you don't actually need to understand how Free is implemented to use it.
for now, I'm gonna show you how easy to use cat's Free
Free Monad from cats already embedded CoYoneda trick in it's implementation, namely `Flatmaped`

.
to free your ADT and get a free program
then, separate your effect from the core business logic.

Imagine we have a document database to query, it's easy to abstract 3 method on it:

`get(key: String)`

`put(key: String, value: String)`

`delete(key: String)`

```
object Database {
def get(key: String): String = {
println("querying database")
s"value for key $key"
}
def put(key: String, value: String) ={
println(s"saving $key to database")
}
def delete(key: String) = {
println(s"deleteing $key")
}
}
```

All of these actions are actually effects, because they will potentially cause some state changes outside the scope where the method is executed.

While testing those methods could be a nightmare as well, you have to either setup a real database or mock these methods' implementation

```
behavior of "program"
it should "hard to unit test get put delete" in {
program() shouldBe (())
}
```

You will find it's too hard to mock a `object`

, so the test could end up with a integration test which require real database, or refactor `Database`

to a normal class so you can mock it properly.

It's hard to test because:

- imperative: when you call the method, the effect actually happen
- stateful: the effect and result depends on database, which is out of the scope of
`Database`

To make your program more declarative and testable, we can describe all database interactions using ADT

```
sealed trait DbEff[A]
case class Put(key: String, value: String) extends DbEff[Unit]
case class Get(key: String) extends DbEff[String]
case class Delete(key: String) extends DbEff[Unit]
```

All these ADTs is just describing what kind of behavior a database can provide, and what value they should return.

no database interaction will actually happen when you construct those ADTs

### Free your program

to lift those ADTs into Free, simply using `liftF`

here we're using cats free implementation, which already have CoYoneda embedded in `Free`

implementation, so we don't need to `lift`

the value to `CoYoneda`

our self.
we've introduced in CoYoneda Lemma (Trick)

```
object DbEff {
def get(key: String): Free[DbEff, String] = Free.liftF[DbEff, String](Get(key))
def put(key: String, v: String): Free[DbEff, Unit] = ???
def delete(key: String): Free[DbEff, Unit] = ???
}
```

`put`

and `delete`

should be pretty much the same

to lift your `program`

defined before to free, the simplest trick is to change all `=`

to `<-`

and remove `val`

```
object program { object freeProgram {
def apply() = { val oldKey = "123"
val oldKey = "123" def apply() = for {
val oldVal = Database.get(oldKey) oldVal <- DbEff.get(oldKey)
val newVal = s"this is new: $oldVal" newVal = s"this is new: $oldVal"
val newKey = oldKey.reverse newKey = oldKey.reverse
Database.put(newKey, newVal) _ <- DbEff.put(newKey, newVal)
Database.delete(oldKey) _ <- DbEff.delete(oldKey)
} } yield ()
} }
```

Just like that, every thing just lifted in to Free, instead of actually querying the database.

### Interpret your program

Since our program is organized, we can define an interpreter just for test, without actually talk to database, but
simulating the interactions between your program and database.
remember the `Lambda`

trick from Kind Projector ?

```
object DbEffInterp {
val fake = Lambda[DbEff ~> IO](_ match {
case Get("123") => IO(s"value for key 123")
case Put("321", v) => IO(println(s"saving 123 to database"))
case Delete("123") => IO(println(s"deleteing 123"))
case a => IO(fail(s"unexpecting interaction: $a"))
})
}
```

So, if you `foldMap`

your program over the interpreter

```
behavior of "free program"
it should "run on fake interpreter to verify your program logic" in {
(freeProgram() foldMap DbEffInterp.fake) unsafeRunSync () shouldBe (())
}
```

A nice message will tell you when `sbt "testOnly *Free"`

[info] - should run on fake interpreter to verify your program logic *** FAILED *** [info] unexpecting interaction: Delete(321) (4-2-free.scala:17)

You'll know what to fix, seems we have some business bug in `freeProgram`

### TODO What really happened here

## Footnotes:

^{2}

hope you still remember what "rank" is from 4-1-kind

```
}
```

^{3}

it's totally fine if you didn't follow, you don't actually need to understand how Free is implemented to use it.

^{4}

Free Monad from cats already embedded CoYoneda trick in it's implementation, namely `Flatmaped`

.

^{5}

here we're using cats free implementation, which already have CoYoneda embedded in `Free`

implementation, so we don't need to `lift`

the value to `CoYoneda`

our self.

^{6}

remember the `Lambda`

trick from Kind Projector ?