Option, Either, State, and IO: Imperative programming in a functional world

Imperative programming in a functional world

Transitioning from imperative to functional programming is a long and arduous (yet ultimately rewarding) road. The newcomer must first master immutability, higher-order functions, and algebraic data types. After that, there are other patterns from imperative programming that must be relearned in a functional universe. Imperative and functional programming both have their own toolkits for dealing with common problems. There are several common types that one will likely encounter throughout their entire career in FP (to varying degrees, depending on the language). Below are four types that I think are the most essential to programming in a purely functional style, in increasing order of complexity.

All code examples are in Scala. We will assume the reader is already familiar with generics and algebraic data types (ADTs).

Option

We would often like to represent the absence of a value. This may be used to indicate an optional config, a user-supplied input, or even some kind of error. For example, map.get(key) may return a value, or there may be no value associated with that key. Likewise, parseInt(string), will fail if the string does not represent an integer.

There are two mechanisms for handling these types of errors (which are not really errors, but just normal occurrences in a program). For a long time, null has been the go-to choice for representing missing values in imperative programs. For example, in Java, the get method on maps returns Null if the key is not in the map. Null has several disadvantages.

For one, it requires the programmer to remember to handle the null case. Since Null is a value of every type, during type checking it will be treated as if it were the correct type, allowing us to write meaningless code like map.get(key) + 1, that may result in a runtime error.

Option replaces Null with an algebraic data type, commonly defined as:

sealed trait Option[A]
final case class Some[A](val: A) extends Option[A]
final case object None extends Option[Nothing]

Here we are using the power of algebraic data types to encode the presence or absence of a value. In one case, we know we definitely have a value of type A, and in the other, we definitely don’t.

Crucially, Option[A] is a distinct type from A. This means we cannot call functions directly on Option[A], but must first pattern-match into the two cases, and handle them both appropriately. For example, the following code is illegal:

val input: Option[String] = get_user_input()
input.capitalize

because capitalize expects type String, not Option[String. The type system forces us to deal with both cases:

val input: Option[String] = get_user_input()
input match {
 case Some(s) => s.capitalize
 case None => “No input provided”
}

Similarly, since parseInt returns an Option[String], we are *forced* to deal with the case where the parse failed. We must deal with every possible program state, not just the nice ones. Without forcing the programmer to deal with these cases, they will manifest as runtime errors.

We don’t have to match every time we want to work with an Option. We can use the standard higher-order function map to make our lives easier. map is defined as follows:

def map[B](f: (A) => B): Option[B] = {
 this match {
   case Some(a) => Some(f(a))
   case None => None
 }
}

We can use it to chain computations like so:

val input: Option[String] = get_user_input()
input.map(_.capitalize)

This capitalizes the input string, if provided, getting back an Option[String].

We can also use flatMap to compose option-valued functions. flatMap is defined as follows:

def flatMap[B](f: (A) => Option[B]): Option[B] = {
  this match {
    case Some(a) => f(a)
    case None => None
  }
}

For example, we can read input from the user and attempt to convert the input to an integer:

val input: Option[String] = get_user_input()
input.flatMap(parseInt) 

Another advantage of Option is that it applies to any type. In many languages, only reference types (such as objects) are nullable, while primitive types are not. Instead, programmers often have to rely on nasty tricks to represent missing primitive values, such as using -1 to represent a missing int (as in Java’s indexOf method).

Finally, Option can be arbitrarily nested. Let’s say we have a Map of people to phone numbers. We don’t know everyone who exists, so not everyone is in this map. Other times, we know of a person but they have requested that their phone number not be made available, so we represent phone numbers as an Option[String], with None representing the hidden information¹.

The map has type Map[String, Option[String]], and if we wanted to get a user’s phone number, the return type would be Option[Option[String]]. This represents that the person may or may not be in the map, and if they are, they may or may not have their phone number hidden. Using Null, we would just have Null for both cases, and couldn’t distinguish missing from blocked numbers.

Either

Exception handling is notoriously fickle. We programmers often like to imagine our code only takes the good path, while sweeping error cases under the rug. Adding error-handling code will inevitably make the code more complex, but it’s necessary. The question is how to represent errors.

In C, sentinel values were often used (along with setting the global variable errno!). Then exceptions were added in languages like Java and C++. Both these approaches have disadvantages. A sentinel value requires the user of the API to memorize which return values are valid and which indicate errors (and what errors they indicate); exceptions are more descriptive, but they change the control flow of the program (like goto), and it’s often difficult to figure out precisely which exceptions a function will throw. Fortunately, Scala supports algebraic data types, so we can model error cases directly as part of our domain.

For this we use Option’s beefed-up sibling, Either²:

sealed trait Either[A, B]
final case class Left[A] extends Either[A, Nothing]
final case class Right[B] extends Either[Nothing, B]

In theory, Either can represent a choice between any two types, but in practice, it is used for error-handling, with Right (analogous to Some) representing the successful computation of a value of type B, and Left representing a failure of type A. The type A can be anything; most often, it is an algebraic data type representing the possible error cases.

Let’s say we want to read from a file, using the simple function readFile(path: String): String which, given a pathname, returns all the file’s contents as a String. There are two error cases: the file may not exist, or we may not have permission to read it. They are represented as the following ADT:

sealed trait FileError
final case object FileNotFound extends FileError
final case object InsufficientPermissions extends FileError

Using exception-style error-handling, readFile would throw one of these two exceptions in case of an error. There are two problems with this approach:

1. The function signature indicates nothing about which exceptions may be thrown
2. The programmer is not forced to deal with these errors

Instead, we can rewrite the function using Either:

readFile(path: String): Either[FileError, String]

Now, when using the function, we use pattern-matching to deal with the errors:

readFile(“cheat_codes.txt”) match {
 case Left(err) =>
   err match {
     case FileNotFound => …
     case InsufficientPermissions => …
   }
   case Right(contents) => …
 }

As an added benefit, if the author of the readFile function later decides to add FileTooLarge as another exception, our code will fail to compile and we’ll be forced to handle this new case in our pattern-match.

Like Option, Either also supports map and flatMap functions, with the difference being that both operate on the Right case, and simply pass through the left case unchanged.

State

Imperative programming makes heavy use of mutable variables and data structures. Functional programming discourages this approach, promoting immutability instead. This often makes for simpler, easier-to-reason about code.

For example, let’s say we’re creating a rogue-like game, and want each enemy to have a random amount of health, random attack power, and either be a ghost or a goblin. We need to generate two pseudo-random integers and a boolean. Random number generators need a seed value to generate a sequence from, so we might have a class that looks something like this:

class Random(var seed: Long) {
  private def nextSeed(): Unit = {
    seed = seed * 6364136223846793005L + 1442695040888963407L
  }
  def nextInt(): Int = {
    nextSeed()
    return seed
  }
  def nextBool(): Bool = {
    nextSeed()
    return seed >= 0
  }
}

Notice how seed is internal to the Random class, and destructively updated.

We use the class like so:

val random = new Random(13l)
val health = random.nextInt()
val attack = random.nextInt()
val isGhost = random.nextBool()

This goes agains the functional paradigm (and isn’t even possible in pure functional languages like Haskell). We want seed to be immutable, but this poses a problem: nextSeed needs to update the seed. Since it can’t mutate, it must return the updated value instead:

class Random {
private def nextSeed(seed: Long): Long = {
  return curSeed * 6364136223846793005L + 1442695040888963407L
}
def nextInt(seed: Long): (Long, Int) = {
  return (nextSeed(seed), seed)
}
def nextBool(seed: Long): (Long, Boolean) = {
  return (nextSeed(seed), seed >= 0)
}
}

To use it:

val random = new Random
val (seed2, health) = random.nextInt(seed1)
val (seed3, attack) = random.nextInt(seed2)
val (seed4, isGhost) = random.nextBool(seed3)

Our code is now pure³. Moreover, there’s a common pattern here: we’ve essentially turned every function into one that, in addition to whatever it was doing previously, takes in and returns some kind of state (in this case, the seed). Thus, a stateful computation represents a function of type

S => (S, A)

where A is the return type and S is the state type. In Scala, we can model this as a type alias:

type State[S, A] = S => (S, A)

The state for our random class is just a single Long seed, so we can create a more specialized type alias:

type RandState[A] = State[Long, A]

Thus, our functions have type nextInt: RandState[Int] and nextBoolean: RandState[Boolean].

Once again, we can define map and flatMap functions:

def map[S, A, B](s: State[S, A], f: A => B): State[S, B] = {
  x: S => 
     val (state, a) = s(x)
     (state, f(a))
}
def flatMap[S, A, B](s: State[S, A], f: A => State[S, B]): State[S, B]) = {
  x: S =>
    val (state, a) = s(x)
    f(a)(state)
}

We can use these functions to simplify the above code:

val random = new Random
val (health, attack, isGhost) = random.nextInt.flatMap(health => 
  random.nextInt.flatMap(attack => 
    random.nextBool.map(isGhost =>
      (health, attack, isGhost))))

Of course, I haven’t explained yet why removing mutable state is desirable.

1. It makes unit testing easier. We can test each function in isolation, by simply passing in some known state that we construct, instead of fudging with various functions to get our internal state to where we want it.
2. We can inspect our state. At any point we can print out our current state for debugging or logging purposes. This gets more useful the more complex our state is.
3. We can reuse a previous state. We always have the entire history for us to use. For example, imagine we wanted to regenerate several enemies with the same health but different attack power. We could reuse the same state for the two health values.
4. Because our functions are pure, we get referential transparency, and by extension equational reasoning. This allows a nice, mathematical method of reasoning about program execution.

This example used a very simple state consistent of a single Long. The benefits of State get more pronounced with more complex, deeply-nested data structures. Here are some more examples of what State could be:

• The state of a TCP Connection (i.e. its finite-state machine) as it is established, used, and torn down
• The state of a database as it is read and written
• A list of non-fatal errors during user input processing
• The state of the entire world in a video game

A word on monads

You may be objecting that the code above is more verbose compared to the impure equivalent. In my mind this is not necessarily unwelcome; verbose code is often more clear and honest. That being said, there are ways of working with compound types that reduce boilerplate. The best known of these patterns is the monad — in fact, all of the above types are monads. A monad is just any type-constructor F that comes with two higher-order functions map[B](f: (A) => B): F[B] and flatMap[B](f: (A) => F[B]): F[B], which we have already explored.⁴. I didn’t bring this up until now because I wanted to deemphasize monads, which are the bane of many FP newcomers. My intent was to demonstrate that it is both possible and productive to do FP without using monads, and I hope I’ve done that.

However, once you are comfortable with one or two of the above examples, it is beneficial to learn how to use monadic programming, as it can greatly simplify your code. These functions are used to allow a form of syntactic sugar called a for-comprehension. As an example, the State example could be rewritten as:

val random = new Random
for {
  health <- random.nextInt
  attack <- random.nextInt
  isGhost <- random.nextBool
} yield (health, attack, isGhost)

with the state now being threaded implicitly through the state functions, more closely mirroring our original imperative code. Likewise, IO, covered below, is almost always used monadically, which is why it is sometimes misleadingly called “the IO monad”.

IO

To be useful to humans, computer programs must interact with the outside world. We type on a keyboard and watch output display on a screen. But even without a human in the way, interaction between programs is impure. Any of the following tasks involve IO:

• Reading/writing to a file
• Asking the hardware for random bits
• Communicating with an external database
• Receiving input from the keyboard
• Rendering to the framebuffer
• Printing to the console

As with imperative programming, these are all necessary in functional programming as well. But they are at the same time disallowed. Why is this?

The fundamental dichotomy between imperative and functional programming is that of statements vs expressions. Expressions are pure computations that are evaluated to yield a result (think arithmetic expressions as the canonical example). Statements are commands to be executed that interact with, and possibly alter, the world. As a rule-of-thumb, in C-like languages, statements usually end in a semi-colon, whereas expressions do not. The important difference between the two, and the reason expressions are preferred, is because expressions compose, while statements do not.

For example, let’s say I want to get input from my user, uppercase it, and print it back:

val input = scala.io.StdIn.readLine()
println(input.toUpperCase)

Since both reading from and writing to the console are statements, they are not composable. By this I mean there is no way to wrap them up and reuse them. For example this isn’t possible:

val shout = {
  val input = scala.io.StdIn.readLine()
  println(input.toUpperCase)
}

This is valid code, but it doesn’t encapsulate the action as intended. Instead it will immediately prompt for input and print out the result, and what is stored in shout is only the result of println, which is Unit.

Now we get to the crucial point: IO allows us to treat statements as expressions. With reified IO, I can treat this block of code as a subroutine:

val shout = IO {
  val input = scala.io.StdIn.readLine()
  println(input.toUpperCase)
}

The type of shout is now IO[Unit] — shout encapsulates the action. This means I can reuse it. For example:

val shoutTwice = shout >> shout

This composes the action with itself. The >> symbol means: do one IO action followed by the other. I can also pass it to another function:

def doSomethingWithIO[A](action: IO[A]): IO[A] = …

This function will take in my action, possibly modify it in some way, and return a new action. This lets us compose complex programs out of small ones, which is essential for modularity.

Once we’ve defined map and flatMap for IO (which I will not do here), we can also use them in a for-comprehension:

for {
  url <- scala.io.StdIn.readLine()
  webpage <- httpGet(url)
} yield webpage

At some point we actually have to run our IO. This is done by calling unsafeRunSync(), which executes the reified commands, and extracts the underlying value. As a matter of principle, this should only be done once, at the very end of a program.

Reification

A common theme to the above is that of reification. To reify means to make an abstract concept concrete — something we can get our hands on. Option reifies missing values / null, Either reifies exceptions, State reifies mutable state, and IO reifies input/output. Reification is a powerful technique, giving us more control over our programs, at the cost of added complexity. Concepts that were once part of the runtime are now something we as programmers have to deal with.

Conclusion

Using functional programming creates new constraints, but also new opportunities. We can safely represent missing values, errors, state, and input/output in our programs. This can come at the cost of some verbosity, and requires us to rewire our brains, but results in easier-to-reason-about, more composable code. Of course, as with any methodology, using pure functional programming isn’t the correct choice in every scenario⁵. Thankfully, Scala gives us the choice to use imperative programming features when appropriate, and it is our job as programmers to use good taste and common sense to keep our code clean.

Footnotes

1. This is not the best design to use in this situation — it is only for the sake of example
2. There are also other patterns for dealing with errors, such as Cat’s Validated, but Either is the simplest
3. One might object that the code is also more verbose, which is true. I would counter that verbosity can often lead to more immediately understandable code, though see the last section for how this might be cleaned up anyway.
4. Technically, it’s anything with a flatMap and pure(a: A): F[A] functions, but this isn’t relevant for our purposes.
5. More specifically, I can think of a few examples where foregoing State or IO has kept my code simpler, but I have never once needed to resort to using Null.

Photo by Blake Connally on Unsplash