Connecting...

Pexels Photo 160107

An introduction to Free Monads by Sergi Toda Flores

Go Back
Pexels Photo 160107

Got the goal to decouple or abstract implementation details from an application code?

In this article by Software Engineer, Sergi Toda Flores at Basement Crowd you can learn to do just that using data!

 

'Free Monads solve the very same problem as Tagless Final but in a different way. Our goal is the same: we want to decouple or abstract the implementation details from the application code. If you recall our previous post, we did this by using expressions or functions that would be injected into our application code. We separated the description of our program from its interpretation which came from an interpreter. This time we’ll do the same but instead of relying on expressions we’ll use data.

 

Algebraic Data Types 

What do I mean by using data rather than expressions. Let’s go back to our previous post, there we had the following:
1 trait IndexDsl[F[_]] {
2   def createIndex(name: String): F[Either[String, CreateIndexResponse]]
3   def deleteIndex(name: String): F[Either[String, DeleteIndexResponse]]
4 }

We can represent the very same set of instructions (or algebra in the FP world) as data:

1 sealed trait IndexAlg[A] 
2 case class CreateIndex(name: String) extends IndexAlg[Either[String, CreateIndexResponse]] 
3 case class DeleteIndex(name: String) extends IndexAlg[Either[String, DeleteIndexResponse]]

We’ve just translated some functions into what’s called an Algebraic Data Type (ADT). Note that the return type of our previous functions now has become into a parametric type. Also note we haven’t defined anywhere which effects will use.

 

Monad

Basically we could say that a program is a set of instructions that are executed one after the other. There’s an FP structure that lets us execute things sequentially this is: the Monad. Even if you are not that familiar with the concept of a Monad, if you have been using Scala for any amount of time you will have been taking advantage of the Monadic properties such as flatMap, and further Scala’s syntactical sugar around that in the form of the for comprehension. Here’s an example:
1 val sequentialFuture = for {
2  x <- Future { Thread sleep 1000; 10 }
3  y <- Future { Thread sleep 2000; 32 }
4 } yield x + y

In scala Future is a Monad and has the flatmap function. For comps add syntactic sugar to make flatmap chains more readable. If you were timing this snippet you’d see it takes 3 seconds to execute rather than 2, even though Futures are concurrent. They were executed sequentially.

 

Free Monad

If the ADT was a monad, it would be possible for us to write the following code since we’d had flatmap:
1 def recreateIndex(name: String) = 
2   for { 
3     _ <- deleteIndex(name) 
4     created <- createIndex(name) 
5   } yield created

Luckily for us, there’s no need to implement the monadic methods in our ADT. Functional libraries such as scalaz or cats do that for us. This is done by lifting of ADT into a structure called Free:

1 type IndexDSL[A] = Free[IndexAlg, A] 
2 def createIndex(name: String): IndexDSL[Either[String, CreateIndexResponse]] = Free.liftF(CreateIndex(name)) 
3 def deleteIndex(name: String): IndexDSL[Either[String, DeleteIndexResponse]] = Free.liftF(DeleteIndex(name))

Now that our ADT is monadic so we can implement recreateIndex in terms of a for comp:

1 def recreateIndex(name: String): IndexDSL[Either[String, CreateIndexResponse]] = 
2   for { 
3     _ <- deleteIndex(name) 
4     created <- createIndex(name) 
5   } yield created

This code is perfectly valid and will compile, unfortunately it won’t do anything as it is. We haven’t even defined if this code will be synchronous or asynchronous, we just know that in order to recreate and index we delete it first and then we create it again.

The implementation details will come from an interpreter as we did with Tagless Final. Here’s a synchronous interpreter:

1 object idInterpreter extends (IndexAlg ~> Id) {
2  override def apply[A](fa: IndexAlg[A]): Id[A] = fa match {
3    case CreateIndex(_) => ().asRight[String]
4    case DeleteIndex(_) => ().asRight[String]
5  }
6 }

 

Summary

Free monad is a way to turn a set of instructions (algebra) into a way to express sequential programs, it is an alternative implementation of the Interpreter pattern and an alternative to the Tagless Final pattern we looked at previously.'


This article was written by Sergi Toda and posted originally on Basement Crowd blog.
 

Recent articles