An Introduction to Functional Programming in JavaScript

A couple of months ago I decided to start learning Haskell as I was interested in seeing what functional programming was all about and how I could embrace it improve my all round programming skills. What quickly became apparent to me with functional programming is that there is a mathematical beauty and purity to it and this, for me at least, results in writing cleaner, more readable code. As I got more into the subject of functional programming I began to think how I could implement functional patterns in a website I am currently developing which has a large client-side data processing functionality and it turns out, after a little digging, that JavaScript is well suited to implementing these functional patterns.

The inspiration behind this post and the functional patterns which are implemented are two brilliant talks by Brian Lonsdorf, and his LambdaJS JavaScript Libraray, I recommend that anybody interested in functional programming in JavaScript watches these: Hey Underscore, You’re Doing It Wrong! and Functional Programming Patterns For The Non-Functional Mind.

What Is Functional Programming?

I won’t spend too much time formally describing what functional programming is as far smarter people than I have already done that job far better than I ever could.

The programming paradigm that most people are familiar with, which most people (as far as I am aware) learn first, is imperative programming (of which object-oriented-programming is an example). Imperative programming is the style traditionally used in languages such as C/C++, Java, Python, Perl etc. Imperative programs are written as a very exacting set of procedures that a computer must follow in order to perform a calculation, the order of execution is highly important and strict and well defined control structures are used (such as loops and branches) to guide the flow of the program. In imperative programming state is very important, variables are used to store the current state of the program (i.e. to store iterator values, temporary variables used to store data until the next stage of the calculation etc), it is changes in these current states that dictate the flow of the program. Taking this into account it can be seen how imperative programming is often described as algorithmic programming.

“Object Orientation makes code understandable by encapsulating moving parts. Functional programming makes code understandable by minimising moving parts”

Michael Feathers

Functional programming on the other hand is stateless. The way of modifying data is through the manipulation and evaluation of purely functional transformations applied to data. Due to functional programming being stateless, functions always give the same output for a given input (the outcome of a function is dependent only on the input and nothing else). In functional programming data is immutable, once a value is set, this value does not change (in the mathematical sense that the number 1 is always equal to the value 1), pure functions do not modify the data that variables point to (or the state of any other value outside of the function), they return a new value (which could be itself a function) after carrying out a transformation on the original values (or functions). A key feature of functional programming is higher/first order functions; functions that behave as ‘first class citizens’ in that they can be passed as arguments to functions as well as being returned by functions.

Why JavaScript?

Leaving behind the definition of functional programming, what is it that makes JavaScript suitable for functional programming? The simple answer is that in JavaScript functions are first class objects just like any other data type such as arrays or integers and as first class objects, functions have their own properties and methods. An example of JavaScript function object method is the length method, for an array, applying length to it returns the number of elements that the array contains, in the case of a function, it returns the number of variables defined in the function definition. As functions are objects, just like any other object, they can be passed to functions as arguments and they can also be returned by functions. The ability for functions to receive and return other functions is a fundamental requirement of functional programming.

Example: Calculating Standard Deviation

To compare the two paradigms, consider the example of calculating the standard deviation (biased) of an array of numbers. The process for calculating the standard deviation is as follows:

1. Calculate the arithmetic mean of the array.
2. Subtract the mean from each value in the array.
3. Square each mean subtracted value.
4. Sum the squared variations.
5. Take the square root of the sum.

Full code from this post is available as a Git repository at: Intro to FP in JS

Imperative Implementation

First we will consider the imperative approach:

var array = [1, 2, 3, 4, 5];

var mean = 0;
// Calculate the mean, first by summing each value in the array
for (var i = 0; i < array.length; i++ ) {
    mean += array[i];
}
// And then by dividing by the number of elements in the array
mean /= array.length;

// Subtract the mean from and square each element and sum. 
var squaredVariations = 0;
for (i = 0; i < array.length; i++) {
    squaredVariations += (array[i] - mean) * (array[i] - mean);
}

// find the mean square deviation. 
var meanSquare = squaredVariations / (array.length);

// And now calculate the standard deviation by taking the square root
var std = Math.sqrt(meanSquare);

console.log(std); // >> 1.414

In the above implementation of the standard deviation calculation state is constantly modified, this means that at each stage, every time a calculation is carried out, the value contained by a variable is modified. For example, for the given array of numbers, [1, 2, 3, 4, 5], the mean variable initially points to a value of zero, after the first iteration, this value changes to one and then three. At the same time the iterator, i is constantly changing value. Once the array values have been summed, the mean variable is once again modified by dividing by the length of the array to give the final mean value. This pattern continues through the rest of the program, a calculation is performed and the current state is updated by modifying the value of a variable.

Functional Implementation

And now for the functional implementation, which I will go through this step by step. The task here is to try and calculate the standard deviation using a series of pure functions. Here, rather than storing values (state), variables will point to functions, these functions do not change value, for a given input they always return the same result.

The first task that we need to complete is to sum each of the elements in the array, we do this by defining a function that takes an array and returns a single vale; the sum. To reduce an array to a singular value, we use the reduce function (also known as a fold function). reduce takes three arguments:

1. A function defining how the array will be reduced, this function in turn takes two arguments, an accumulator and the current array value.
2. An initial value for the accumulator to be provided to the reducing function when evaluating the first array element (this value is often taken as the identity value of the reducing function).
3. The array of numbers to be reduced.

In JavaScript arrays have a built in reduce method which accepts a reducing function and an initial value as arguments, in functional programming we want functions rather than methods so we rewrite reduce as a function that takes the array as an argument. We will design our functions following the design patterns and rules used in LambdaJS. The documentation for LambdaJS states the following rules:

1. The data comes last. E.g: str.method(arg) -> method(arg, str)
2. Everything is curried
3. Functions with optional arguments are split into two functions. One with _ at the end that takes the options. E.g: indexOf(x,str) and indexOf_(x,y,str)
4. Every function is pure

We will not be implementing rule 3 as it is outside of the scope of this example and currying (rule 2) will be explained later. Using these rules we can define reduce as:

var reduce = function(func, init, xs) {
    return xs.reduce(func, init);
};

N.B. in functional programming it is convention to us the variable name xs to describe an array of values x.

So, what exactly is reduce doing? We know that func takes two arguments; the current value of the accumulation (initially set to init) and the current element x from xs. The return value of func then becomes the new accumulator value and is passed to func with the next element from xs, this continues until all xs have been passed to func, the result of the reduction is then the final value of the accumulator.

Now we know how the reduction function works it is easy to see that in order to sum the array we need to define func as an addition of its two arguments; the current accumulator value and the current element from xs.

A powerful feature of JavaScript (and a number of other languages) is the ability to define anonymous functions. Also known as a lambda (as in lambda calculus), an anonymous function, as the name suggests, is a function without a named identifier, they are most often used as arguments to other functions and are often not reachable outside of the context in which they are defined. To sum an array of numbers xs, we can pass to reduce an anonymous function that returns the sum of two arguments, an initial value of zero and xs itself:

var xs = [1, 2, 3, 4, 5];

var sumOfxs = reduce(function(a, b) {
    return a + b;
}, 0, xs);

In order to make the above code more modular, reusable and readable we can formally define the anonymous function, we will call this function add, this is a function that will form one of the basic building blocks of our library of functions from which more adventurous functions can be built. Refactoring, the above code becomes:

// Return the sum of two numbers
var add = function(a, b) {
    return a + b;
};

// Calculate the sum with the reduce function
var sumOfxs = reduce(add, 0, xs);

Already the code has become much more readable than the imperative case, to calculate the sum we see that we want to reduce the array down to a single value using addition with an initial value of zero.

Like add, reduce is a function that you would only write once and keep it in a function library, rather than defining it every time it is required. So far, in just calculating the sum of the array of numbers the benefits of a functional approach should be becoming apparent, we have negated the use of a loop, this means we do not have to define an iterator variable and the limits of the iteration, we do not have to manually access the array elements and we do not risk the all too common ‘off by one’ error which is a natural hazard when implementing loop operations. The code is more modular with far fewer exposed moving parts, here the only scope for error is in wrongly defining the sum function or choosing the wrong initial value, given this, any error should be very easy to locate.

As it stands, our sumOfxs function will work perfectly well but we can further refactor this by increasing the level of abstraction even further. We can see that to sum an array, the reducing function will always take add and zero as the first two arguments. We want to define a new function, sum that takes only xs as an argument.

Currying

One of the keys to functional programming is spotting how functions can be further reduced and generalised. In the example of our summing reduce function we can notice that the first two arguments are constant (the add function and initial value). The only argument influencing the outcome of the summation is xs. If the function argument or the initial value argument are altered then the reduction will no longer be a zero-based sum. The aim now is to transform the reduction from a function that takes three arguments, to a sum function that only takes xs as an argument. This is where we meet another of the key concepts of functional programming, currying.

In a nutshell, currying is the process of transforming a function that takes multiple arguments into a function that takes a reduced number of arguments and returns another function until all the arguments of the initial function have been supplied. In function notation this translates as:

f(x, y, z) = g(z) = f'(x, y)(z) where g = f'(x, y) is the curried version of f

Using JavaScript’s built in function methods, it is fairly straight forward to define a ‘currying’ function which makes it possible to curry any other function. To make a function ‘curryable’, we define a curry as a function takes a function as its argument and returns a new curryable function which depending on the number of arguments supplied either returns the result of the complete evaluation of the original function, or another function which accepts the remaining, unsupplied arguments.

var curry = function (fn, fnLength) {
    fnLength = fnLength || fn.length;

    return function () {
        var suppliedArgs = Array.prototype.slice.call(arguments);

        if (suppliedArgs.length >= fn.length) {
            return fn.apply(this, suppliedArgs);
        }

        else if (!suppliedArgs.length) {
            return fn;
        }

        else {
            return curry(
                fn.bind.apply(
                        fn, [this].concat(suppliedArgs)
                ), fnLength - suppliedArgs.length
            );
        }
    };
};

For example, redefining our reduce function as a curryable function:

var reduce = curry(function(func, init, xs) {
    return xs.reduce(func, init);
});

when provided with three arguments, the reduction is evaluated and a value is returned as normal. However, now that it is curryable, if only the first argument (func) is supplied, the reduction cannot be evaluated so a new function is returned which can accept the remaining two arguments (init and xs). In turn, if this new function is only provided with the init argument, another function which accepts the final argument is returned. In function notation this is equivalent to the following:

f(x, y, z) = g(y, z) = h(z) where g = f'(x) and h = g'(y) = f'(x)(y)

and f‘ (f-prime) indicates a curried f. Similarly, if only the first two arguments are supplied to reduce, a new function which only accepts the final argument is returned. In function notation:

f(x, y, z) = g(z) = f'(x, y)(z)

Using this latter case, the sum of an array of numbers can be defined as the function returned by supplying reduce with only two arguments; add and zero.

var sum = reduce(add, 0);

// Test out on an array of numbers
console.log(sum([1,2,3,4,5])); // >> 15

Because reduce(add, 0) returns a function, the above is exactly equivalent to the more verbose:

var sum = function(xs) {
    return reduce(add, 0)(xs) // which == reduce(add, 0, xs)
};

Now we have a general array summing function that we can add to our library of general functions. The mean is now easy to define, it is a function that takes an array and returns the sum of the elements divided by the number of elements:

// define length as a function rather than a method
var length = function(xs) {
    return xs.length;
};

// calculate the mean
var mean = function(xs) {
    return sum(xs) / length(xs);
};

Now that we have calculated the mean of the values in the array functionally, it should be noticed that at no point has any state been saved. The mean is defined purely in terms of functions only dependent on the input data, compared to the imperative version where the state of the summation and iterator values are modified with every iteration through the array.

The next stage in calculating the standard deviation is, for each x in xs, subtract mean(xs) and square the result returning a new array of transformed elements. We do this using the map function. For an array, xs and a function func, map returns a new array of elements containing the result of performing func on each of the elements in xs. This is very similar to reduce only in this case an array is returned as opposed to a single value and the argument func only accepts the current element of xs as its argument. Also like reduce, JavaScript has an inbuilt map method but we again want to define this as a curryable function:

var map = curry(function(func, xs){
    return xs.map(func);
});

Now we can start to define a function to subtract the mean and then square each element of xs. First we will define a square function which just returns the square of the input argument, we then build an anonymous function as an argument to map which subtracts the mean from each element and then squares the result, it is this value that is returned as an element in the new mapped array.

var squaredDeviations = function(xs) {
    return map(function(x) {
        return square(x - mean(xs));
    }, xs);
};

var square = function(x) {
    return x * x;
};

The anonymous function in the above example only takes one argument, x, yet it subtracts the mean of another variable, xs. This is possible due to closure. In JavaScript, functions have access to any variable in the environment (closure) in which they were defined. In our example, the anonymous function is defined within squaredDeviations, as xs is provided to squaredDeviations as an argument, the anonymous function can also access it.

Composition

To complete the calculation of the standard deviation, we just calculate the mean of the squared deviations and take the square root of the mean. Using the mean function we defined earlier we can write:

var std = function(xs) {
    return Math.sqrt(mean(squaredDeviations(xs)));
};

While the above code is descriptive (takes the square root of the mean of the squared deviations) we can improve it further by removing the nesting of functions using another key technique in functional programming; composition. Here we see that the outcome of the calculation is obtained by applying mean to squaredDeviations and then by applying the square root to the result of this. Rather than nesting functions inside one another, we would like to be able to define a new function that is a composition of the nested functions and accepts the inner-most argument of the nested functions as its own argument. In function notation (with ∘ indicating composition), we want the following:

j (x) = f(g(h(x))) where j = f ∘ g ∘ h

Fortunately with JavaScript’s inbuilt function methods, this is fairly easy to implement. We define a new function, compose which accepts a series of functions as arguments and returns a new function which is a composition of the argument functions:

var compose = function() {
    var funcs = arguments;
    return function() {
        var args = arguments;
        for (var i = funcs.length; i-- > 0;) {
            args = [funcs[i].apply(this, args)];
        }
        return args[0];
    };
};

Using this compose function we can write our standard deviation as:

var std = compose(Math.sqrt, mean, squaredDeviations);

// test it out
console.log(std([1,2,3,4,5])); // >> 1.414

// this is the same as:
console.log(compose(Math.sqrt, mean, squaredDeviations)([1,2,3,4,5])) // >> 1.414

// and the same as the nested implementation
console.log(Math.sqrt(mean(squaredDeviations([1,2,3,4,5])))); // >> 1.414

Rather than having the nested functions as previously, by implementing compose, we return a new function which takes one argument, xs and passes this to squaredDeviations the first function (working right to left), the result of this is then passed to mean which the result of is finally passed to the square root function.

As our final code we have:

var square = function(x) {
    return x * x;
};

var add = function(a, b) {
    return a + b;
};

var sum = reduce(add, 0);

var mean = function(xs) {
    return sum(xs) / length(xs);
};

var squaredDeviations = function(xs) {
    return map(function(x) {
        return square(x - mean(xs));
    }, xs);
};

var std = compose(Math.sqrt, mean, squaredDeviations);

Summary

Studying the final functional code, it can be seen that at no point is state recorded, variables do not point to values, they point to functions. Each function is only dependent on its arguments and always returns the same result for a given input, the state of the outside environment has absolutely no bearing on the functionality. We can also see that everything is immutable, once a variable is set, it does not change, for example, mean always points to the same function that takes an array and returns a value, compared to the imperative case where the value of mean is constantly updated to point to the current mean value.

The modularity of the functional code is also a big bonus. Small, highly specific functions are used to carry out a specific task, these functions can then be combined (using composition and currying etc) in any number of ways to create new functions which carry out more complex tasks. In our example code, mean is used twice and this in turn calls our sum function. The high modularity of the code makes testing very simple as each function has a known output for a given input, tests do not have to be written which concentrate on setting the scene (making sure other environment variables are set to the correct state) before hand to make sure that tests pass. It also means that code is highly reusable.

This may be subjective but I also find the functional code much more readable than the imperative code with its loops and iterators. The functional code clearly says that to calculate the standard deviation, we take the square root of the mean of the squared deviations. This is a common feature with functional programming, it tends to say what it is we want to accomplish rather than how we accomplish it as is the way with imperative programs (for loops, constantly modifying state etc).

I do not want this piece to be confused as me saying that we should all adopt functional programming for all occasions because, we should not. The aim of this piece was to give an introduction to functional programming and how it can be implemented in JavaScript with the aim of hopefully writing more simple, clearer code. Most of my work in JavaScript is still largely object oriented but as I am learning, I am implementing more and more functional patters and I am finding that this is improving both my productivity and the robustness of the code I am producing. It may not be for everyone but it can never hurt to look at solving old problems from a new angle.

Full code from this post is available as a Git repository at: Intro to FP in JS