DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Refcards Trend Reports Events Over 2 million developers have joined DZone. Join Today! Thanks for visiting DZone today,
Edit Profile Manage Email Subscriptions Moderation Admin Console How to Post to DZone Article Submission Guidelines
View Profile
Sign Out
Refcards
Trend Reports
Events
Zones
Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Partner Zones AWS Cloud
by AWS Developer Relations
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Partner Zones
AWS Cloud
by AWS Developer Relations
Securing Your Software Supply Chain with JFrog and Azure
Register Today

Trending

  • Effective Java Collection Framework: Best Practices and Tips
  • Microservices With Apache Camel and Quarkus
  • Understanding Dependencies...Visually!
  • Microservices With Apache Camel and Quarkus (Part 2)

Trending

  • Effective Java Collection Framework: Best Practices and Tips
  • Microservices With Apache Camel and Quarkus
  • Understanding Dependencies...Visually!
  • Microservices With Apache Camel and Quarkus (Part 2)
  1. DZone
  2. Coding
  3. Languages
  4. For-Comprehension Free Monads in Scala

For-Comprehension Free Monads in Scala

Scala’s for-comprehension has more to offer than traditional monadic operations.

Michael Wang user avatar by
Michael Wang
·
Aug. 23, 19 · Presentation
Like (2)
Save
Tweet
Share
11.09K Views

Join the DZone community and get the full member experience.

Join For Free

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.

Monad (functional programming) Scala (programming language)

Opinions expressed by DZone contributors are their own.

Trending

  • Effective Java Collection Framework: Best Practices and Tips
  • Microservices With Apache Camel and Quarkus
  • Understanding Dependencies...Visually!
  • Microservices With Apache Camel and Quarkus (Part 2)

Comments

Partner Resources

X

ABOUT US

  • About DZone
  • Send feedback
  • Careers
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 600 Park Offices Drive
  • Suite 300
  • Durham, NC 27709
  • support@dzone.com

Let's be friends: