Functional Side effects with Applicatives, Part 1

Bringing structure and composability to mutable state

This is part of my series on algebraic structures. The whole series can be seen here.

In my last post I introduced applicative functors, and showed how they build on plain functors to allow us to apply pure functions to values inside of special contexts. This made our code more generic and composable by letting us specify our logic in pure functions and lift it into whatever context is needed using liftA. This is not all there is to applicatives, though. There are many cases where our logic is inherently connected to a particular context, and where we may want to combine these pieces of logic cleanly. Applicatives can help us in many of these cases, too. This will be the focus of this post: the use of applicatives to represent and compose more complicated effects which are usually the domain of imperative programming. This is the first of a series of three posts which will introduce “computational effects”, explain their relationship with functor contexts and with side effects, and will show examples of using applicatives to write code which handles effects in a composable way.

These posts assume that you’ve read my previous posts on functors and applicatives, and that you are familiar and comfortable with currying. Other than that, no additional functional programming knowledge is assumed. As before, this post will be heavy on example code using JavaScript and Flow.

Effects and contexts

When introducing functors, I said that they represented a value in a context. For a Set, this context is that there could be more than one individual value. For a Promise, this context is asynchronicity, the fact that the value may only exist in the future. For Maybe, this context is nullability, the fact that the computation may fail and not produce any value at all. What is common between these is that they all represent something “extra” that can be produced by a computation, other than the plain values involved. This extra thing is called a “computational effect”, or just an “effect” for short. When we operate inside of a functor context, that functor’s effects become available to us. We call such code “effectful” to distinguish it from code whose output does not contain this extra structure. The effects which we’ve seen up until now are relatively simple, but much more complex ones are possible.

Side effects

When we hear the word “effect” it’s usually while talking about the bogeyman of functional programming, “side effects”. Side effects are scary and bad and seem far removed from the nice abstractions which we’ve built using applicatives so far. In reality, though, side effects are just a subset of computational effects which tend to be poorly behaved. Side effects can be thought of in terms of stateful contexts: code performs a side effect when it reads state from, or modifies the state of, some context which is not fully encapsulated by that code. For instance, code which outputs logs modifies the state of a console, code which creates a file modifies the state of the filesystem, and code which makes a network request modifies the state of the internet. It’s the nature of the context which determines whether something is an actual side effect or a pure computational effect; if we can encapsulate the context and structure it according to laws, then we can regain the benefits of pure code.

Developers who are familiar with unit testing know that it’s important to remove these side effects to enable fast and predictable test suites, and often do so by providing special dependencies which isolate the side-effecting code from the actual world. Code which would normally read from or write to a database instead gets access to a mock database, and is actually interacting with data that’s stored in memory. From the perspective of the “side-effecting” code, nothing has changed, but from the perspective of the system as a whole, the side effects have disappeared. This tells us something important: it’s possible to write code which looks and behaves locally as though it is performing side effects, while allowing those effects to be encapsulated and controlled by its callers.

We will take advantage of this when we use applicatives to replace unconstrained side effects. The general approach takes three steps:

1. Identify the state which is modified by a side effect, and create a representation of that state in memory. Perform the modifications on this data structure instead of on the outside world.
2. Remove the impure mutation from this code by creating new, “modified” copies of data structures and carrying them from step to step of the computation rather than actually performing mutation.
3. Represent the context holding the state explicitly as a functor context, and implement map, pure, and ap, allowing the context to be composed.

Clearly not every side effect can be handled in this way; if your code calls some remote API, it’s unlikely that you’ll be able to encapsulate that entire API in a local data structure. For the cases where this is possible, though, this technique allows us the ability to deal with “side effects” in a structured, functional way. It’s important to note that making our functions pure is only part of the benefit here: we are also interested in making effects explicit and easily composable. In imperative code, it is impossible to tell if a function is doing something extra by just looking at that function’s signature. When we represent effects using functor contexts, we can tell exactly what effects a function is capable of performing by looking at its signature; the only effects possible are those associated with the functor which this function returns.

An effectful computation: Parsing

To make this more concrete we’ll look at a realistic use case for applicatives, in the form of a very basic parser. First we’ll look at what happens when we try to combine parsers without using applicatives, and then we’ll compare this to what we can do using an applicative parser interface.

A parser consumes a string input, and produces either a parsed value, or fails. Further, we’ll give our parsers the ability to consume only a small piece of the string input, which will let us sequence parsers one after the other:

type ParseResult<A> = {
  parsed: A,
  remaining: string
} | null;
type Parser<A> = string => ParseResult<A>;

If you’re used to parsers in an imperative setting, this signature may see a bit strange. Imperative parsers are usually expressed as consuming input from an external stream, and have the side effect of modifying this stream as they run. We will choose not to modify our input, in order to keep our code functional. Instead we will return both a result value and the “modified” input at each step, which is really just a modification of a copy of the input. This is the method of encapsulating side effects which is discussed in the previous section.

Another important thing to note about this signature is that ParseResult is a union type of an actual result object and null. In the case where parsing succeeds, a result object will be returned, but in the cases where an unexpected character is encountered, the parser will return null.

First up, let’s implement a parser for numbers:

const numerals = new Set([
  "0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]);
function number(str: string) : ParseResult<number> {
  let i = 0,
      found = "";
  while(numerals.has(str[i])) {
    found = found.concat(str[i]);
    i++;
  };
  if (!found.length) return null;
  return {
    parsed: parseInt(found),
    remaining: str.slice(found.length)
  };
}

This function takes characters off the front of a string, one at a time, as long as the characters are numeric. Then it turns the string of numbers into an actual number using JavaScript’s built-in parseInt function. If no numbers are found, the parser fails. Let’s see it in action:

console.log(number("123")); // { parsed: 123, remaining: ""}
console.log(number("123abc")); // { parsed: 123, remaining: "abc" }
console.log(number(" 123")); // null

Let’s also implement a function for parsing a specific string:

function string(sought: string) : Parser<string> {
  return input => {
    if (!input.startsWith(sought)) return null;
    return {
      parsed: sought,
      remaining: input.slice(sought.length)
    };
  };
};

While number was a parser, string is a function that takes an argument and returns a parser. Given a string argument, string returns a parser which parses this argument, or which fails if the requested string doesn’t occur at the front of the parser’s input. Let’s see this in action as well:

console.log(string("a")("abc")); // { parsed: "a", remaining: "bc" }
console.log(string("ab")("ab")); // { parsed: "ab", remaining: "" }
console.log(string("bc")("abc")); // null

Given these examples, we can see what effects are part of a Parser context. The main result of executing a parser is the contents of the parsed field out the object the parser outputs. However, the computation may fail, returning a null instead. And further, the computation is stateful: A parser consumes a portion of its input, and returns the state of the unconsumed input alongside its main return value.

Now that we have a couple parsers, let’s try combining them. Here’s a function to parse a number, followed by a dash, followed by a number, and return a pair of the two numbers as its result:

function numberDashNumber(str: string)
  : ParseResult<[number, number]> {
  const first = number(str);
  if (!first) return null;
  const second = string("-")(first.remaining);
  if (!second) return null;
  const third = number(first.remaining);
  if (!third) return null;
  return {
    parsed: [first.parsed, third.parsed],
    remaining: third.remaining
  };
}

All this function does is call three parsers in order, threading the output of each into the input of the next, and then return the result of the parsers that we want. This is a lot of boilerplate to do a simple thing though: it would be nice to be able to compose Parsers without needing detailed knowledge of the ParseResult type. That is to say, we want our code which composes parsers to do so in a way which is generic with regards to parser’s internal structure. To this end, we’re going to make our Parser type an applicative.

Applicative Parsing

To make Parser an applicative functor, we first need to make it a functor with a map function. Mapping over a functor will just be applying a transformation to the parser’s result:

function map<A, B>(fn: A => B, a: Parser<A>) : Parser<B> {
  return str => {
    const parseResult = a(str);
    if (parseResult === null) return null;
    return {
      parsed: fn(parseResult.parsed),
      remaining: parseResult.remaining
    };
  }
};

Then, we need an implementation of pure:

function pure<A>(a: A) : Parser<A> {
  return str => ({
    parsed: a,
    remaining: str
  });
}

pure lifts any plain value into a parser for that value, by creating a parser which returns that value without consuming any input.

Finally, we need the heavy lifter of the three, ap:

function ap<A, B>(fnParser: Parser<A => B>, aParser: Parser<A>) 
  : Parser<B> {
  return str => {
    const firstParse = fnParser(str);
    if (firstParse === null) return null;
    const secondParse = aParser(firstParse.remaining);
    if (secondParse === null) return null;
  
    return {
      parsed: firstParse.parsed(secondParse.parsed),
      remaining: secondParse.remaining
    };
  };
}

ap runs the first parser, producing a function. Then it runs the second parser on the remaining input from the first parser, producing a result of type A. Finally it applies the parsed function to the parsed value, producing a value of type B, and returns this value. The remaining input is whatever is left after applying both given parsers. ap takes care of handling parse failures as well, returning null if either input parser failed. While ap may look complicated, there’s only two possible implementations of it which typecheck and follow the applicative laws: we either do what we did above, or we swap the order in which we apply the two parsers, feeding the output of aParser into fnParser. In this way, the definition of applicatives gives us guard rails which guide our implementation, making us only need to make one real decision about how ap should work.

Using ap and map, we can implement liftA2 and liftA3 in the usual way.

Now that we have an applicative instance for our Parser type, we can reimplement our number-dash-number parser using this applicative interface. First, we need to write the function that will be lifted over the applicative:

function collectNumbers(n1: number, dash: string, n2: number) {
  return [n1, n2];
}

Our goal is to make a parser which consumes a number, a string, and a number from the input string, and returns a pair of numbers. Rather than intermix this logic with the gritty details of parsing, we write a function which deals just with the parser’s output, and isn’t coupled to parsing at all. Then we lift this function over the parser applicative:

const numberDashNumberAgain =
  liftA3(
    curry3(collectNumbers),
    number, string("-"), number);

If you compare this to our first implementation of numberDashNumber, this is much more focused. This also shows us something important about applicatives: liftA doesn’t just let us apply a function to the contents of multiple applicatives; it also sequences the effects of each applicative and combines them. The number and string("-") parsers each consume part of their input string when they’re run. When we run numberDashNumberAgain, the number parser will consume input, advancing through the string, then the string("-") parser will start consuming input where the number parser left off, and will consume a dash, then the last number parser will start consuming input after the dash. numberDashNumberAgain is thus a composition of not only the results of each smaller parser; it is also a composition of each parser’s effects.

In imperative code, side effects pose any number of problems: They’re either left unconstrained and unencapsulated, making our code complex and poorly abstracted, or they require verbose and manual “threading through” of data, as we saw in our first implementation of numberDashNumber. When we throw away unconstrained, imperative side effects in favor of functional computational effects, we gain the ability to work with these effects generically. We could change our definition of the Parser type and our code which composed parsers would continue to work, as long as the new Parser type was still an applicative.

In part two of this post we’ll see a functional implementation of a more complex problem, and walk through the process of using applicatives to add effects to it in a clean and composable way.

All code samples from this post may be found here.

Thanks to Lizz Katsnelson for editing this post.