{{announcement.body}}
{{announcement.title}}

# For-Comprehension Free Monads in Scala

DZone 's Guide to

# For-Comprehension Free Monads in Scala

· Java Zone ·
Free Resource

Comment (0)

Save
{{ articles[0].views | formatCount}} Views

A 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 for-comprehension through its monadic operations; it lifts the operations to free monads and is run by an interpreter. However, Scala’s for-comprehension has more to offer than monadic operations.

## 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]
• 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
}
override def exec[A](fa: AskTell[A]):A = fa match {
println(message)
name.asInstanceOf[A]
}
case Tell(message) => {
println(message)
message.asInstanceOf[A]
}
}
}
}``````
• Workflow modeling
``````val asktell = for {
_    <- Tell(s"Hello \${name}!")
} yield ()``````

And finally, run the workflow:

``runFree(asktell, asktellExec)``

## For-Comprehension in Scala

For-comprehension is a lightweight notation for expressing sequence comprehensions. It takes the following forms:

•  `For`, with `yield`, is translated into `map`:
``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` with `yield` is translated to `flatMap` and `map`:
``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`, without `yield`, is translated to `foreach`, anything inside `foreach` 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`, with `guard`, is translated to `withFilter`:
``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 for-comprehension.

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 for-comprehension. 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.

``````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 for-comprehension to access. They cover the third and fourth case of for-comprehension 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)
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 ()

} {
println(s"\${firstname} \${lastname}, \${age} years old")
}``````

We notice that we are able to use predicates, as well as for-comprehension 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 for-comprehension in Scala. We have shown how free monads work with for-comprehension, identified the areas to be improved, and provided the implementation.

The enhanced free monad implementation maintains the properties of free monads – stack-free and natural transformation. By making free monads fully for-comprehension, the encoding gained firepower to model more dynamic operations; the interpreter separates the concerns from execution; and the client program remains the same.

Topics:
scala ,functional programing ,java ,monads ,free ,for-comprehension ,flatmap ,foreach

Comment (0)

Save
{{ articles[0].views | formatCount}} Views

Opinions expressed by DZone contributors are their own.