What is Functional Programming?

Functional programming is a programming paradigm in which programs are built by applying and composing pure functions(more on that later). Unlike the imperative approach(where the computation is expressed by a sequence of statements that alter the state of the program), the functional paradigm is declarative, meaning that the computation is expressed by using only expressions and declarations.

The functional paradigm has its roots on a mathematical formal system of computation, developed by Alonzo Church in the 1930s, called lambda calculus. Many other functional languages has been developed since then. Nowadays, most programming languages supports this idiom, very few enforce it though; Languages that support multiple styles of programming are called multi-paradigm languages. In this tutorial we shall explore the functional paradigm using Javascript.

In order to understand how the functional paradigm differs from the imperative one, we need to introduce some of its foundations; let us being with pure functions.

Pure functions

Functional programming relies on the concept of pure functions. A pure function is a function that is referentially transparent(the return values are identical for identical arguments, the function must not rely on any mutable state) and side effect free(no local static variables, non-local variables, reference arguments and no input/output streams.).

Let us take a look at some practical examples. The following Javascript function does not rely on any non-local variable/static variable/IO stream, hence it has no side effect. Furthermore, if we call it an arbitrary number of times with the same exact set of arguments, we get the same exact result, hence it is also referentially transparent:

// 'sum' is side-effect free
const sum = (x, y) => x + y;

// If we call 'sum' an arbitrary number of 
// times, we always get the same result.
// Hence it is referentially transparent
console.log(sum(5, 5)); // 10
console.log(sum(5, 5)); // 10
console.log(sum(5, 5)); // 10

Let us now look at an un-pure function.

let pi = 3.1415926

// Compute area of circle
const AreaOfCircle = (radius) => pi * Math.pow(radius, 2);


// The result of the 'AreaOfCircle' may change according to
// the stat of the `pi` global variable
console.log(AreaOfCircle(5)); // 78.539815
console.log(AreaOfCircle(5)); // 78.539815
pi = 10
console.log(AreaOfCircle(5)); // 250

As you can see the AreaOfCircle function relies on a global, mutable variable. Hence, if we try to invoke the function with the same pair of arguments, the result may change over time. In fact, other functions can alter the state of the pi variable, making the result unpredictable.

To make this function pure, we can either move the pi variable to the signature of the AreaOfCircle function:

// Solution 1:
// Move `pi` variable to the signature of the function:
const AreaOfCircle = (radius, pi) => pi * Math.pow(radius, 2);

console.log(AreaOfCircle(5, 3.1415926)); // 78.539815
console.log(AreaOfCircle(5, 3.1415926)); // 78.539815
console.log(AreaOfCircle(5, 3.1415926)); // 78.539815

or we can treat it as a constant:

// Solution 2:
// Treat 'pi' as a constant
const pi = 3.1415926;

const AreaOfCircle = (radius) => pi * Math.pow(radius, 2);

// Trying to alter the state of the `pi` constant
// results in a runtime error
console.log(AreaOfCircle(5)); // 78.539815
console.log(AreaOfCircle(5)); // 78.539815
console.log(AreaOfCircle(5)); // 78.539815
pi = 10
// ^ Uncaught TypeError: Assignment to constant variable.

In the latter case, we still have a non-local variable, but since its state is immutable, it does not cause any side effect. Hence, free variables do not necessarily make a function unpure.

Function composition

Another cornerstone of functional programming is function composition. Compose two(or more) functions means passing the result of a function as an argument of another. From a mathematical point of view, if we have two functions $f$ and $g$, we can combine them using the following notation: $$ (f \circ g)(x) = f(g(x)) $$

This is read as "$f$ composed $g$". Let us now see a practical example on how to combine multiple functions together.

Let $f$, $g$ and $h$ be three functions defined as follow: $$ f(x) = x ^ 2 \ \ \ g(x) = x * 5 \ \ \ h(x) = x + 1 $$

now suppose that we want to compute the result of $$ (f \circ g \circ h)(x) $$

with $x = 3$. We can combine these functions as follows:

const f = (x) => x * x;
const g = (x) => x * 5;
const h = (x) => x + 1;

const x = 3;
const result = f(g(h(x)));

console.log(result); // 400

Keep in mind that composition evaluates functions from right to left, passing each output to the next function.

First-Class Functions

In a functional programming language, functions should support the following two features:

  1. Taking a function as an argument;
  2. Returning another function to the caller.

A function with these capabilities is called a high-order function. A programming language that treats functions as any other object, is a language that supports first-class functions . In this kind of programming language you can assign a function to a variable or pass it around just like any other value. For instance:

const sayHi = function() {
    return "Hi!";
}

const v = sayHi;
v(); // Hi!

You now may be wondering whether there is a difference between these two terms, the answer is yes! while these two concepts are closely related, they are not the exact same thing:

  • First-class functions: is a concept used to describe whether a programming language treats functions just like any other values. For example both Python and Javascript treat functions as any other values, C and C++ do not;
  • High-order functions: is a concept used to describe those functions that work with other functions(take them as parameters/returning them), this term is primarily used when dealing with functions from a mathematical point of view. Thus, it is not strictly related to programming.

Recursion

In the first part of this guide, we stated that a functional program consists only in a series of function compositions, nothing more. This excludes the existence of iterative structures, such as while loops or for loops. Obviously, in Javascript you can find loops but ideally, if you want to stick to the definition, you should avoid them. The functional alternative to loops is recursion. Let us begin with the definition:

Recursion is a technique of solving computation problems where the final solution depends on smaller solutions to smaller instances of the same problem.

—- Graham; Knuth; Patashnik (1990). Concrete Mathematics

In other words, recursion allows a function to call itself until it reaches a “final” state called base case. Recursion is very powerful, in fact it has been proven that recursive-only programming languages are also Turing complete, so we can achieve the same exact result without using any looping structure. Let see one of the most common problem that can be easily solved using recursion: factorial.

In mathematics, the factorial of $n \in \mathbb{Z}$ is defined as follows: $$ n! = n \cdot (n - 1) \cdot (n - 2) \cdots 2 \cdot 1 = \prod_{i=1}^n i $$

Without using recursion, this problem can be solved using a for loop:

function fact(n) {
    let res = 1;
    for(let i = 1; i <= n; i++)
        res *= i;

    return res;
}

console.log(fact(5)); // 120

Now let us try to get the same result using recursion. The recursive approach forces us to identify the exit condition(or base case) of the algorithm.

The exit condition is required to stop the recursion and to prevent a stack overflow. Spotting the base case is usually a matter of looking at the formal definition of the algorithm we are trying to implement.

The exit condition of the factorial function is $n = 0$, that is $n! = 1$. We now have everything we need to build our recursive algorithm:

function fact(n) {
    if(n === 0) return 1; // Base case

    return n * fact(n - 1);
}

console.log(fact(5)); // 120

λ-Functions

So far we saw three different ways of defining a function in Javascript:

// Method 1
function sum(x, y) {
    return x + y;
}

// Method 2
const sub = function(x, y) {
    return x - y;
}

// Method 3
const half = (x) => x / 2;

The first example uses the default syntax to define a function: it has a name and a signature. To invoke it, you can refer to its name.

But what about the second and the third one? These are anonymous functions, that is a function that it is not bounded to a name. This kind of unnamed functions are usually referred as lambda functions.

In javascript, there are two ways of declaring an anonymous function:

  • Pre ES2015(function expression):
const foo = function(arg) {
    return <expr>;
}
// OR
// for self-invoked functions(IIFE)
(function(arg) {
    <stmt>;
})();
  • Starting ES2015(arrow functions):
const foo = (arg) => <expr>;

An anonymous function is useful in all those circumstances where you have to define a function that will be invoked a single time only.

Let us see a practical example. Let us say we need to find the half of each element of an array of integers, without using anonymous functions, this problem requires the definition of a new named function:

function half(n) {
    return n / 2;
}

let vector = [2, 4, 8, 16, 32, 64];
vector = vector.map(half);

console.log(vector); // [ 1, 2, 4, 8, 16, 32 ]

As you can see, the half function is being invoked only in one occurrence. Using an anonymous function, we can remove the declaration of a new, standalone, named function:

let vector = [2, 4, 8, 16, 32, 64];
vector = vector.map(function(n) {
    return n / 2;
});

console.log(vector); // [ 1, 2, 4, 8, 16, 32 ]

If this looks too verbose for you, then you can shorten it a bit more by using the new “arrow” syntax:

let vector = [2, 4, 8, 16, 32, 64];
vector = vector.map(n => n / 2);

console.log(vector); // [ 1, 2, 4, 8, 16, 32 ]

We will talk more about the map function(along with filter and reduce) by the end of this article.

Closures

Closures are another core concept of functional programming, they are being used to associate variables with a function that operates on it without exposing global variables. They provide a way to implement information hiding without declaring a class and the private attributes. Before formally define what a closure is, we need to understand two other concepts.

Nested functions

A nested function is a function defined inside another function. For example:

function foo() {
    function bar() {
    }
}

We will refer to the outer function foo as the enclosing function.

Free variables vs Bound variables

Take a look at the following snippet of code:

function foo(x) {
    return x + y;
}

as you can see there are two occurrences of the variables x. The first one(in the signature of the function) is the declaration of the parameter, while the second one(in the function body) is the real usage of the variable.

Each variable declaration defines a scope for that variable, i.e. the section of the program where the variable can be accessed. In the previous example, the scope of the variable x is the body of the function foo.

When the usage of a variable appears within the scope of a variable declaration, we say that the former is bounded to the latter, and that the latter is a binding occurrence of the variable. In the previous example, the x in the signature of the function is the binding occurrence of this variable while the x in the function body is bounded to the binding occurrence.

On the other hand, y does not have any binding occurrence(i.e., declaration of y), thus it is a free variable.

To put it simple, a free variable is a variable that is neither local nor a parameter of a function. A bound variable is a variable defined in the parameter list of the function or defined as a local variable.

Let us go back to closures.

A closure is a function that encapsulates(or encloses) its outer lexical environment. In other words, it is a nested function that is bundled together with the free variables from the enclosing function that has ended its execution.

Take a look at the following function:

// Define the enclosing function
function outer() {
    const name = "John";

    // define the inner function
    // it has access to the free variables
    // of the enclosing function(in this case 'name')
    function inner() {
        console.log(name);
    }

    // Return the inner function
    return inner;
}

const f = outer();
f(); // John

In this example we are declaring two nested functions in which the inner one still has access to the free variables(the name variable) even after the outer function has terminated. Hence, closures allowed us to declare the name variable without exposing it to the global level.

Emulating private attributes with closures

Let us now look at a more practical example, say want to create an object called Person that defines the first name, the last name and the age of a human being without messing around with global variables.

One solution to do so might be to define a new class with three private attributes and three getters/setters. This is the approach we would follow in a language such as Java, C# and C++.

In Javascript, we can implement private attributes with a simple factory function(i.e. a function that returns an object). The factory function will return three setters and three getters that will access the free variables of the enclosing function. The only way to read/write the attributes is to pass through the closures(the getters/setters.). Let us take a look at the code:

const Person = (name, surname, age) => {
    let _name = name;
    let _surname = surname;
    let _age = age;

    return {
        // Getters
        getName() { return _name; },
        getSurname() { return _surname; },
        getAge() { return _age; },
        // Setters
        setName(name) {_name = name;},
        setSurname(surname) {_surname = surname;},
        setAge(age) {_age = age;}
    };
};

// Create two new objects
const turing = Person("Alan", "Turing", 30);
const church = Person("Alonzo", "Church", 40);

// Try to access attributes through closure
console.log(turing.getName() + ' ' + turing.getSurname() + ": " + turing.getAge());
church.setAge(42);
console.log(church.getName() + ' ' + church.getSurname() + ": " + church.getAge());

// Try to access attributes by bypassing closure
console.log(turing._name); // undefined

As you can see, to create new objects we can invoke the factory function:

const turing = Person("Alan", "Turing", 30);
const church = Person("Alonzo", "Church", 40);

each object has access to an independent closure, so data hiding is guaranteed. Furthermore, if we try to access object’s attributes by bypassing closure’s getters/setters, we get an error:

console.log(turing._name); // undefined

Understanding map, filter and reduce functions

Another cornerstone of functional programming, beside applying and composing functions, is the extensive usage of arrays and arrays operations. The three main array functional methods are:

  • Map: returns a new array with the same number of transformed items;
  • Filter: returns a new array with same number or fewer of the same items;
  • Reduce: returns a single value.

These functions operate on arrays and either transform, filter or reduce them according to a certain rule. They do not alter the original array.

Map

The map function applies a certain function to every element of the array, the resulting array has the same size of the original array. The only difference is that each element has been transformed according to a user-defined function. The syntax for this function is:

const arr = [2, 5, 9];
let new_arr = arr.map(function callback(element, index, array) {
    // return value
}[, thisArg]);

only the element parameter is required, you can ignore the other two for now.

Let us take a look at an example. Let us say that we want to increment each element of an array by one. Using the functional map function, we can achieve this result with just one line of code:

const arr = [2, 5, 9];
let new_arr = arr.map(x => x + 1);

console.log(new_arr); // [ 3, 6, 10 ]

As you can see our anonymous function defines only the element parameter(x), leaving the other two to default.

Filter

The filter function applies a certain conditional statements to each element of the original array. If the condition is true, the element gets pushed to the resulting array, otherwise the element is filtered out. The size of the resulting array can be less or equal of the size of the original array. The syntax is:

const arr = [2, 5, 9];
let new_arr = arr.filter(function callback(element, index, array) {
    // boolean value
}[, thisArg]);

Let see an example. Say that we want to filter out all these items that are odd. The resulting array will contain only those items that are even.

const arr = [2, 5, 9];
let new_arr = arr.filter(x => x % 2 === 0);

console.log(new_arr); // [ 2 ]

In this case the output array’s size is equal to one(i.e. less than the original), however we can also obtain an array with the same size(and content) of the original.

For instance, let us say that we want to filter out all those items less or equal to zero, leaving only items greater than zero. To do so, we can write:

const arr = [2, 5, 9];
let new_arr = arr.filter(x => x > 0 === 0);

console.log(new_arr); // [ 2, 5, 9 ]

We can also apply these functions to objects and array of objects:

const Office = [
    { "name": "Michael", age: 42 },
    { "name": "Jim", age: 32 },
    { "name": "Pam", age: 30 },
    { "name": "Dwight", age: 37 },
    { "name": "Ryan", age: 35 },
];

let res = Office.filter(employee => employee.age >= 35);
console.log(res);
// [
//   { name: 'Michael', age: 42 },
//   { name: 'Dwight', age: 37 },
//   { name: 'Ryan', age: 35 }
// ]

Reduce

The reduce function takes each element of the input array and reduce them to a single value according to a reducing function. The syntax for this function is:

const arr = [2, 5, 9];
let new_arr = arr.reduce(callback[, initialValue]);

This function takes up to four arguments but only two are required:

  1. accumulator: the “total” value of the iteration;
  2. currentValue: the current value of the array;
  3. index: the index of the current value;
  4. array: the original array.

Let us see an example. Suppose that we want to sum all the elements of an array, without reduce we would use a for loop and a sum variable:

const arr = [2, 5, 9];

let sum = 0;

for(let i = 0; i < arr.length; i++)
    sum += arr[i];

console.log(sum); // 16

The reduce function helps us to reduce the verbosity of the previous code:

const arr = [2, 5, 9];

let new_arr = arr.reduce((sum, x) => sum + x);

console.log(new_arr); // 16

References