1. Introduction
In this tutorial, we cover monads and free monads and why they’re useful, as well as go over examples for practical demonstration. Scala has very powerful typing constructs that allow us to implement strongly typed functional design patterns, like monads and free monads, enabling new abstraction capabilities by building on simpler constructs.
A monad in Scala is an object that wraps another value and defines the flatMap method to apply a function to the wrapped value. The function takes the internal value and returns another monad. Free monads are designed to provide the same compositional properties as monads but separate the logic specification from its implementation.
2. Monads
A monad is a concept from category theory that has been extended to functional programming because of useful compositional properties. Scala has many monads; for example, Either, Option, List, and Future are monads. We can tell a type is a monad if it has a pure constructor and a flatMap function:
trait Monad[F[_]]:
def flatMap[A, B](fa: F[A])(f: (A) => F[B]): F[B]
def pure[A](a: A): F[A]
def map[A, B](fa: F[A])(f: A => B): F[B] =
flatMap(fa)(a => pure(f(a)))
We use pure to create monads, then we use flatMap and map to compose logic in nested sequential scopes:
val listComposition =
for
number <- 0 to 9
letter <- 'A' to 'Z'
yield s"$number$letter"
For-comprehensions are just syntactic sugar for flatMap and map. The compiler transforms it to this:
val desugaredListComposition =
(0 to 9).flatMap: number =>
('A' to 'Z').map: letter =>
s"$number$letter"
We compose with flatMap and map values. For a more thorough explanation, see our article on monads.
3. Free Monads
Similar to monad, “free” terminology is taken from higher mathematics. Free constructions capture the idea of the least specific or most general construction satisfying certain properties. In the context of free monads, we have a general way of satisfying monad properties with a functor, allowing us to enhance functors with a monadic structure.
A functor is more general than a monad, having only a map method like this:
sealed trait Functor[F[_]]:
def map[A, B](fa: F[A])(f: A => B): F[B]
See our more thorough explanation of functors; for F[_] syntax, see our article on higher-kinded-types.
To model a free monad structure, we use Free:
trait ~>[F[_], G[_]]:
def apply[A: Typeable](f: F[A]): G[A]
sealed trait Free[F[_], A: Typeable]:
def map[B: Typeable](f: A => B): Free[F, B] = FlatMap(this, (a: A) => Pure(f(a)))
def flatMap[B: Typeable](f: A => Free[F, B]): Free[F, B] = FlatMap(this, f)
def foldMapAs[G[_]: Monad](using F ~> G): G[A] = this match
case Pure(value) => summon[Monad[G]].pure(value)
case FlatMap(sub, f) =>
summon[Monad[G]]
.flatMap(sub.foldMapAs[G]): in =>
f(in).foldMapAs[G]
case Suspend(s) => summon[F ~> G](s)
case class Pure[F[_], A: Typeable](value: A) extends Free[F, A]
case class FlatMap[F[_], A: Typeable, B: Typeable](sub: Free[F, A], f: A => Free[F, B]) extends Free[F, B]
case class Suspend[F[_], A: Typeable](s: F[A]) extends Free[F, A]
In our Free type, map and flatMap provide the normal monadic operations. foldMapAs allows us to convert a Free[F, A] to a Free[G, A], and Pure, FlatMap, and Suspend are used to construct a specification of monadic logic using Free. We need to use A: Typable as a means to overcome type erasure in Scala 3. See on our article on Scala 2 type erasure; for an explanation of using F ~> G, see our article on contextual abstractions.
3.1. Basic Example
Let’s consider a basic example by defining LazyCatchable:
trait LazyCatchable[+A]:
def run(): Either[Catch, A]
final class Lazy[A](value: => A) extends LazyCatchable[A]:
def run(): Either[Catch, A] = Try(value) match
case Success(value) => Right(value)
case Failure(e) => Left(Catch(e))
final case class Catch(e: Throwable) extends LazyCatchable[Nothing]:
def run(): Either[Catch, Nothing] = this
LazyCatchable allows us to wrap a lazy computation in Lazy and Catch errors if we decide to evaluate. We can already write a monadic program without writing flatMap or map methods for LazyCatchable:
val sumProgram: Free[LazyCatchable, Int] =
for
a <- Suspend(Lazy(1))
b <- Suspend(Lazy(2))
result <- Pure(a + b)
yield result
We’re able to monadically compose without LazyCatchable being a monad. Our sumProgram isn’t a number; it’s a data structure that represents our program:
val desugaredSumProgram =
FlatMap(
Suspend(Certainly(1)),
(num1: Int) => FlatMap(
Suspend(Certainly(2)),
(num2: Int) => Pure(num1 + num2)
)
)
3.2. Translating Between Monads
One of the major reasons to use free monads is that we can define our logic using any type of constructor we want, but we still need a monad instance to compute composition. Instead, we can define a translation between our LazyCatchable and an existing monad, like a Future:
given LazyCatchable2Future: (LazyCatchable ~> Future) with
def apply[A: Typeable](f: LazyCatchable[A]): Future[A] = f match
case Catch(e) => Future.failed(e)
case lazyValue: Lazy[_] => Future:
lazyValue.run() match
case Left(Catch(e)) => throw e
case Right(value: A @unchecked) => value
LazyCatchable2Future allows us to convert a LazyCatchable to a Future. Then we need a Monad instance of Future to foldMapAs our data structure into a single value:
given FutureMonad: Monad[Future] with
def flatMap[A, B](fa: Future[A])(f: (A) => Future[B]): Future[B] = fa.flatMap(f)
def pure[A](a: A): Future[A] = Future(a)
override def map[A, B](fa: Future[A])(f: A => B): Future[B] = fa.map(f)
Now, we can intuitively convert our sumProgram into a Future that implements its specification:
val sumProgramFuture: Future[Int] = sumProgram.foldMapAs[Future](using FutureMonad, LazyCatchable2Future) // Future computes to 3
3.3. DSL Models
Instead of representing our program with the implementation details, we can use a DSL to model the various stages and provide implementation details when we convert it to a proper monad. Let’s consider a workflow represented as an enum:
enum WorkflowCommand:
case FeelInspiredToLearn
case LikeFriendlyEnvironments
case WantToHelpPeopleBuildConfidenceCoding
case JoinBaeldungAsAWriter
Now, we can model a program using the various stages of the workflow:
def command[C <: WorkflowCommand](c: => C): Free[LazyCatchable, C] = Suspend(Lazy(c))
val joinBaeldungWorkflow: Free[LazyCatchable, WorkflowCommand] =
for
_ <- command(WorkflowCommand.FeelInspiredToLearn)
_ <- command(WorkflowCommand.LikeFriendlyEnvironments)
_ <- command(WorkflowCommand.WantToHelpPeopleBuildConfidenceCoding)
`reachOutToday!` <- Pure(WorkflowCommand.JoinBaeldungAsAWriter)
yield `reachOutToday!`
Using free monads, we can define our logic more purely, more succinctly, and precisely than any other tutorial online*.* We can use the existing LazyCatchable2Future interpreter, which will always compute JoinBaeldungAsAWriter. The LazyCatchable2Future interpreter is handy when you want to mock a successful execution for testing. We can also provide a different translation with implementation details:
given BaeldungWorkflowInterpreter: (LazyCatchable ~> Future) with
private def askQuestion(question: String, repeat: Boolean = false): Boolean =
if repeat then print(s"\nInvalid response: try again (y or n) ")
else print(s"\n$question (y or n) ")
readChar() match
case 'y' | 'Y' => true
case 'n' | 'N' => false
case _ => askQuestion(question, true)
private def step[C <: WorkflowCommand](question: String, command: C, error: String): Future[C] = Future:
if askQuestion(question) then command
else throw new Exception(error)
def apply[A: Typeable](f: LazyCatchable[A]): Future[A] = f match
case Catch(e) => Future.failed(e)
case lazyCmd: Lazy[_] => lazyCmd.run() match
case Left(Catch(e)) => Future.failed(e)
case Right(command: WorkflowCommand) =>
command match
case WorkflowCommand.FeelInspiredToLearn =>
step(
question = "Do you feel inspired to learn Scala?",
command = command,
error = "Baeldung has tutorials for other technologies too, like Java."
)
case WorkflowCommand.LikeFriendlyEnvironments =>
step(
question = "Do you like friendly environments?",
command = command,
error = "Bye."
)
case WorkflowCommand.WantToHelpPeopleBuildConfidenceCoding =>
step(
question = "Do you want to help people build confidence coding?",
command = command,
error = "Baeldung tutorials are reliable and informative."
)
case WorkflowCommand.JoinBaeldungAsAWriter => Future.successful(command)
case Right(misc) => Future.successful(misc)
With our WorkflowCommandInterpreter, we can convert the logic of filtering a candidate to an interactive program, leaving all other possible values to a default interpretation. Just as simply as we did before, we can convert joinBaeldungWorkflow to an interactive Future interpretation:
val joinBaeldung: Future[WorkflowCommand] = joinBaeldungWorkflow.foldMapAs[Future](using FutureMonad, BaeldungWorkflowInterpreter)
If we execute the Future and interact with the console, the output looks like this:
Do you feel inspired to learn Scala? (y or n) y
Do you like friendly environments? (y or n) y
Do you want to help people build confidence coding? (y or n) y
JoinBaeldungAsAWriter
By answering yes to all the questions, we finish the workflow without errors and the Future completes with JoinBaeldungAsAWriter. If we answer n to one of the questions, the workflow fails, and an exception is thrown:
Do you feel inspired to learn Scala? (y or n) y
Do you like friendly environments? (y or n) n
[error] java.lang.Exception: Bye.
We can make many different interpretations for the same specification.
4. Conclusion
In this article, we’ve reviewed the basic implementation details and practical motivations for free monads. Free monads are powerful because they enable us to separate the program’s specification from its interpretation. The applications of free monads are expansive, and we have only scratched the surface in this article.
As usual, the code is available over on GitHub.