47 Degrees joins forces with Xebia read more

FP for Beginners - III - Applications as Coproducts of Free Algebras

FP for Beginners - III - Applications as Coproducts of Free Algebras

Previously, in the second edition of our Beginners series, we introduced you to Monad Transformers, a useful construct to monadically compute with nested structures such as Future[Option[_]]. This time, we’re going to tackle Free Monads and how you may rely on them to build and structure Applications.

Free Monads

For the purpose of this article, a Free Monad is a data type that allows the decoupling of program declaration from program interpretation. This means you can use Free monads and Free applicatives to completely describe a program’s business logic. You can describe both sequential and parallel operations as well as their interactions without having to provide an implementation. When you need to execute the logic you can provide a decoupled and cleanly abstracted implementation for that particular execution.

ADTs as verbs

First, you’ll need to describe the operations your program will perform.

sealed trait Interact[A]
case class Ask(prompt: String) extends Interact[String]
case class Tell(msg: String) extends Interact[Unit]

In the ADT above, each node in the ADT represents verbs or actions that your Application exposes through it’s API. Each one of the operations exposes the type of input arguments and what outputs they produce. In this way, asking the user for a value requires a prompt message Ask(prompt: String) and will return a value once the user provides the input extends Interact[String].

Smart constructors

Once you have the operations defined you can lift them via “smart constructors” to the context of Free with Free#liftF, which is what you will ultimately use to write your program.

import cats.free._

object InteractOps {
	def ask(prompt: String) : Free[Interact, String] =
		Free.liftF[Interact, String](Ask(prompt))

	def tell(msg: String) : Free[Interact, Unit] =
		Free.liftF[Interact, Unit](Tell(msg))
}

There is a lot going on behind the scenes, but basically, we are getting Free monads out of our ADT. If you are interested in the details on how Free Monads work internally and how they are defined from a Category Theory perspective check out the Free Monads Cats Tutorial.

Now that you have smart constructors wrapping your ADT, we can write a program like this:

import InteractOps._

val program = for {
	cat <- ask("What's the kitty's name?")
	_ <- tell(s"You said $cat")
} yield ()

There’s one issue here. There isn’t an implementation for Ask and Tell yet! At this point, your program is nothing but a tree-like structure:

Gosub(
	Suspend(
		Ask(What's the kitty's name?)),
		...)

Behind the scenes, each time flatMap is invoked through the use of for comprehensions, the tree continues to grow by chaining operations that will be performed sequentially down the road once they’ve been evaluated.

In order to evaluate this Free structure, you need to provide an interpreter. An interpreter in the context of Free Monads is a function called a Natural Transformation.

A Natural Transformation, also seen in the wild as ~>, is a function that can transform the initial ADT based operations into an actual value wrapped by a target runtime Monad. It’s easier done than said.

import cats.{Id, ~>}

def interpreter : Interact ~> Id = new (Interact ~> Id) {
	def apply[A](fa: Interact[A]) : Id[A] = fa match {
		case Ask(prompt) => println(prompt); readLine
		case Tell(msg) => println(msg)
	}
}

title

In the example above, Id was used as a target monad which does nothing but wrap an actual value. This is to conform to the process of performing a Natural Transformation, where you go from one type constructor to another, literally transforming from a container type F[_] to container type G[_]. You may choose any other Monad like container in your impl such as Task, Future, Option…

Finally, you can evaluate your program like this:

val evaluated = program foldMap interpreter
scala> What's the kitty's name? <Waits for user input>
You said Tom

Hopefully, this basic program gives you an idea on how Free works and how it’s an incredibly useful datatype to decouple Biz Logic not just from implementation, but also runtime interpretation.

Composing ADTs

As you use algebraic design throughout your Application and start building biz logic actions around Free Algebras, you will quickly run into the need to define more than just one algebra. This is paramount to building apps on top of Free. Each ADT will end up being a branch of the Tree, which is your Application.

Multiple ADTs will quickly make you realize that unrelated Monads do not compose.

To see what we are talking about, let’s add a new ADT that will take care of providing meaning and actions related to persistence to the application.

sealed trait DataOp[A]
case class AddCat(a: String) extends DataOp[String]
case class GetAllCats() extends DataOp[List[String]]

object DataOps {
	def addCat(a: String): Free[DataOp, String] = Free.liftF[DataOp, String](AddCat(a))
	def getAllCats: Free[DataOp, List[String]] = Free.liftF[DataOp, List[String]](GetAllCats())
}

Now that you have two ADT’s, let’s try to combine their operations in a meaningful way.

import InteractOps._, DataOps._

val program = for {
	cat <- ask("What's the kitty's name?")
	addedCat <- addCat(cat)
	_ <- tell(s"$addedCat has been stored")
} yield ()

Compilation Failed
Main.scala:292: type mismatch;
found   : cats.free.Free[cmd5.Interact,Unit]
required: cats.free.Free[cmd10.DataOp,?]
_ <- tell(s"$addedCat has been stored")
^
Main.scala:291: polymorphic expression cannot be instantiated to expected type;
found   : [B]cats.free.Free[cmd10.DataOp,B]
required: cats.free.Free[cmd5.Interact,?]
addedCat <- addCat(cat)

So, a Free[DataOp, ?] can’t be composed with Free[Interact, ?]. That’s because while they’re in the context of Free, they are not parametericed by the same type constructor, but by two unrelated ones that are not part of the same ADT.

Applications as Coproduct of Algebras

Fear not! The Inject type class described by Swierstra in Data types à la carte lets you compose different algebras in the context of Free. It does so by building on top of Coproduct which is then utilized as a new unique parameterized type constructor where the smart constructors can rely on uniformity when composing dispair ADTs.

What is a Coproduct anyway?

In the same way we think of Either, Xor, \/ as disjoint unions of A or B, a Coproduct can be seen as a disjoint union in the Category of sets. Wait, what? For the purpose of this post, think of a Coproduct as the disjoint union of F[_] and G[_], so similar to Xor but for type constructors. You can use the Coproduct data type to build a recursive type level tree of all the nested operations defined in the ADTs.

So if an application is a group of algebraic data types describing the core actions, we can also state that In the context of Free, an Application is the Coproduct of it’s algebras. And after such a bold statement let us just write that…

import cats.data.Coproduct

type Application[A] = Coproduct[Interact, DataOp, A]

Once you have a type alias pointing to a type constructor representing your app, you can parameterize your smart constructors so they are suitably adapted to this new structure when instantiated.

class Interacts[F[_]](implicit I: Inject[Interact, F]) {
	def tell(msg: String): Free[F, Unit] = Free.inject[Interact, F](Tell(msg))
	def ask(prompt: String): Free[F, String] = Free.inject[Interact, F](Ask(prompt))
}

object Interacts {
	implicit def interacts[F[_]](implicit I: Inject[Interact, F]): Interacts[F] = new Interacts[F]
}

class DataOps[F[_]](implicit I: Inject[DataOp, F]) {
	def addCat(a: String): Free[F, String] = Free.inject[DataOp, F](AddCat(a))
	def getAllCats: Free[F, List[String]] = Free.inject[DataOp, F](GetAllCats())
}

object DataOps {
	implicit def dataOps[F[_]](implicit I: Inject[DataOp, F]): DataOps[F] = new DataOps[F]
}

The two primary changes above are the parameterization of both Interacts and DataOps classes to F[_], and the replacement of Free#liftF for Free#inject.

Parameterizing the smart constructors to F[_] allows you to obtain Free monads on demand that are parameterized to the same Functor, which in this case is the Application.

Free#inject gives you the same functionality as liftF, but it requires an Inject instance available. This instance is responsible for injecting the operation inside a Coproduct.

def program(implicit I: Interacts[Application], D: DataOps[Application]): Free[Application, Unit] = {

	import I._, D._

	for {
		cat <- ask("What's the kitty's name?")
		_ <- addCat(cat)
		cats <- getAllCats
		_ <- tell(cats.toString)
	} yield ()

}

Now that you can compose operations and build full program definitions, you need to align the interpreters. The single interpreter used before previously had shape of Interact ~> Id but now that you are combining ADTs inside a Coproduct, you need your interpreter to have the shape of Application ~> Id.

Similar to how the ADTs line up in the Coproduct:

type Application[A] = Coproduct[Interact, DataOp, A]

You need to align all of your interpreters and compose them, so the runtime evaluation strategy is a mirror of the program definition.

object InteractInterpreter extends (Interact ~> Id) {
	def apply[A](i: Interact[A]) = i match {
		case Ask(prompt) => println(prompt); readLine()
		case Tell(msg) => println(msg)
	}
}

object InMemoryDataOpInterpreter extends (DataOp ~> Id) {
	private[this] val memDataSet = new ListBuffer[String]

	def apply[A](fa: DataOp[A]) = fa match {
		case AddCat(a) => memDataSet.append(a); a
		case GetAllCats() => memDataSet.toList
	}
}

val interpreter: Application ~> Id = InteractInterpreter or InMemoryDataOpInterpreter

Notice the order matches left to right, Coproduct ADTs definition with interpreters or composition.

In the same fashion, if you had more Algebras you could continue stacking them like so:

type C01[A] = Coproduct[Interact, DataOp, A]
type Application[A] = Coproduct[OneMoreADT, C01, A]

val c01Interpreter: C01 ~> Id = InteractInterpreter or InMemoryDataOpInterpreter
    val interpreter: Application ~> Id = OneMoreADTInterpreter or c01Interpreter

title Remember, we are only using Id[_] as the target Monad for illustrative purposes. In real world scenarios, you may want to lift it to an effect capturing monad such as Task.

Abstracting over results

If you want extra flexibility, or selective behavior at runtime you can even leave the interpreters parameterized to M[_]. This allows the user to compute in the context of any arbitrary type constructor for which an Capture instance is found. Capture in this context is for data types that can capture an effectful computation and accordingly deal with exceptions.

import simulacrum.typeclass

@typeclass trait Capture[M[_]] {
  def capture[A](a: => A) : M[A]
}

class Interpreters[M[_]: Capture] {

	def InteractInterpreter: Interact ~> M = new (Interact ~> M) {
		def apply[A](i: Interact[A]) = i match {
			case Ask(prompt) => Capture[M].capture({println(prompt); readLine()})
			case Tell(msg) => Capture[M].capture({println(msg)})
		}
	}

	def InMemoryDataOpInterpreter : DataOp ~> M = new (DataOp ~> M) {
		private[this] val memDataSet = new ListBuffer[String]

		def apply[A](fa: DataOp[A]) = fa match {
			case AddCat(a) => Capture[M].capture({memDataSet.append(a); a})
			case GetAllCats() => Capture[M].capture(memDataSet.toList)
		}
	}

	def interpreter: Application ~> M =
		InteractInterpreter or InMemoryDataOpInterpreter

}

Now since M[_] may be any type constructor for which a Capture instance exists, you can create your own implementations for Task, Try, Xor or anything that can capture effectful computations.

import monix.eval.Task
import monix.cats._

implicit val taskCaptureInstance = new Capture[Task] {
  override def capture[A](a: => A): Task[A] = Task.evalOnce(a)
}

import cats.implicits._

type Result[A] = Throwable Xor A

implicit val xorCaptureInstance = new Capture[Result] {
  override def capture[A](a: => A): Result[A] = Xor.catchNonFatal(a)
}

implicit val tryCaptureInstance = new Capture[Try] {
  override def capture[A](a: => A): Try[A] = Try(a)
}

val xorInterpreter = new Interpreters[Result].interpreter

val taskInterpreter = new Interpreters[Task].interpreter

val tryInterpreter = new Interpreters[Try].interpreter

The flexibility of parameterizing interpreters empowers you to have different runtimes and use Effect capturing async capable type constructors such as Task applied in production while keeping things simple in tests by interpreting to Xor, Try or any other type constructor that does not require execution contexts.

Your program can now be evaluated to any given interpreter, changing its runtime behavior while keeping definitions and interactions intact. True separation of Business Logic from implementation.

val xorProgram = program foldMap xorInterpreter

val taskProgram = program foldMap taskInterpreter

val tryProgram = program foldMap tryInterpreter

Conclusion

Algebraic design with Free monads, Coproduct, and Inject helps to arrange an application as collections of Algebras which describe operations. These operations and how they are combined are ultimately an Application definition and the core biz logic that defines it.

The application structure is completely isolated and independent of interpretation and may remain unchanged even when changing implementations.

As always, thanks for reading! If you have any questions or suggestions, don’t hesitate to start the conversation on Twitter, or in the comments below.

For those interested in a REPL ready version of the code you can obtain one here

Ensure the success of your project

47 Degrees can work with you to help manage the risks of technology evolution, develop a team of top-tier engaged developers, improve productivity, lower maintenance cost, increase hardware utilization, and improve product quality; all while using the best technologies.