The Power of Purity

A key concept in functional programming is that of referential purity. A referentially pure function will always return the same value given the same arguments; this unlocks some extremely powerful behaviour that is unavailable to impure functions. This post will examine function purity and show how we can implement memoization as a result.

Let's first compare an impure and a pure function for complete clarity of terms. We'll use JavaScript for these examples, and start with an impure example:

let counter = 0;

function incrementCounter() {
    return ++counter;
}

incrementCounter is an impure function - it has no arguments, yet it will return a different value each time it is called. There is no one-to-one mapping between input and output values. It also has a side-effect - the global variable counter is modified by the function.

A pure counterpart to this function might be this: (remember JavaScript is pass-by-value so we aren't mutating the argument here)

function incrementCounter(previousValue) {
    return ++previousValue;
}

No matter how many times we call the function incrementCounter(2), the return value will always be 3. This is a great advantage - in the impure function the counter variable could have been changed by another part of our code base with unpredictable results. Our pure function is entirely predictable, and predictable is easy.

In some ways, a pure function is equivalent to a lookup table:

Input | Output
1       2
2       3
3       4

If our arguments are finite, then this equivalence is entirely true. Not the case for numbers, but certainly the case with, for example, boolean values:

function negate(boolVal) {
    return !boolVal;
}

Input | Output
True    False
False   True

Interestingly, in Haskell, a functional language, we can actually implement our functions as lookup tables:

negate :: Bool -> Bool
negate True = False
negate False = True

Returning to the world of JavaScript, let's imagine we have a function that takes one argument and does some CPU-intensive calculation, then returns a result. The details don't matter - it only matters that this is a pure function.

function calculate(input) {
    const output = // do something fancy with input
    return output;
}

We know that as a result of the calculate function's purity, it will return the same output for any given input - the expensive calculation only really needs to be done once for each input. Using memoization we can save the calculated result for an input - the next time the function is called with the same input we can return the saved value.

We'll implement it using the ES2015 construct Map:

function memoize() {

    const memo = new Map();
    
    return (input) => {
    
        if (memo.has(input)) {
            return memo.get(input);
        }
        
        const result = // expensive calculation
        
        memo.set(input, result);
        
        return result;
    }
}

const calculate = memoize();

Looking at this function, there is only one line that is specific to the actual operation taking place (// expensive calculation) - if we can abstract this out then we will have a generic memoizer for functions taking one argument. We can do this by passing the function we wish to memoize as an argument to the memoize function, and applying it to the input.

function memoize(fn) {

    const memo = new Map();
    
    return (input) => {
    
        if (memo.has(input)) {
            return memo.get(input);
        }
        
        const result = fn(input);
        
        memo.set(input, result);
        
        return result;
    }
}

function calculate(input) {
    const result = // expensive calculation
    return result;
}

const memoizedCalculate = memoize(calculate);

Our memoize higher-order function can be used to add memoization to any arity-1 pure function. If we have many intensive calculations to perform, then this could speed up our code immensely at very little cost of complexity.

I think memoization is a superbly useful technique, and one that illustrates the power of pure functions. It's one I use every day via the useful reselect library, that uses memoization for redux selectors.