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

howto accomplish a task. Declarative code stateswhatthe 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 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;

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 different form of abstractions such as functions creating new functions, functions modifying other functions or even functions that can control 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 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 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 behaviour 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 output on each invocation. Another example of impure functions are those having any form of side effects like network connections, filesystem operations or user 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 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 number of lines of code, but on the other hand our code better describes what computation should be performed to achieve 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 (s*poiler alert:* it contains final version of declarative implementation, although achieved with a slightly different refactorings).

## Reference list

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

## Further reading

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

The end result here is more complex than needed, because it fails to use mapping and reducing. Consider the following alternative:

//Produces a random number between i and j

const rand = (i,j) => i + Math.floor(Math.random() * j)

//Given a pair of indices i and j, then an array, returns a new array with elements at i and j swapped

const exchangeArrayIndices = (i,j) => array => {

const iElement = array[i];

const jElement = array[j];

const newArray = array.slice();

newArray[i] = jElement;

newArray[j] = iElement;

return newArray;

}

//Given i and j, produces an array of the integers from i to j, counting up if i is less than j and down if i is greater than j

const range = (i,j) => i range(array.length – 1, 0)

.map(i => [i, rand(0,i)])

.reduce((accumulator, current) => exchangeArrayIndices(…current)(accumulator), array)

LikeLiked by 1 person

Thanks for your feedback. I purposely avoided using map or reduce here. I wanted to discuss other FP paradigms. In my next post I’m going to add recursion and composition to the existing code. I think your proposal perfectly fits part 3 – map, filter and reduce in action 🙂

LikeLike