For-Comprehension Free Monads in Scala

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.

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)

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.

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

• 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 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)       
    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 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.