Dealing with external effects building a pure functional api using Scala is an interesting topic in the context of pure functional programs design. Today there are great frameworks four developing your external interactions apis like Cats Effect or ZIO, to name a few. However, it is recommendable for developers that want to work with pure IO to become familiar with the concepts that I will explain in this post.

Case

Imagine a groupedWithin operator that pushes downstream a mini-batch of data in a List[A] in every interval of t seconds. For each element of this collection it is necessary to execute an IO operation that will produce a runtime value, that could be considered as a kind of context for the next operation.

Antecedents

There are a lot of explanations about this (and a little old) topic and I would suggest reading the red book “Functional Programming in Scala” by Chiusano and Bjarnason, chapter 13 “External Effects and IO”.

def sum(list: List[Int]): Int = list match {
case Nil => 0
case x :: xs => x + sum(xs)
}
def sumWithAccumulator(list: List[Int], accumulator: Int): Int = {
list match {
case Nil => accumulator
case x :: xs => sumWithAccumulator(xs, accumulator + x)
}
}

Abstracting over the IO Type

We can think that an IO type represents an interaction with the outside world, there is no need in thinking about any specific implementation yet. The only thing that it is necessary for the moment is that the effect execution creates a runtime value for the successive one.

trait IO[A] { self =>
def execute : A
def flatMap[B](f: A => IO[B]): IO[B] = {
new IO[B] {
def execute = f(self.execute).execute
}
}

def map[B](f: A => B): IO[B] =
new IO[B] { def execute = f(self.execute) }
}
case class PrintToConsole(msg: String) extends IO[Unit] {
override def execute: Unit = println(msg)
}
for {
_ <- PrintToConsole("Hello")
_ <- PrintToConsole("World")
} yield()
def fold[A, B](l: List[A])(z: B)(f: (B, A) => IO[B]): IO[B] = {
l match {
case h :: tail => f(z, h) flatMap (z2 => fold(tail)(z2)(f))
case _ => new IO[B] {
override def execute: B = z
}
}
}
val list = List.fill(5)("Hello")
val result2 = IO.fold(list)() { (_, b) =>
PrintToConsole(b)
}
result2.execute

Trampolines

If you analyze the Cats IO documentation you can see something that people that are not familiar with these concepts may overlook: “IO is trampolined in its flatMap valuation”. Take a look to the following example:

import cats.effect.IOdef fib(n: Int, a: Long, b: Long): IO[Long] =
IO.suspend {
if (n > 0) fib(n - 1, b, a + b) else IO.pure(a)
}

Folding a List without blowing the Stack

The first thing that we need is to take a look to the meaning of Trampoline. There are a lot of definitions and blogs about this topic, I still recommend the red book because besides explaining the concept and proposing some interesting exercises, it gets deeper and describes the connection between Trampolines and the Free Monad very well. There is a very interesting paper of Runar Bjarnason about these concepts that I recommend reading carefully.

sealed trait TailRec[A] {
def map[B](f: A => B): TailRec[B] = flatMap(f andThen (Return(_)))
def flatMap[B](f: A => TailRec[B]): TailRec[B] = FlatMap(this, f)
}
final case class Return[A](a: A) extends TailRec[A]
final case class Suspend[A](resume: () => TailRec[A])
extends TailRec[A]
final case class FlatMap[A, B](sub: TailRec[A], k: A => TailRec[B]) extends TailRec[B]
def foldSafe[A, B]
(l: List[A])(z: B)
(f: (B, A) => TailRec[IO[B]]): TailRec[IO[B]] = {

l match {
case h :: tail =>
f(z, h)
.flatMap (z2 => Suspend(() =>
foldSafe(tail)(z2.execute)(f)))
case Nil =>
Return(new IO[B] {
override def execute: B = z
})
}
}

The Interpreter

To explain how the interpreter works I will borrow the factorial calculation example using the Trapoline:

def fac(n: Int): TailRec[Int] = {
if (n == 0)
Return(1)
else
FlatMap[Int, Int](Suspend(() => fac(n - 1)), x => Return(n * x))
}
FlatMap(
Return(1),
x => Flatmap(
Return(1 * x), x => Flatmap(
Return(2 * x), x => Flatmap(
Return(3 * x), x => Flatmap(
Return(4 * x), x => Return(5 * x)
)
)
)
)
)
def run[A](tr: TailRec[A]): A = tr match {
case Return(a) => a
case Suspend(r) => run(r())
case FlatMap(x, f) => x match {
case Return(a) => run(f(a))
case Suspend(r) => run(FlatMap(r(), f))
case FlatMap(y, g) => run(y.flatMap(g(_) flatMap f))
}
}

Testing the API

For testing our new foldSafe function, we create the a new collection and pass the function that represent the side effect as parameter, and this must be a (A, B) => TailRec[IO[B]] function:

val list = List.fill(50000)("Hello")

val result = IO.foldSafe(list)() { (_, b) =>
Return(PrintToConsole(b))
}

IO.run(result)

Conclusions

As I mentioned at the beginning of this post, different IO monad implementations solve this problem and developers, normally, don´t have to be worried about the stack although sometimes some words related to trampolines can appear and it is good to know where they come from.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store