Grokking Monad in Scala - Free

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
}

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

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

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:

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

}

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

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

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

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.

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