A journey to functional JavaScript: Part 1 – fundamentals

JavaScript has a quite fascinating history. Brendan Eich created on his own the first language prototype in just ten days. Its implementation was highly influenced by the concepts of first-class functions from Scheme and prototypes from Self. Initially, it was developed under the name Mocha, but released as LiveScript. The latter name didn’t last long either. Java was so hot back in 1995, that Netscape decided to take marketing move and rename their new language to JavaScript. This decision has greatly influenced the way JavaScript has been perceived for many years. Outward similarities to Java promoted imperative, object-oriented style among developers using it. Ideas borrowed from Scheme have always enabled using functional programming styles as well. However, it was never the case until it started to get momentum a few month ago.

Array shuffle algorithm

A few weeks ago I was working on one of my side projects. At some point, I had to randomize the order of items in an array. To my surprise, it turned out there is no existing method baked into JavaScript language ready to use right away. I made a quick research and I figured out that the best approach would be to use the modern version of the Fisher–Yates algorithm:

-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

Imperative vs declarative

Imperative code is primarily concerned with explicitly stating how to accomplish a task. Declarative code states what the outcome should be, and leaves the implementation to some other responsibility.

Kyle Simpson [2]

When you search npm repository for the phrase array shuffle you will discover that all top matches are implemented in JavaScript with the imperative style similar to:

function arrayShuffle( input ) {
	const scratch = [ ...input ];
	let range = scratch.length;
	let result = [];

	while ( range ) {
		const roll = Math.floor(
			Math.random() * range
		);
		const pick = scratch[ roll ];
		range -= 1;
		scratch[ roll ] = scratch[ range ];
		result = [ pick, ...result ];
	}

	return result;
}

I asked myself, how would this code look like if it was written using declarative style. In this post, I’m going to explain how the function presented above can be transformed to functional programming world step by step. All refactorings are accompanied with the corresponding FP paradigms.

Functional programming

Functional programming is the use of functions that transform values into units of abstraction, subsequently used to build software systems.

Michael Fogus [3]

Functional programming is not a new concept. The idea of building software around functions has been around for decades. Aforementioned Scheme language is a dialect of another programming language Lisp, which was originally specified in 1958.

const scratch = [ ...input ];
let range = scratch.length;
let result = [];

I started with something really simple and extracted a general-purpose function out of scratch.length expression which returns the number of items in the array.

const length = list => list.length;

The newly introduced function uses an arrow function expression and doesn’t change the code too much.

const scratch = [ ...input ];
let range = length( scratch );
let result = [];

First-class functions

A functional programming language is one facilitating the use and creation of first-class functions.

Michael Fogus [3]

Functions can be used in JavaScript the same way as you use variables. They can be assigned to variables or passed around as param just like any other type.

const roll = Math.floor(
	Math.random() * range
);
const pick = scratch[ roll ];
range -= 1;
scratch[ roll ] = scratch[ range ];
result = [ pick, ...result ];

I noticed that there are 2 lines of code where a similar operation is performed. I introduced new function which returns the nth element of the given list.

const nth = n =>
	list => list[ n ];

I not only assigned function to nth variable, but I also constructed this expression in a way where it returns another function. That’s why it needs to be called twice to return the final result.

const roll = Math.floor(
	Math.random() * range
);
const pick = nth( roll )( scratch );
range -= 1;
scratch[ roll ] = nth( range )( scratch );
result = [ pick, ...result ];

Higher-order functions

A function that receives or returns one or more other function values has the special name: higher-order function.

Kyle Simpson [2]

The term comes from mathematics. Higher-order functions allow us to create a different form of abstractions such as functions creating new functions, functions modifying other functions or even functions that can control the flow of the program.

I already used a higher-order function above. nth creates another function.

scratch[ roll ] = nth( range )( scratch );
result = [ pick, ...result ];

Next, I turned my attention to the line where result gets updated. I wrote prepend function to put it in place of [ pick, ...result ] expression. It returns a new list with the given element prepended to another list.

const prepend = el =>
	list => [].concat( el, list );

This is another higher-order function, which behaves in a similar way to what I presented before.

scratch[ roll ] = nth( range )( scratch );
result = prepend( pick )( result );

Closures

Closure is when a function remembers and accesses variables from outside of its own scope, even when that function is executed in a different scope.

Kyle Simpson [2]

Closures make it possible for the inner function to reference to a variable from the outer function. This access is persisted, even after the parent function has closed.

I implemented aforementioned nth and prepend functions in a way where they use closure to remember variables. It might not be obviously visible from the code presented before. That’s why I want to show more examples which should better explain how it works.

const first = nth( 0 );
const second = nth( 1 );

first( [ 'a', 'b', 'c' ] ); // returns 'a'
first( [ 1, 2, 3 ] ); // returns 1
second( [ 'a', 'b', 'c' ] ); // returns 'b'
second( [ 1, 2, 3 ] ); // returns 2

Currying

A curried function is one that returns a new function for every logical argument that it takes.

Michael Fogus [3]

Currying is a method where a function with multiple arguments is transformed into a chain of one-argument functions. It combines two aforementioned techniques: higher-order functions and closures.

I would like to relate nth and prepend utilities again. They represent also multi-argument functions which are expressed in a curried form.

range -= 1;
scratch[ roll ] = nth( range )( scratch );
result = prepend( pick )( result );

The next line of code that caught my eye was one where randomly picked element gets replaced with the last element in the range. I declared a curried function update which returns a new copy of the list with the item at the provided index replaced with the given value.

const update = idx =>
	x =>
		list => {
			const result = [ ...list ];

			result[ idx ] = x;

			return result;
		};

I partially applied function’s arguments twice to increase readability of this code. First, I declared updatePick method which remembers the index where update operation is going to be performed. Next, I introduced updatePickWithLast which stores the last value in the current range of the scratch array. Finally, I updated the line to replace scratch variable with the result of updatePickWithLast call with scratch as its last param passed.

range -= 1;
const updatePick = update( roll );
const updatePickWithLast = updatePick(
	nth( range )( scratch )
);
scratch = updatePickWithLast( scratch );
result = prepend( pick )( result );

Purity

A pure function is a function that, given the same input, will always return the same output and does not have any observable side effect.

Brian Lonsdorf [1]

Purity is also known as referential transparency and it means that a function call can be replaced with its corresponding return value without changing the behavior of the program. A pure function also doesn’t depend on or modify variables outside of its scope.

All functions introduced so far: length, nth, prepend and update are pure. In case of update method I had to use special strategy to avoid the side causes. I copied first a direct input list to protect its value against mutation via reference.

scratch = updatePickWithLast( scratch );
result = prepend( pick )( result );

I didn’t like the fact that we keep the size of scratch array on all while loop iteration when each time the last element becomes utterly unnecessary. It definitely makes it harder to understand how array shuffle algorithm works. I decided to write init utility which returns all but the last element of the given list.

const init = list => list.slice( 0, length( list ) - 1 );

This function is also pure. I used Array’s slice which does not change the array which invokes it. I purposely avoided using splice which is a similar method, but it mutates the array that calls it. I added init call after the line where a randomly picked item got replaced with the last element. I hope it made it clear that on every iteration the number of processed items shrinks.

scratch = updatePickWithLast( scratch );
scratch = init( scratch );
result = prepend( pick )( result );

Impure

You may never have considered it before, but randomness is impure. A function that uses Math.random() can never be pure, because you cannot ensure/predict its output based on its input.

Kyle Simpson [2]

JavaScript methods like Math.random() or Date.now() are impure by design. Behind the scenes, they use global variables to decide if they should change the output on each invocation. Another example of impure functions are those having any form of side effects like network connections, filesystem operations or user’s mouse and keyboard events.

while ( range ) {
	const roll = Math.floor(
		Math.random() * range
	);
	const pick = nth( roll )( scratch );

I identified the chunk of code which contains Math.random() and therefore it can’t be refactored to be pure. I extracted function to separate the impure part from the rest of code. I decided to make this utility work with a list instead of range to align its signature with other functions.

const pickRandIndex = list => Math.floor(
	Math.random() * length( list )
);

It was possible thanks to the previously introduced change that added step where init call keeps range variable and the length of scratch list in sync.

while ( range ) {
	const roll = pickRandIndex( scratch );
	const pick = nth( roll )( scratch );

Immutability

In functional programming, the ideal situation is that there is never mutation, and if you start with a policy of immutability, you’d be surprised how far you can get.

Michael Fogus [3]

An immutable value can never be modified after it has been created. In JavaScript, numbers and strings are immutable by design, but it doesn’t apply to object or arrays. In the latter case, immutability can be enforced by making sure that a new copy is always created whenever a change is required. I have already presented an example of this technique when update or init functions were introduced.

function arrayShuffle( input ) {
	let scratch = [ ...input ];
	let range = length( scratch );
	let result = [];

	while ( range ) {
		const roll = pickRandIndex( scratch );
		const pick = nth( roll )( scratch );
		range -= 1;
		const updatePick = update( roll );
		const updatePickWithLast = updatePick(
			nth( range )( scratch )
		);
		scratch = updatePickWithLast( scratch );
		scratch = init( scratch );
		result = prepend( pick )( result );
	}

	return result;
}

As I shared above that general tactic is getting rid of mutable variables. There are three of them here. It started with range variable which can be inlined after I introduced init transformation. It turned out that I can move computation which decrements range value to the new function called last.

const last = list => nth( length( list ) - 1 )( list );

It was safe to eradicate range variable completely once its decrementation got replaced with last call.

function arrayShuffle( input ) {
	let scratch = [ ...input ];
	let result = [];

	while ( length( scratch ) ) {
		const roll = pickRandIndex( scratch );
		const pick = nth( roll )( scratch );
		const updatePick = update( roll );
		const updatePickWithLast = updatePick(
			last( scratch )
		);
		scratch = updatePickWithLast( scratch );
		scratch = init( scratch );
		result = prepend( pick )( result );
	}

	return result;
}

Summary

I reached the point where I covered most of the fundamentals of functional programming. It seems like a good moment to wrap up this post. So far, I have introduced a bunch of small and simple functions to learn all paradigms. On the one hand it admittedly increased the number of lines of code, but on the other hand, our code better describes what computation should be performed to achieve the desired result.

In Part 2 of the series, I’m going to continue this refactoring journey. I want to take a deeper dive and discuss more advanced topics like recursion and function composition. Finally, I plan to glue everything together using point-free style. In the meantime, you can check my GitHub repository where I documented all my explorations with atomic commits (spoiler alert: it contains final version of declarative implementation, although achieved with slightly different refactorings).

Reference list

1. Mostly adequate guide to Functional Programming – book by Brian Lonsdorf.
2. Functional-Light JavaScript – book by Kyle Simpson.
3. Functional JavaScript: Introducing Functional Programming with Underscore.js – book by Michael Fogus.

Further reading

1. A Brief History of JavaScript – article by Sebastián Peyrott.
2. Imperative vs Declarative Programming – article by Tyler McGinnis.
3. Why Curry Helps – article by Hugh FD Jackson.
4. Immutability in JavaScript – article by Christian Johansen.
5. Functional Programming Jargon – community maintained glossary with JavaScript examples.