# Functional Programming to the max

This post is an adaptation of the talk FP to the max, credit goes to John A De Goes. We will take a minimal example written in a procedural style and introduce functional programming techniques and principles to create a more principled application. It is important to preface this post with a disclaimer which is Do not try this on your codebase!! - this example is an overkill and is only intended to help developers see how functional concepts can be applied on a small scale so that they can extrapolate these techniques on larger projects.

# Number Guessing Game

The example we will use throughout this post is a number guessing game. When the program starts it will ask the user for his/her name and on input the program will generate a random number between 1 and 5 and ask the user to guess the number. If the user guesses the number correctly, the program will inform the user of his/her unique mind-reading abilities (incidentally, the user’s superpowers will work 20% of the time!), otherwise, the program will notify the telekinetic failure. Finally, once the game round is complete, the program will ask the user the choose between having another go or exiting. The complete source code is listed below:

def main(args: Array[String]): Unit = {
println(s"Hello $name welcome to the game!") var exec: Boolean = true while (exec) { val num: Int = scala.util.Random.nextInt(5) + 1 println(s"Dear$name, please guess a number from 1 to 5")
if (guess == num) println(s"You guessed right, $name!") else println(s"You guessed wrong,$name the number was $num") println(s"Do you want to continue$name?")
case "y" => exec = true
case "n" => exec = false
}
}
}


So what’s “wrong” with such a program? To understand what we can improve, let us first detour and explain the three functional programming principles.

# Functional Programming Properties

Functional programs have three main properties:

1. Total - Functions always return an output for every input.
2. Deterministic - Functions return the same output for the same input.
3. Pure - The only purpose of providing a function input is to compute the output.

In contrast, procedural programs are:

1. Partial - Procedures do not return values for some inputs (for example, they throw exceptions).
2. Non-Deterministic - Procedures return different outputs for the same input.
3. Impure - Procedures perform side-effects which mutate data or interact with the external world.

Let’s have a look at some examples to see how these principles apply.

Example 1: Print line to system output

def println(s: String): Unit = ???


The method println above is:

• Total - it is defined for all inputs - the output is always unit
• Deterministic - all inputs yield the same output - unit
• Impure - under the hood println invokes some system calls to push things to the screen - this is not part of the computation.

Example 2: Parse integer

def parseInt(s: String): Int = ???


The method parseInt above is:

• Partial - not all strings are valid numbers, e.g. the input “hello world” would throw an exception
• Deterministic - all inputs will give the same result or error
• Pure - There are no side-effects or interactions apart from the conversion from a string to an integer.

Example 3: Generate a random number

def randomInt(): Int = ???


The method randomInt above is:

• Total - for every input we get an output
• Non-Deterministic - by definition the return of a random function is non-deterministic
• Impure - random numbers are generated by observing outside data that is not predictable or generated using pseudo-random streams, both of which are external to the computation.

Having understood the properties of functional programs, we will now iterate over the source problem and convert it into an equivalent program that is more principled (i.e. follows more functional programming properties).

# Number Guessing Game - First Iteration

In the first iteration of the program, we will directly address two partial functions. The first partial function that we are going to address is

val guess: Int = readLine().toInt


readLine().toInt is a partial function since it is not defined for all inputs (some inputs will throw an exception). One way to implement the total equivalent is to swap the return type from Int to Option[Int] to capture cases in which the input would throw an exception. You can think of Option[Int] as a more honest type since it explicitly encodes those values which yield no result.

def parseNumber(str: String): Option[Int] = Try(str.toInt).toOption


The second partial function we will address in this section is

readLine() match {
case "y" => exec = true
case "n" => exec = false
}


This function is not total since it is only defined for two inputs, “y” and “n”, in all other cases, a MatchError is thrown. We can convert this to a total function as follows:

var continue: Boolean = false
while(continue) {
continue = false
case "y" => exec = true
case "n" => exec = false
case _ => continue = true
}
}


The complete code after these two conversions is

def main(args: Array[String]): Unit = {
println(s"Hello $name welcome to the game!") var exec: Boolean = true while (exec) { val num: Int = scala.util.Random.nextInt(5) + 1 println(s"Dear$name, please guess a number from 1 to 5")
guessOpt match {
case None =>
println("Not a number!")
case Some(guess) =>
if (guess == num) println(s"You guessed right, $name!") else println(s"You guessed wrong,$name the number was $num") println(s"Do you want to continue$name?")
var continue: Boolean = false
while(continue) {
continue = false
case "y" => exec = true
case "n" => exec = false
case _ => continue = true
}
}
}
}
}


# Number Guessing Game - Second Iteration

The initial iteration of the program is already more principled than our original problem, and, in most cases, we would stop here. For the sake of this exercise, however, we will address three more procedures: println, readLine and Random.nextInt. How to convert such functions into pure functions has perplex the FP community for years. Fortunately, the solution was simple and elegant; let’s welcome the IO monad. Let’s start this section by creating the IO monad from scratch.

Disclaimer to the future FP reader In this post, I will be taking a very informal approach to describing the IO Monad. If you feel that there is a better way to explain this section, please comment below. It would be great if we as a community come together and help newcomers in the field!

You can think of the IO monad as a “container” that contains a description of a computation. The computation itself might not be functional (in the functional programming sense), but the description itself is. The basic definition of the IO Monad is as follows:

case class IO[A](unsafeRun: () => A) {}


You can see that the value of type A is deferred (the return of a function) by placing it into an IO[A] box, and only when the unsafeRun method is called, the value of type A is returned. Let’s have a look at an example.

object IOSample {
def main(args: Array[String]): Unit = {
val program: IO[Unit] = IO(() => println("Hello World"))
println(program)
}
}


Running the program above will result in the following output:

IO(com.suprnation.IOSample$Lambda$15/0x0000000801162c40@5b464ce8)


As you can see, nothing happens - program is just a description that has an embedded println computation. So the above description is total, deterministic and pure, and is one value from the infinite IO[Unit] set.

To run this description, we need to invoke the unsafeRun method as follows:

object IOSample {
def main(args: Array[String]): Unit = {
val program: IO[Unit] = IO(() => println("Hello World"))
program.unsafeRun()
}
}


At this point the program transitions from pure to impure (as in not following the FP properties) and “Hello World” is printed to the console.

## Transforming IO; map and flatMap

To compose IO, we will need two main methods: map and flatMap defined as follows:

case class IO[A](unsafeRun: () => A) { self =>
def map[B](fn: A => B): IO[B] = IO(() => fn(self.unsafeRun()))
def flatMap[B](fn: A => IO[B]): IO[B] = IO(() => fn(self.unsafeRun()).unsafeRun())
}


Visually if we think of IO as a box with a value inside, we can think of map as a function that swaps the value of the box by passing it through the function fn and flatMap as swapping the box based on the current value. As an example let’s say we want to increment the value val three = IO(() => 3).

We can achieve this by using the map function as follows:

val three = IO(() => 3)
three.map(v => v + 1)


What if we want to return true when the value inside the box is even and false otherwise? In this case, we want to swap the box entirely, and hence we would use a flatMap as follows:

val three = IO(() => 3)
three.flatMap(v => if (v % 2 == 0) IO(() => true) else IO(() => false))


Before we go further, let’s define two helper methods on the IO companion object - point and unit - to help us package pure values in an IO box.

object IO {
def point[A](a: A): IO[A] = IO(() => a)
def unit: IO[Unit] = IO.point(())
}


Using these helper methods, we can simplify the example above as follows:

val three = IO.point(3)
three.map(v => v + 1)
three.flatMap(v => if (v % 2 == 0) IO.point(true) else IO.point(false))


## For comprehension

Before we transform the original program, let’s do one final example of adding two IO[Int] together. Given the following program

object IOArithmetic {
def main(args: Array[String]): Unit = {
val number1: IO[Int] = IO.point(1)
val number2: IO[Int] = IO.point(2)
}
}


we cannot simply add the two numbers using number1 + number2 but we need to use a combination of flatMap and map to sequence the computation. The solution to this problem is as follows:

object IOArithmetic {
def main(args: Array[String]): Unit = {
val number1: IO[Int] = IO.point(1)
val number2: IO[Int] = IO.point(2)

number1.flatMap(n1 => {
number2.map(n2 => {
n1 + n2
})
})
}
}


The use of flatMap and map to sequence computations is so common that Scala has some special syntactic sugar called for comprehensions. Thus, the above can be re-written as follows:

for {
n1 <- number1
n2 <- number2
} yield n1 + n2


Moving forward, we will prefer this style rather than explicitly writing flatMap and map but remember that both are equivalent and it is just syntactic sugar .

# Final Conversion

Armed with the IO Monad, let’s crank up the function knob and finalise the conversion. We will start by wrapping up the println, readLine and Random.nextInt within IO as follows:

def putStrLn(message: String): IO[Unit] = IO(() => println(message))
def getStrLn: IO[String] = IO(() => readLine())
def randomNumber(upper: Int): IO[Int] = IO(() => scala.util.Random.nextInt(upper))


Next, we will convert the original program using flatMap and map. The conversion is reasonably mechanical but to illustrate our conversion strategy, let’s transform the first three lines of the procedural program.

println("What is your name?")
println(s"Hello $name welcome to the game!")  These three lines can be written using a for-comprehension as follows: for { _ <- putStrLn("What is your name?") name <- getStrLn _ <- putStrLn(s"Hello$name welcome to the game!")
} yield ()


In a sense, this program is reminiscent of the procedural counterpart, but there is one key difference - this program is just a description. We will need to call unsafeRun to execute this description which will unwrap the descriptions and perform the underlying computations. At this point our program violates the functional properties defined above and crosses the pure to impure boundary.

val program = for {
_    <- putStrLn("What is your name?")
name <- getStrLn
_    <- putStrLn(s"Hello $name welcome to the game!") } yield () program.unsafeRun()  The transformed number guessing game is as follows: def main(args: Array[String]): Unit = { def checkContinue(name: String): IO[Boolean] = for { _ <- putStrLn(s"Do you want to continue$name?")
input <- getStrLn
cont <-  input.toLowerCase() match {
case "y" => IO.point(true)
case "n" => IO.point(false)
case _ => checkContinue(name)
}
} yield cont

def gameLoop(name: String): IO[Unit] = for {
num <- randomNumber(5).map(_ + 1)
_   <- putStrLn(s"Dear $name, please guess a number from 1 to 5") input <- getStrLn _ <- parseNumber(input) match { case None => putStrLn("Not a number!") case Some(guess) => if (guess == num) putStrLn(s"You guessed right,$name!")
else putStrLn(s"You guessed wrong, $name the number was$num")
}
cont <- checkContinue(name)
_    <- if (cont) gameLoop(name) else IO.unit
} yield ()

val program: IO[Unit] = for {
_     <- putStrLn("What is your name?")
name  <- getStrLn
_     <- putStrLn(s"Hello \$name welcome to the game!")
_     <- gameLoop(name)
} yield ()

program.unsafeRun()
}


Note that loops in functional programs are transformed into tail-recursive functions. Note also that even though our functions are tail-recursive, our IO implementation is not, and this program will lead to stack overflow issues. Multiple libraries implement a stack safe IO; we opted for simplicity to showcase how functional concepts relate. If you are going to use IO in production, I strongly recommend using Cats Effect or ZIO.

# Conclusion

This post transformed a procedural program into a functional program abiding to the three functional principles. The final transformation is still not the end of the road to functional-town; we could expand this example further to categorise different types of IO (tag-less final), but we will leave that for another post. For now, the take-home message is this:

Think of functional programming as a tool in your toolbox. You can always adjust the level of purity in your codebase to fit your comfort level. What’s important is that whatever you do, try to be more principled.

As always, stay safe, keep hacking.

Written on September 6, 2021