ForComprehension Free Monads in Scala
Scala’s forcomprehension has more to offer than traditional monadic operations.
Join the DZone community and get the full member experience.
Join For FreeA free monad is a construction that allows you to build a monad from any functor. There exists rich literature that explains this concept, notably from Cats and Scalaz documents.
In Scala, free monad allows us to model a workflow using forcomprehension through its monadic operations; it lifts the operations to free monads and is run by an interpreter. However, Scala’s forcomprehension has more to offer than monadic operations.
In this article, we introduce our enhancement by extending free monads beyond monadic operations. We show that this addition makes the free monads more powerful and provides more elegant encoding, without breaking monad law. We briefly explain the building blocks of free monad without making elaborating on its details. Readers are encouraged to understand its full context through online resources. We illustrate our enhancement based on the sample implementation in this article: Free Monads Explained (Pt. 1), without using any of the Scala libraries.
Basic Form of Free Monads
Free monads consist of six parts.
 The central piece is a trait
Free[F[_], A]
, with monadic operations. This is the container that encapsulates the user operations.
sealed trait Free[F[_], A] {
def flatMap[B](f: A => Free[F, B]): Free[F, B] = this match {
case Return(a) => f(a)
case FlatMap(sub, cont) => {
FlatMap(sub, cont andThen (_ flatMap f))
}
}
def map[B](f: A => B): Free[F, B] = flatMap(a => Return(f(a)))
}
case class Return[F[_], A](a: A) extends Free[F, A]
case class FlatMap[F[_], I, A](sub: F[I], cont: I => Free[F, A]) extends Free[F, A]
 User Instructions, for instance:
sealed trait AskTell[A]
case class Ask(message:String) extends AskTell[String]
case class Tell(message:String) extends AskTell[String]
 An implicit function that lifts the user instructions to free monads.
implicit def liftF[F[_], A](fa: F[A]): Free[F, A] = FlatMap(fa, Return.apply)
 An interpreter that runs the free monads.
def runFree[F[_], A](prg: Free[F, A], executor: Executor[F]): A = {
prg match {
case Return(a) => a
case FlatMap(sub, cont, filter) => {
runFree(cont(executor.exec(sub, filter)), executor)
}
}
}
 Implementations of user instructions encapsulated in an executor:
sealed trait Executor[F[_]] {
def exec[A](fa: F[A]): A
}
val asktellExec = new Executor[AskTell] {
override def exec[A](fa: AskTell[A]):A = fa match {
case Ask(message) => {
println(message)
val name = scala.io.StdIn.readLine()
name.asInstanceOf[A]
}
case Tell(message) => {
println(message)
message.asInstanceOf[A]
}
}
}
}
 Workflow modeling
val asktell = for {
name < Ask("What is your name?")
_ < Tell(s"Hello ${name}!")
} yield ()
And finally, run the workflow:
runFree(asktell, asktellExec)
ForComprehension in Scala
Forcomprehension is a lightweight notation for expressing sequence comprehensions. It takes the following forms:

For
, withyield
, is translated intomap
:
for(x < List(1,2,3)) yield x*x
Which will be translated to:
List(1,2,3).map {x => x*x}
 Then, nested
for
withyield
is translated toflatMap
andmap
:
for(x < List(1,2,3); y < List(4,5,6)) yield x*y
Which will be translated to:
List(1,2,3).flatMap { x =>
List(4,5,6).map { y => x*y}
}

For
, withoutyield
, is translated toforeach
, anything insideforeach
are actions with a side effect, for instance, sending emails, writing to the database, etc.
for(x < List(1,2,3)) println(x)
Which will be translated to:
List(1,2,3).foreach{x => println(x)}

For
, withguard
, is translated towithFilter
:
for(x < List(1,2,3) if x ==3 ) yield x*x
Which is translated to:
List(1,2,3).withFilter(x == 3)..map {x => x*x}
As we can see, free monad provides map
and flatMap
; it covers the first and second case in forcomprehension.
Enhanced Free Monads
Free monads provide a natural transformation of workflow through monadic operations; however, the workflow is not only an independent sequence of user instructions; actions with side effects can be part of the workflow, and the workflow sequence can be branched out depending on predicates. As discussed, the current free monad implementation cannot utilize the full potential of forcomprehension. The missing parts are foreach
translation and filters, which will be addressed in our enhanced free monad.
Here are the encodings to each part of the enhanced free monad.
 Free Monad definition:
def foreach[U](f: A => U) : Free[F, A] = this match {
case Return(a) => {
f(a) match {
case free : Free[F, A] => free
case _ => this
}
}
case FlatMap(sub, cont, filter ) => {
FlatMap(sub, cont andThen (_ foreach f), filter)
}
}
def withFilter(f: A => Boolean): Free[F, A] = this match {
case Return(a) => this
case FlatMap(sub, cont, filter ) => FlatMap(sub, cont, f(ph))
}
The key addition to an enhanced free monad is the presence of foreach
and withFilter
for forcomprehension to access. They cover the third and fourth case of forcomprehension discussed in the last section. A key change to FlatMap
is that it carries the evaluation of the predicate in its construction and carried on for future execution:
case class FlatMap[F[_], I, A](sub: F[I], cont: I => Free[F, A], filter:Boolean) extends Free[F, A]
 The user instruction interface remains the same
 Implicit lift
implicit def liftF[F[_], A](fa: F[A]): Free[F, A] = FlatMap(fa, Return.apply, true)
Implicit lift function adds a Boolean guard with a default value of true.
 The interpreter:
def runFree[F[_], A](prg: Free[F, A], executor: Executor[F]): A = {
prg match {
case Return(a) => a
case FlatMap(sub, cont, filter) => {
runFree(cont(executor.exec(sub, filter)), executor)
}
}
}
The interpreter constructs the calling sequence and passes the guard
recursively.
 User instruction implementation
val asktellExec = new Executor[AskTell] {
override def exec[A](fa: AskTell[A], filter:Boolean) = fa match {
case Ask(message) if filter => {
println(message)
val result = scala.io.StdIn.readLine()
result.asInstanceOf[A]
}
case Tell(message) if filter => {
println(message)
message.asInstanceOf[A]
}
case _ => "filtered out".asInstanceOf[A]
}
The guard
is applied here before execution.
 Workflow modeling:
val asktell = for {
hour < Ask("What time is it?")
_ < Tell(s"Good Morning, it is ${hour}am") if (hour.toInt <= 12)
_ < Tell(s"Good afternoon, it is ${hour.toInt 12}pm") if (hour.toInt > 12)
} yield ()
val asktell2 = for {
firstname < Ask("what is your first name?")
lastname < Ask("what is your last name?")
age < Ask("what is your age?")
} {
println(s"${firstname} ${lastname}, ${age} years old")
}
We notice that we are able to use predicates, as well as forcomprehension with actions.
The execution of the workflow remains the same:
runFree(asktell, asktellExec)
The complete implementation can be found on GitHub.
Conclusion
In this article, we summarized the building blocks of a free monad, as well as explained forcomprehension in Scala. We have shown how free monads work with forcomprehension, identified the areas to be improved, and provided the implementation.
The enhanced free monad implementation maintains the properties of free monads – stackfree and natural transformation. By making free monads fully forcomprehension, the encoding gained firepower to model more dynamic operations; the interpreter separates the concerns from execution; and the client program remains the same.
Opinions expressed by DZone contributors are their own.
Comments