# Functional Side effects with Applicatives, Part 2

## Modeling the reading of state

--

This is part two of a three-part series on effectful programming with applicative functors. In part one we saw that many imperative side effects can be encapsulated into well-behaved computational effects by modeling the side effect as a modification to state within a given context and then making this context into an applicative functor. We used this to implement a simple applicative parser, which provided the effects of consuming input and potentially failing, and saw that `liftA`

let us compose the effects of parsers in order to easily parse compound data structures. (If you haven’t read part one, I highly recommend doing so before continuing.)

This post will implement a solution to another problem in much the same way that we approached parsing. Our motivating example will be a simple evaluator for lisp-like arithmetic expressions. We’ll work with ASTs (abstract syntax trees, data structures describing the results of parsing a programming language) representing terms like these:

`(+ 1 (* 4 2))`

(+ foo (* 4 bar))

(+ foo (let bar 5 (+ 1 (* 4 bar))))

We’ll start with an implementation of plain arithmetic, and then see how we can use applicatives to extend this implementation to support reading and writing the values of variables within our expressions. We’ll also see some useful patterns for doing typed functional programming in JavaScript along the way.

## The base implementation

First, let’s write a beginning implementation which doesn’t support expressions with variables. Here’s a definition of our AST:

type Expr

= Val

| Plus

| Times

;class Num {

value: number;

constructor(value: number) {

this.value = value;

}

}class Plus {

left: Expr;

right: Expr;

constructor(left: Expr, right: Expr) {

this.left = left;

this.right = right;

}

}class Times {

left: Expr;

right: Expr;

constructor(left: Expr, right: Expr) {

this.left = left;

this.right = right;

}

}

We declare `Expr`

as a union type, which can hold three different types of data: a value, an addition, or a multiplication. Each of these types of data is declared as its own class; this will make it easy for us to differentiate them later.

Next we’ll implement a function which evaluates an expression to a number. Our `Expr`

data type is recursive, so the most trivial implementation of a function on it will be too:

const plus = (a, b) => a + b,

times = (a, b) => a * b;function evaluate(expr: Expr) : number {

return expr instanceof Num ?

expr.value : expr instanceof Plus ?

plus(evaluate(expr.left), evaluate(expr.right)) : /* expr is a Times */

times(evaluate(expr.left), evaluate(expr.right));

}

*(If you’re not familiar with nested ternary expressions, I’d recommend reading the **MDN docs**. This was the motivation for representing our data as classes; **instanceof** gives us an infallible way to distinguish them, and Flow’s type refinements allow our type system to know what concrete type we’re dealing with in each case.)*

To use this, we just create an AST corresponding to a given expression and evaluate it:

// corresponds to (+ 1 (* 4 2))

const expr = new Plus(

new Num(1),

new Times(

new Num(4),

new Num(2)));console.log(evaluate(expr)); // 9

## Supporting variables by adding an environment

Operating on plain numbers is fine, but we also want to be able to evaluate expressions like `(+ foo (* 4 bar))`

, where “foo” and “bar” are variables in a larger scope. To support this, we need to add a context where names are bound to values. We’ll call this `Env`

:

`export class Env<X, Y> {`

contents: Map<X, Y>;

constructor(contents: Map<X, Y>) {

this.contents = contents;

}

}

We could consume an `Env`

by manually pulling it apart and interacting with its `contents`

field, but this would be a poor separation of concerns. Rather than couple our business logic to the internal structure of `Env`

, we’ll write a helper to fetch the value corresponding to a particular name:

function fetch<X, Y>(name: X, env: Env<X, Y>) : Y {

if (!env.contents.has(name))

throw new Error("Referenced an undefined variable!"); return (env.contents.get(name) : any);

}

There are a couple of alarming things about this function. One is the unsafe typecast, and this has a good explanation: Flow’s type refinements don’t extend to functions like `has`

, so while we know that `contents.get`

will return a value corresponding to a key, Flow thinks that `get`

might return `undefined`

for a missing key. We can’t do an `undefined`

check on the return value of the `get`

, though, because then our function wouldn’t be properly generic: if someone bound the value `undefined`

to the name `foo`

, then fetching `"foo"`

had better return `undefined`

. Thus, an unsafe cast is the least of possible evils here.

The second alarming thing in this function is that it throws an error, a very non-functional way of dealing with failure. We do so for simplicity’s sake, and will remedy this in part three of this series.

We also need to add an AST node for our variable nodes. We’ll call this new type `Var`

, and we’ll add it to our `Expr`

type:

type Expr

= Num

| Plus

| Times

| Var

;class Var {

name: string;

constructor(name: string) {

this.name = name;

}

}

Here’s where the effectful nature of this example comes into play. When we `evaluate`

a node, the value no longer depends solely on that individual node, but also on the state of a larger context (the `Env`

associated with this node.) We could handle this naively by threading the `Env`

through the computation:

function evaluate(expr: Expr, env: Env<string, number>) : number {

return expr instanceof Num ?

expr.value : expr instanceof Plus ?

plus(evaluate(expr.left, env), evaluate(expr.right, env)) : expr instanceof Times ?

times(evaluate(expr.left, env), evaluate(expr.right, env)) : /* expr is a Var */

fetch(expr.name, env);

}

This is very similar to our first parser implementation from part 1. We’ve taken the step of handling a side effect (dependence on values from an outside context) by threading that context’s state through our computation. The downside is that we now have `env`

as an extra argument that has to be passed to each invocation of `evaluate`

, which makes for unsatisfying boilerplate. We’ve also solved the problem for our specific case without saying anything about how to work with computations that depend on an `Env`

in general.

We can do better. We’ll back up and define a general type for computations which depend on an `Env`

. When we want to have a computation depend on a value, the natural way to do this is to pass the value to the computation as a function argument. Thus this will be our type:

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

As one might expect for a post on applicatives, `InEnv`

turns out to be an applicative functor. Here is its implementation:

export function map<X, Y, A, B>(

fn: A => B,

a: InEnv<X, Y, A>) : InEnv<X, Y, B> { return env => fn(a(env));

}export function pure<X, Y, A>(a: A) : InEnv<X, Y, A> {

return env => a;

}export function ap<X, Y, A, B>(

fn: InEnv<X, Y, A => B>,

a: InEnv<X, Y, A>) : InEnv<X, Y, B> { return env => fn(env)(a(env));

}

`map`

creates a new `InEnv`

, which passes the environment through to the computation it’s given, and transforms that function’s result with the given function on the way out. `pure`

creates a new `InEnv`

which discards whatever `Env`

its given and returns the selected value. (This gives good background for why `pure`

is named as such; if our applicative represents some kind of effect, `pure`

creates a value which doesn’t make any use of that effect. In the previous post our `Parser`

applicative had the effect of consuming input and possibly failing, and our `pure`

implementation consumed no input and always succeeded. In this case our `InEnv`

applicative provides the effect of dependence on an environment, and `pure`

disregards that effect by ignoring its `env`

argument.) Finally, `ap`

produces a function which takes an `Env`

and uses it to produce a function `A => B`

and an `A`

, and applies the first to the second to get a `B`

.

These functions all have the nice property of only having one possible implementation which typechecks, making implementing them straightforward.

These signatures may seem strange, because in examples so far `map`

and `ap`

have always had two type variables, and `pure`

has always had one. Here they have four and three, and that’s okay. `X`

and `Y`

are simply passed through as part of the signature, and don’t appear in the function body at all. You can imagine them merging into the `InEnv`

type itself, and the signatures here being something like

`map(fn: InEnvXY<A => B>, a: InEnvXY<A>) : InEnvXY<B>`

The key is that, if you can imagine “partially applying” generics, then for any types `X`

and `Y`

, an `InEnv<X, Y><A>`

is an applicative taking one generic argument, just like all of the applicatives we’ve seen so far.

We can also implement `liftA`

on our new applicative in the usual way:

`export function liftA2<X, Y, A, B, R>(fn: A => B => R) `

: (InEnv<X, Y, A>, InEnv<X, Y, B>) => InEnv<X, Y, R> {

return (a, b) => ap(map(fn, a), b);

}

*(As I mentioned in my post introducing applicatives, there are ways to derive the implementation of **liftA** from the implementations of **ap** and **map** automatically, but limitations in Flow means that this requires **type system tricks** which are beyond the scope of these post.)*

Now that we have a type and applicative instance for our environment-dependent computations, let’s reimplement evaluation. `evaluate`

takes an `Expr`

and returns a value which depends on an environment, and it specializes the types of the names and values involved to strings and numbers, so it will have the type:

`Expr => InEnv<string, number, number>`

If we expand out the definition of `InEnv`

, we can see that this is the type

`Expr => Env<string, number> => number`

which is the curried form of our naive `evalutate`

function’s signature.

To fill out the implementation of `evaluate`

, we‘ll need a case for each of the types in `Expr`

: `Num`

, `Plus`

, `Times`

and `Val`

. We have what we need for the first three of these:

const plus = liftA2(a => b => a + b),

times = liftA2(a => b => a * b);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 is a Var */

?????????????

}

For the `Num`

case, we have a plain number, and we want a number wrapped in the `InEnv`

functor. `pure`

gives us what we need here.

For `Plus`

and `Times`

, we want to apply a normal function (adding and multiplying numbers) to the results of a recursive invocation of `evaluate`

, which will return a number inside an `InEnv`

context. This is the essential purpose of an applicative functor; we just need to `liftA`

our addition and multiplication functions into the relevant functor.

It’s worth going back and comparing what we have now to our first, variable-less implementation of `evaluate`

. The type signature returns a functor instead of a plain value, the `Num`

case has changed to use `pure`

instead of returning the value directly, and `plus`

and `times`

refer to lifted functions rather than normal ones, but the structure of the `Num`

, `Plus`

and `Times`

cases are otherwise unchanged. This is the essence of applicatives: writing normal code which applies functions to values even though we’re inside an effectful context.

To complete `evaluate`

, we need to handle the `Var`

case. To do this, lets modify our `fetch`

function to match our new signatures:

function fetch<X, Y>(name: X) : InEnv<X, Y, Y> {

return env => {

if (!env.contents.has(name))

throw new Error("Referenced an undefined variable!"); return (env.contents.get(name) : any);

};

}

If we piece apart the type signature of `fetch`

like we did with `evaluate`

, we can see that all we’ve done here is curried our initial `fetch`

function. Now that `fetch`

returns the same type as `evaluate`

, completing our implementation is easy:

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 is a Var */

fetch(expr);

}

We can test this by manually creating and evaluating an expression in an environment:

const env = new Env(new Map([

["foo", 2],

["bar", 3]

]));// corresponds to (+ foo (* 4 bar))

const expr = new Plus(

new Var("foo"),

new Times(

new Num(4),

new Var("bar")));console.log(evaluate(expr)(env)); // 14

Success.

In this post we saw a more realistic example of a case where applicatives can be useful, and walked through the process of refactoring a messy solution using manual state threading into a cleaner applicative one. We started with a pure, effect-free arithmetic evaluator, and added support for the effect of reading state from an environment. Importantly, we did so in a generic and composable way, by implementing a reusable `InEnv`

abstraction and then lifting our arithmetic logic into `InEnv`

’s context. In part three of this series we’ll take this a step further by adding another effect to `InEnv`

which allows the writing of state. This will let us fully implement our arithmetic evaluator by adding a `Let`

node to our AST which modifies state within its scope. We’ll also see how we can add additional effects by composing `InEnv`

with other applicatives, and dig into the common building blocks of effectful applicative solutions.

*All code samples from this post may be found **here**.*

*This is part of my series on algebraic structures. A list of all posts in the series may be found **here**.*

*Thanks to **Lizz Katsnelson** for editing this post.*