# Functional Side effects with Applicatives, Part 3

This is the final part of a three-part series on effectful programming with applicative functors. In the last two posts we’ve covered what computational effects are, and how we can use them in conjunction with applicative functors to capture side effects in functional code. In part one we did this to implement composable parsers; in part two we implemented a general applicative representing the effect of reading from an environment and used this to implement an evaluator for an AST representing arithmetic expressions. (If you have not read these posts, I recommend doing so before continuing with this one.)

In this post we’ll expand upon the example from part two, adding support for writing state as well as reading it. We’ll also see how applicative composition gives us an easy way to make our solution handle failures gracefully. Finally we’ll inspect our completed solution, see how its component pieces typify the building blocks involved in effectful applicative programming, and learn how the mathematical notion of “parametricity” gives us confidence that an applicative solution enforces a strong separation of concerns.

## Modifying state

Now that our `evaluate` function supports variables, let’s go a step farther and add the ability to change the value of variables within some scope. This will allow us to evaluate expressions like `(let x 1 (+ x 2))`, which assigns the value `1` to `x` and evaluates to `3`. As before, we’ll add a new data type to our `Expr` type:

`type Expr  = Num  | Plus  | Times  | Var  | Let  ;class Let {  name: string;  value: number;  scope: Expr;  constructor(name: string, value: number, scope: Expr) {    this.name = name;    this.value = value;    this.scope = scope;  }}`

Adding the support for `Let` to our `evaluate` function is as simple as it was for `Var`: we just add another entry to the conditional. In this case, we’ll offload the logic to an `alias` function which we have not yet written:

`function evaluate(expr: Expr) : InEnv<string, number, number> {  return expr instanceof Num ?     pure(expr.value)  : expr instanceof Plus ?    plus(evaluate(expr.left), evaluate(expr.right))  : expr instanceof Times ?    times(evaluate(expr.left), evaluate(expr.right))  : expr instanceof Var ?    fetch(expr)  : /* expr is a Let */    alias(expr.name, expr.value, evaluate(expr.scope));  }`

Note that inside the `Let` case we recursively evaluate the scope contained by the `let` block, and then pass the results of that evaluation into `alias`. If we had implemented `evaluate` by manually threading the environment through (as we did in our naive implementation in the last section) then we would have needed to modify the environment first, and then pass the modified environment into `evaluate`. The approach we’re using here can be thought of as “evaluate the inner scope, getting back a value in an `InEnv` context, and then add the effect of a state change to that context.” In order to model a changing state, `alias` will return a function which takes an environment, modifies that environment, and then passes that environment into the `InEnv` function which `alias` wraps. As usual, we will accomplish this modification by copying the input and modifying the copy:

`function alias<X, Y, A>(  name: X,   value: Y,   contents: InEnv<X, Y, A>) : InEnv<X, Y, A> {  return env => {    const newEnvContents = new Map(env.contents);    newEnvContents.set(name, value);    return contents(new Env(newEnvContents));  };}`

With that, we can see our solution in action:

`const env = new Env(new Map([  ["foo", 2],  ["bar", 3]]));// (+ foo (let bar 5 (+ 1 (* 4 bar))))const expr = new Plus(  new Var("foo"),  new Let(    "bar", 5,    new Plus(      new Num(1),      new Times(        new Num(4),        new Var("bar")))));console.log(evaluate(expr)(env)); // 23`

More effects are possible with our `Env` type. As an exercise, consider trying to extend the sample code for this post with a `Copy` type, which works like `Let` but copies the current value of one variable to another.

## Dealing with failure by composing different applicatives

Remember this?

`if (!env.contents.has(name))  throw new Error("Referenced an undefined variable!");`

In cases where a computation can fail, rather than perform a side effect like throwing an exception in the case of failure, we can use an additional applicative context which allows us to express failure as an effect. Fortunately we already have something which will let us do this: `Maybe`.

We’ll do this by saying that any computation in the `InEnv` applicative might fail. This is easy to express with a slight change to our types:

`type InEnv<X, Y, A> = Env<X, Y> => A;`

turns into

`type InMaybeEnv<X, Y, A> = InEnv<X, Y, Maybe<A>>;`

In my first post on applicatives I mentioned that the composition of applicatives is always applicative. If we have applicatives `F<A>` and `G<A>`, then we can mechanically produce the `map`, `ap`, and `pure` functions for `F<G<A>>`:

`type FG<A> = F<G<A>>function mapFG<A, B>(fn: A => B, a: FG<A>) : FG<B> {  return mapF(x => mapG(fn, x), a);}function pureFG<A>(a: A) : FG<A> {  return pureF(pureG(a));}function ap<A, B>(fn: FG<A => B>, a: FG<A>) : FG<B> {  return liftA2F(curry2(apG))(fn, a)}`

In our case we can import the `map`, `ap`, and `pure` functions of each applicative as the objects `inEnv` and `maybe`, and make our new composed type an applicative like so:

`function map<X, Y, A, B>(  fn: A => B,  a: InMaybeEnv<X, Y, A>) : InMaybeEnv<X, Y, B> {  return inEnv.map(x => maybe.map(fn, x), a);}function pure<X, Y, A>(a: A) : InMaybeEnv<X, Y, A> {  return inEnv.pure(maybe.pure(a));}function ap<X, Y, A, B>(  fn: InMaybeEnv<X, Y, A => B>,  a: InMaybeEnv<X, Y, A>) : InMaybeEnv<X, Y, B> {  return inEnv.liftA2(curry2(maybe.ap))(fn, a)}`

(Again, we only have to define these by hand because of limits in Flow’s type system. With the right workarounds, we can write a `composeA` function which takes `inEnv` and `maybe` as arguments, and returns an object containing the `map`, `ap` and `pure` defined for the `InMaybeEnv` type.)

Now that we’re in the `Maybe` applicative, `fetch` can be modified to succeed or fail accordingly:

`function fetch<X, Y>(name: X) : InMaybeEnv<X, Y, Y> {  return env => env.contents.has(name) ?    new Just((env.contents.get(name) : any)) :    null;}`

Any time we change the structure of an applicative we need to check each of the functions which touch that applicative’s internal structure for breakage. We’ve updated `of` and `fetch`, but in this case `alias` will still work for our nested case without modification.

The applicative context separates our specific application logic from the general effect logic, so no changes are needed to `evaluate` other than updating its type signature:

`function evaluate(expr: Expr) : InMaybeEnv<string, number, number> {  return expr instanceof Num ?     pure(expr.value)  : expr instanceof Plus ?    plus(evaluate(expr.left), evaluate(expr.right))  : expr instanceof Times ?    times(evaluate(expr.left), evaluate(expr.right))  : expr instanceof Var ?    fetch(expr)  : /* expr is a Let */    alias(expr.name, expr.value, evaluate(expr.scope));  }`

Because `plus` and `times` are defined in terms of `liftA2`, which is defined in terms of `map` and `ap`, our code which combines `InMaybeExpr`s will respond appropriately to the `Maybe` applicative’s affects, and will cause the whole computation to fail if a failure occurs in any piece of it:

`const env = new Env(new Map());// (+ 1 (* foo 2))const expr = new Plus(  new Num(1),  new Times(    new Var("foo"),    new Num(2)))console.log(evaluate(expr2)(env2)); // null`

Much better than throwing an error, and with a minimum of additional code needed.

## What have applicatives given us?

Now that we have a complete solution, it’s worth taking a step back and looking at how the characteristics of our code are determined by the choice of an applicative approach.

Our `evaluate` function has five cases, which fall into two distinct groups:

1. The `Plus` and `Times` cases. These functions called in these cases are produced by using `liftA` on functions which combine plain values, producing functions which combine values inside of applicative contexts.
2. The `Num`, `Var`, and `Let` cases. These cases create applicatives by calling special functions defined for the `InEnv` or `InMaybeEnv` applicative. The `Var` case calls `fetch`, which provides the effect of reading state, and the `Let` case calls `alias`, which provides the effect of modifying state. The `Num` case calls `pure`, which produces a value and the “empty” effect.

These are the building blocks of applicative code. The `InEnv` and `InMaybEnv` functors provides a context which effects can exist in, and functions which operate on the internal structure of these functors create effects. To know what effects are present or possible within a given functor, we only need to look at what effect-creating functions are available. To do useful things with the values inside our effectful context, we use `liftA` to lift functions on the wrapped types into our context. The “magic” of applicatives is that no matter what effects are provided by our effect-creating functions, our lifted functions will be able to compose these effects. (So long as our `map`, `ap`, and `pure` implementations follow the functor laws.)

An important part of the effect-creating functions is that they are completely general, and are decoupled from the concerns of evaluating expressions or anything else regarding our present solution. We can see verify this by looking at their signatures:

`pure<X, Y, A>(A) : InMaybeEnv<X, Y, A>fetch<X, Y>(X) : InMaybeEnv<X, Y, Y>alias<X, Y, A>(X, Y, InMaybeEnv<X, Y, A>) : InMaybeEnv<X, Y, A>`

Because no concrete types appear in these function’s signatures, their logic can’t possibly be coupled to any concrete type. In functional programming, this concept is known as “parametricity”: the guarantee that a function whose types are all type parameters (generics) will behave the same when given arguments of any type. When I commented in the last post that there was only one implementation of `map`, `ap`, and `pure` on `InEnv` which would type check, parametricity was the reason why. There’s only one way that these functions can behave if they’re going to work across all types that they may be given, and the type checker enforces this.

The value of parametricity shouldn’t be underestimated. “Separation of concerns” is considered an important attribute of good software across languages, environments and paradigms, but an exact definition of what constitutes a proper separation of concerns can be hard to pin down. Usually it’s said to mean that “a software component should only have one reason to change”, but this is an incredibly wiggly definition. Looking at a component and asking why it might need to change is largely an exercise of imagination, and decisions about which imagined reasons are worth preemptively guarding against and which aren’t tend to rest on heuristics and gut feelings. When you’re dealing with generic functions, though, you get a rock solid guarantee: a generic function’s concerns cannot possibly be coupled to the concerns of whatever concrete type will eventually be passed to it.

When representing effects using applicatives, this has important implications for our architecture. We’ve separated our logic of how to deal with interpreting an expression (by turning expressions into values and effects) from our logic specifying how to implement a given effect (by reading and writing values in a `Map`). And importantly, when we look at the system with parametricity in mind, our type system proves that these concerns are indeed separate.

For a less mathematical intuition about this, we can just compare our final code (supporting `Var` and `Let`) to our initial, effect-free code. The code looks the same — no extra values threaded through, no new closures or mutable state. By moving ourselves into an applicative context, we’ve gained the ability to work with effects by just applying functions to values, the same way we work with pure, effect-less data. We also know that we’re decoupled because when we changed our `InEnv` applicative by composing it with the `Maybe` applicative, the `evaluate` function which was written in terms of `InEnv` didn’t need to change; our changes were limited to the effect-creating functions which operated on `InEnv`'s internal structure.

This concludes our present tour through applicative functors. It’s been a long and dense journey, so here is a summary of the major points that we’ve seen so far:

• Functors provide a context which can hold values, and a `map` function to apply normal functions to functions in values. `map` can be curried in order to lift single-argument functions on plain values into functions on values in contexts.
• Applicative functors add additional functions and constraints to functors. An applicative gives us a `pure` function which can lift a value of any type into a functor, and an `ap` function which lets us apply functions in a context to values in a context.
• Using `ap` and `map`, we can define `liftA`, which lifts multi-argument functions on plain values into functions on values in context.
• The implementations of `map`, `ap`, and `pure` must follow certain laws. These laws ensure that the things we build on top of applicatives will compose in expected ways.
• Purely functional computations return values. Sometimes, though, a computation may return a value plus something extra. This extra thing is called a “computational effect”. We can create data structures which represent these effects.
• In software, “side effects” are the reading or modification of state in a context which is outside of our current software component. If we can encapsulate this state inside of a component, and represent modifications to it immutably, then we can turn the side effect into a well-behaved computational effect.
• When we encapsulate a computational effect inside an applicative functor, then functions lifted with `liftA` will compose these effects automatically.
• To do effectful applicative programming, we write effect-creating functions, which return an instance of an applicative containing the effect we want. Our effectful code works with the output of these functions, and never touches the internal structure of our applicative context directly.
• The concept of “parametricity” tells us that generic functions are guaranteed to be decoupled from concrete types. Because all of our effect-creating functions are generic, this gives us a mathematical guarantee that we’ve separated our concerns around implementing effects from our concerns around using them.
• Because the composition of applicatives is itself an applicative, we can compose applicatives to add additional effects. When doing so we may need to change our effect-creating functions, but our code that’s written in terms of an applicative will remain unchanged.

The concept of applicative functors can be both deep and subtle, but is an invaluable tool in any functional programmer’s toolbox. Using them allows for the creation of expressive, purely functional code capable of handling cases which are most idiomatically associated with imperative programming. When you find yourself reaching for a side effect, consider how that effect might be expressed as an applicative. You may find your code much more modular and composable as a result.

All code samples from this post may be found here.

As powerful as applicative functors are, there are some cases which they cannot adequately express. In a future post I’ll show some of these cases, and demonstrate how they lead us to a oft-mentioned subtype of applicatives, the monad. You can find all of my posts on algebraic structures here.

Thanks to Lizz Katsnelson for editing this post.

--

--