Free monad example 1

free-monad-example-1.scala

/*
https://typelevel.org/cats/datatypes/freemonad.html

Free your ADT

There are five basic steps to "freeing" the ADT:

1 Create a type based on Free[_] and KVStoreA[_].
2 Create smart constructors for KVStore[_] using liftF.
3 Build a program out of key-value DSL operations.
4 Build a compiler for programs of DSL operations.
5 Execute our compiled program.

 */

sealed trait KVStoreA[A]

case class Put[T](key: String, value: T) extends KVStoreA[Unit]

case class Get[T](key: String) extends KVStoreA[Option[T]]

case class Delete(key: String) extends KVStoreA[Unit]



// 1. Create a Free type based on your ADT

import cats.free.Free
import cats.free.Free.compile

type KVStore[A] = Free[KVStoreA, A]


//2. Create smart constructors using liftF
// These methods will make working with our DSL a lot nicer, and will lift KVStoreA[_] values into our KVStore[_] monad
// (note the missing "A" in the second type).

import cats.free.Free.liftF

// Put returns nothing (i.e. Unit).
def put[T](key: String, value: T): KVStore[Unit] =
  liftF[KVStoreA, Unit](Put[T](key, value))

// Get returns a T value.
def get[T](key: String): KVStore[Option[T]] =
  liftF[KVStoreA, Option[T]](Get[T](key))

// Delete returns nothing (i.e. Unit).
def delete(key: String): KVStore[Unit] =
  liftF(Delete(key))

// Update composes get and set, and returns nothing.
def update[T](key: String, f: T => T): KVStore[Unit] =
  for {
    vMaybe <- get[T](key)
    _ <- vMaybe.map(v => put[T](key, f(v))).getOrElse(Free.pure(()))
  } yield ()

// 3. Build a program
//Now that we can construct KVStore[_] values we can use our DSL to write "programs" using a
//for -comprehension:

def program: KVStore[Option[Int]] =
  for {
    _ <- put("wild-cats", 2)
    _ <- update[Int]("wild-cats", (_ + 12))
    _ <- put("tame-cats", 5)
    n <- get[Int]("wild-cats")
    _ <- delete("tame-cats")
  } yield n

/*
4. Write a compiler
for your program


As you may have understood now, Free[_] is used to create an embedded DSL .By itself, this DSL only represents a
sequence of operations (defined by a recursive data structure); it doesn't produce anything. Free[_] is a programming
language inside your programming language!

So, like any other programming language, we need to compile our abstract language into an effective language and then
run it.

To do this, we will use a natural transformation between type containers. Natural transformations go between types
like F[_] and G[_](this particular transformation would be written as FunctionK[F, G] or as done here using the
symbolic alternative as F ~> G).

In our case, we will use a simple mutable map to represent our key value store:

*/

import cats.arrow.FunctionK
import cats.{Id, ~>}
import scala.collection.mutable

// The program will crash if a type is incorrectly specified.
// KVStoreA ~> Id is an alias for FunctionK[KVStoreA, Id]
def impureCompiler: KVStoreA ~> Id =
  new(KVStoreA ~> Id) {

    // a very simple (and imprecise) key-value store
    val kvs = mutable.Map.empty[String, Any]

    def apply[A](fa: KVStoreA[A]): Id[A] =
      fa match {
        case Put(key, value) =>
          println(s"put($key, $value)")
          kvs(key) = value
          Id(())
        case Get(key) =>
          println(s"get($key)")
          kvs.get(key).asInstanceOf[A]
        case Delete(key) =>
          println(s"delete($key)")
          kvs.remove(key)
          Id(())
      }
  }

//5. Run program
/*
Free[_] is just a recursive structure that can be seen as sequence of operations producing other operations. In this 
way it is similar to List[_]. We often use folds (e.g. foldRight) to obtain a single value from a list; this recurses 
over the structure, combining its contents.

The idea behind running a Free[_] is exactly the same. We fold the recursive structure by:

* consuming each operation.
* compiling the operation into our effective language using impureCompiler (applying its effects if any).
* computing next operation.
* continue recursively until reaching a Pure state, and returning it.

*/

program.foldMap(impureCompiler)
//put(wild-cats, 2)
//get(wild-cats)
//put(wild-cats, 14)
//put(tame-cats, 5)
//get(wild-cats)
//delete(tame-cats)