Functional Programming in JavaScript

TL; DR

Functional programming needs a different mindset than most of the developers/software engineers/programmers are used to. In this blog post I explain the main concepts of functional programming with examples written in JavaScript. Additional articles will follow with more in-depth details of Functional Programming in JS.

Source code can be found on GitHub, in the jsFunctionalProgramming repo.

I would like to thank Csaba Hellinger for the support and input he offered for writing this article.


PART 1

Table of Contents

  1. Why Functional Programming
  2. f(x) = = = J(s)
  3. First Class Functions
  4. Tail Call Optimization
  5. Testing Recursive Calls

Functional programming evolves from the Lambda Calculus which (on a very high level) is a Mathematical Abstraction of function representation and how these representations should be evaluated.

Functional programming is a declarative programming paradigm.

Why Functional Programming ? ^

Using functional programming has some specific characteristics:

  1. Avoiding State Change (and mutable data) - one of the characteristics of functional programming is that functions do not change the state of the application, they rather create a new state from the old one.
  2. Declarations vs statements - in functional programming as in Mathematics a declarative approach is used for defining/describing functions.
  3. Idempotence - it means when invoking a function (any number of times) using the same arguments will always have the same result, this also goes hand in hand with avoiding state change.

These three reasons do not seem to mean much at first glance, but if we analyze this more in depth we figure out that because of the three characteristics the following use cases are good candidates for functional programming:

  1. Parallel code execution - because of the Idempotence and Avoiding State Change properties of functional programming, the code written in a functional manner can be parallelized easier since there will not be synchronization issues.
  2. Concise/Compact Code - since functional programming has a declarative approach the code does not have additional algorithmic steps like there is in procedural programming.
  3. Different mindset - once you coded in a real functional programming language you will develop a new mindset and a new way of thinking when writing applications.

f(x) === J(s) ^

Is JavaScript a real (purely) functional programming language?

NO! JavaScript is not a pure functional programming language...

First-class Functions ^

BUT it can be used well for functional programming because it has first-class functions. By definition a programming language has first-class functions, if it handles functions as any other type within the language. For example functions can be passed as arguments to other functions or can be assigned to variables.

We will examine some first class function, but first lets start with building blocks which we need to have in order to use JS as a real functional programming language.

In most of the pure functional programming languages (Haskell, Clean, Erlang) there are no for or while loops, so iterating over lists needs to be done using recursive functions. Pure functional programming languages have language support and are optimized for list comprehension and list concatenation.

Here is an implementation of a functional for loop, we will use this in our code later on, but you will see this has limitations in JS since tail call optimization is not widely supported (yet), but more on this later.

function funcFor(first, last, step, callback) {

    //
    // recursive inner function
    //
    function inner(index) {
        if ((step > 0 && index >= last) || (step < 0 && index < last)) {
            return;
        }

        callback(index);

        //
        // next (proper tail call)
        //
        inner(index + step);
    }

    //
    // start with the first
    //
    inner(first);
}

The inner function contains the stop condition handling, it invokes the callback with the index value and the recursive call inner(index + step) ensures the loop passes on to the next step.

Recursion is an important aspect of functional programming.

Now lets see some real first class functions:

function applyIfAllNumbers(items, fn) {  
    if(areNumbers(items)) {
        return funcMap(items, fn);
    }
    return [];
}

The purpose of the applyIfAllNumbers function is, to invoke the fn function for each number in the items parameter, but ONLY if all the elements in the items array are numbers.

Below are the validator functions:

function areNumbers(numbers) {  
    if (numbers.length === 0) {
        return true;
    }
    else {
        return isNumber(numbers[0]) &&
               areNumbers(numbers.slice(1));
    }
}

function isNumber(n) {  
    return isFinite(n) && +n === n;
}

The code is straightforward, the isNumber returns true if the parameter is a number, otherwise false. The areNumbers reuses the isNumber to determine if all the elements in the numbers array are numbers or not(again, recursion was used to implement the logic).

Another example is applyForNumbersOnly:

function applyForNumbersOnly(items, fn) {  
    let numbers = filter(items, isNumber);
    return funcMap(numbers, fn);
}

Which can be simplified even more:

function applyForNumbersOnly(items, fn) {  
    return funcMap(filter(items, isNumber), fn);
}

applyForNumbersOnly invokes the fn method only for numbers in the items collection.

The funcMap function is the re-implementation of the well known map function from functional programming, but here I used the funcForEach implementation to create it:

function funcForEach(items, fn) {  
    return funcFor(0, items.length, 1, function(idx) {
        fn(items[idx]);
    });
}

function funcMap(items, fn) {  
    let result = [];
    funcForEach(items, function(item) {
        result.push(fn(item));
    });
    return result;
}

Last we have the filter function which, again, uses recursion to apply the filter logic.

function filter(input, callback) {  
    function inner(input, callback, index, output) {
        if (index === input.length) {
            return output;
        }
        return inner(input, 
                     callback, 
                     index + 1, 
                     callback(input[index]) ? output.concat(input[index]) : output);
    }
    return inner(input, callback, 0, []);
}

Tail call optimization (TCO) in JS ^

In the EcmaScript 2015 TCO specs there are some use-cases defined when the language should support tail call optimization. One of the most important requirements is to "use strict" mode in your code, otherwise JS cannot apply the TCO.

There is no built in method to detect if a browser supports TCO or not, this has to be done through code:

"use strict";

function isTCOSupported() {  
    const outerStackLen = new Error().stack.length;
    // name of the inner function mustn't be longer than the outer!
    return (function inner() {
        const innerStackLen = new Error().stack.length;
        return innerStackLen <= outerStackLen;
    }());
}

console.log(isTCOSupported() ? "TCO Available" : "TCO N/A");  

Here is an example of the functional re-implementation of Math.pow function, which can benefit from the TCO in EcmaScript 2015.

This pow implementation uses ES6 default parameters to simplify implementation.

function powES6(base, power, result=base) {  
    if (power === 0) {
        return 1;
    }

    if (power === 1) {
        return result;
    }

    return powES6(base, power - 1, result * base);
}

First thing to note is that we have three arguments instead of two. The third parameter holds the result of the calculation. We have to carry the result around in order to have an implementation where our recursive call is really a tail call and JS can use his TCO technique.

In case we cannot use ES6 features, besides that I do not recommend using recursive implementation because the language will not offer support for optimization, the implementation is more complex:

function recursivePow(base, power, result) {  
    if (power === 0) {
        return 1;
    }
    else if(power === 1) {
        return result;
    }

    return recursivePow(base, power - 1, result * base);
}

function pow(base, power) {  
    return recursivePow(base, power, base);
}

We separated the recursive calculation to another function recursivePow, this takes three arguments as the powES6 did. Using a new function and passing the base parameter to it we implemented the default parameter initialization logic from ES6.

On this page you can check how widely is the TCO implemented by different browsers and platforms.

Since Safari 10 is the browser which fully supports TCO (at the time of writing this article) I will run some tests with the pow function to see how well does it perform.

Testing Recursive Calls ^

I used the powES6 and pow functions with the following test code:

"use strict";

function stressPow(n) {  
    var result = [];
    for (var i=0; i<n; ++i) {
        result.push(
          pow(2, 0),
          pow(2, 1),
          pow(2, 2),
          pow(2, 3),
          pow(2, 4),
          pow(2, 5),
          pow(2, 10),
          pow(2, 20),
          pow(2, 30),
          pow(1, 10000),
          pow(2, 40),
          pow(3, 10),
          pow(4, 15),
          pow(1, 11000),
          pow(3.22, 125),
          pow(3.1415, 89),
          pow(7, 2500),
          pow(2, 13000)
        );
    }

    return result;
}

var start = performance.now();  
var result_standard = stressPow(2500);  
var duration = performance.now() - start;  
console.log(result_standard);  
console.log(`Duration: ${duration} ms.`);

I executed this JS code on Chrome v55, Firefox v50, Safari v9.2 and Safari v10.

Nr. Chrome v55 (ms) FF v50 (ms) Safari 9.2 (ms) Safari 10 (ms)
1 1076.12 499.1 431.94 398.51
2 1061.20 499.36 479.20 373.59
3 1069.27 518.75 415.98 368.53
4 1056.84 499.98 423.72 373.79
5 1043.06 511.05 429.64 361.37
6 1056.72 505.59 424.78 361.26
7 1096.32 507.68 427.83 358.30
8 1099.12 515.85 436.83 356.68
9 1016.51 504.91 425.74 362.77
10 1056.65 530.31 430.95 368.32
AVG 1063.18 509.25 432.66 368.33
Conclusion

Looking at the measurements it can be seen that Safari is the best performer if it comes to recursive function execution. Safari 10 with his TCO optimization support for JavaScript is the fastest, around ~2.8 times faster than running the code inside Chrome. Firefox performs almost as good as Safari 9.2 which was a surprise for me.

If you enjoyed reading this blog post, please share it or like the Facebook page of the website to get regular updates. You can also follow us @dealwithjs.

Lets stay functional!

PART 2 will come shortly with high order functions and samples how to implement procedural code in functional style.