# Compose For Speed

A common functional pattern, for lack of a better word, is to compose various functions together. This is often seen as an elegant way of combining multiple operations on a single data structure. But another advantage of composition is that it allows us to write faster, more efficient code.

We’ll look briefly what composition is, some properties of map, and then consider some (contrived) examples in JavaScript along with their performances.

#### Composition: What it is

Very simply, composition is an operation that takes a function from a to b, and a function from b to c, and returns a function from a to c.

The arrows are functions, f and g, and the circles are types. Here composition allows us to construct a new arrow starting at the first circle, a, ending at the last circle, c. What’s interesting here is that we don’t care about the arrows, nor do we care about the circles — so long as the end of one arrow matches with the beginning of another, we can compose the arrows.

#### Chaining maps in JavaScript

For the sake of argument, suppose we have an array with 100,000 numbers in it, called nums. And suppose we are interested in performing some elementary operations over each element in the array.

`const double = num => num * 2;const triple = num => num * 3;const quad = num => num * 4;const exp = num => num * num;`

One way we might apply these functions to each element of the array would be to chain a series of maps together,

`nums .map(double) .map(triple) .map(quad) .map(exp);`

This maps double over nums, creating a new array, to which we map triple over, creating a new array, to which we map quad over… and so on. What’s important to notice here is that we are performing four mapping operations, which means we are building up three intermediate representations before returning our fourth array.

#### An Important Property of map

Now, this is not ideal since the total number of maps, or passes over the array, is determined by the number of operations we want to perform, or O(n). A better solution would be one in which the number of passes over the array is just 1, or O(1). This can be achieved with function composition.

To see how we can achieve this with composition, consider the follow property of map:

`map f . map g = map (f . g)`

The dot (.) here is the composition operator, and f and g are functions. In English, this says,

`if you map f after mapping g, then that is the same as mapping a function which applies f after g.`

In other words, a composition of maps is equal to a map of compositions. Therefore, map is distributive over function composition. This is easy to verify (and a more rigorous proof of this can be found in Graham Hutton’s Fold paper).

`Ex 1. (map (+10) . map (*2)) [1, 2, 3][12, 14, 16]`
`Ex 2. map ((+10) . (*2)) [1, 2, 3][12, 14, 16]`
`(map (+10) . map (*2)) [1, 2, 3] == map ((+10) . (*2)) [1, 2, 3]True`

Or the equivalent code in JavaScript, assuming we have a compose function,

`Ex 1. [1, 2, 3].map(n => n * 2).map(n => n + 10)[12, 14, 16]`
`Ex 2. [1, 2, 3].map(compose(n => n + 10, n => n * 2))[12, 14, 16]`

Despite returning the same values, the difference between Ex 1 and Ex 2 is the evaluation: the first example involves two passes (maps) over the array (once for the function (*2) and once for the function (+10)) — causing an intermediate representation to be created — whereas the second involves only one pass over the array —creating no intermediate representation.

#### Performance in JavaScript: Some Examples

So it follows that if we are able to compose our functions, we then can get away with performing only one map, which should be faster than multiple maps. In fact, this is something that the Haskell GHC compiler does as an optimisation, known as fusion. Of course, we do not have that luxury in JavaScript, therefore we will have to handcode the optimisation ourselves.

What happens in JavaScript in practice? In the following examples, we will use the compose function from the underscore library, along with the console.time and console.timeEnd functions to record time taken. We will compare what happens when you map a composed function with a series of chained maps.

In a file add the following (you’ll need to have installed underscore),

`const compose = require(‘underscore’).compose;`
`let nums = [];`
`for (let i = 0; i < 100000; i++) nums.push(i);`
`const double = num => num * 2;const triple = num => num * 3;const quad = num => num * 4;const exp = num => num * num;`
`const composedFunction = compose(double, triple, quad, exp);`
`console.time("composed function");nums.map(composedFunction);console.timeEnd("composed function");`
`console.time("uncomposed function");nums .map(double) .map(triple) .map(quad) .map(exp);console.timeEnd("uncomposed function");`

The output of this (with a 2.9GHz i7 processor, using node 8), averaged over 10 runs[1]:

`\$ node numberstest.jscomposed function: 37.54msuncomposed function: 103.93ms`

That is, the version involving function composition is almost 3 times faster in this specific case. What about if we start mapping over arrays of objects? In another file add,

`const compose = require(‘underscore’).compose;`
`const doubleO = obj => ({ key: obj.key * 2 });const tripleO = obj => ({ key: obj.key * 3 });const quadO = obj => ({ key: obj.key * 4 });const expO = obj => ({ key: obj.key * obj.key });`
`let os = [];`
`for (let i = 0; i < 100000; i++)    os.push({key: i})`
`const composedFunctionO = compose(doubleO, tripleO, quadO, expO);`
`console.time('composed function over objects');os.map(composedFunctionO);console.timeEnd('composed function over objects');`
`console.time('uncomposed function over objects');os .map(doubleO) .map(tripleO) .map(quadO) .map(expO);console.timeEnd('uncomposed function over objects');`

The output of this, averaged over 10 runs[2]:

`\$ node objecttest.jscomposed function over objects: 83.47msuncomposed function over objects: 176.50ms`

Again, composition wins by quite the mile. As a final example, consider the identity function,

`const id = x => x;`

This is probably one of the simplest functions writable — take an input and give it straight back without modification. Let’s look at what happens when we apply id to our array 10 times, just to be absurd.

`const compose = require('underscore').compose;`
`const id = obj => obj;`
`let os = [];`
`for (let i = 0; i < 100000; i++)    os.push({key: i})`
`const composedFunction = compose(id, id, id, id, id, id, id, id, id, id);`
`console.time('composed function of id');const r = os.map(composedFunction);console.timeEnd('composed function of id');`
`console.time('uncomposed function of id');os .map(id) .map(id) .map(id) .map(id) .map(id) .map(id) .map(id) .map(id) .map(id) .map(id);console.timeEnd('uncomposed function of id');`

The output of this, averaged over 10 runs[3]:

`\$ node idtest.jscomposed function of id: 40.57msuncomposed function of id: 261.12ms`

Again, composition is vastly faster, here around 6 times faster.

Now for the caveats. These examples are simple and really don’t reflect what programmers do in their day to day work. Moreover, the data structures we have used are relatively large and simple. However, the simplicity in the code will hopefully help to demonstrate the point — composition does not create intermediate representations, allowing a single map to be used, meaning faster code.

In itself that is an interesting result, but what makes this all the more significant is the fact that we arrived at this result purely by considering the abstract properties of our code. Namely, that map is distributive over function composition — i.e. map f . map g = map (f . g). We did not start with the code examples; instead, the code examples came out of these known mathematical properties.

#### Appendix

[1] Raw results for mapping over array of numbers:

`composed function: 36.411msuncomposed function: 101.838mscomposed function: 40.195msuncomposed function: 105.363mscomposed function: 39.725msuncomposed function: 109.773mscomposed function: 34.599msuncomposed function: 102.457mscomposed function: 38.232msuncomposed function: 107.059mscomposed function: 39.724msuncomposed function: 99.361mscomposed function: 36.200msuncomposed function: 103.650mscomposed function: 34.055msuncomposed function: 102.804mscomposed function: 35.248msuncomposed function: 100.624mscomposed function: 41.013msuncomposed function: 106.361ms`

[2] Raw results for mapping over array of simple objects:

`composed function over objects: 81.930msuncomposed function over objects: 183.875mscomposed function over objects: 82.504msuncomposed function over objects: 181.905mscomposed function over objects: 83.793msuncomposed function over objects: 182.160mscomposed function over objects: 84.268msuncomposed function over objects: 163.915mscomposed function over objects: 83.933msuncomposed function over objects: 179.896mscomposed function over objects: 83.308msuncomposed function over objects: 182.458mscomposed function over objects: 82.534msuncomposed function over objects: 181.936mscomposed function over objects: 82.354msuncomposed function over objects: 180.052mscomposed function over objects: 84.272msuncomposed function over objects: 165.253mscomposed function over objects: 85.831msuncomposed function over objects: 163.557ms`

[3] Raw results for mapping id over array of simple objects:

`composed function of id: 44.540msuncomposed function of id: 278.322mscomposed function of id: 40.849msuncomposed function of id: 280.103mscomposed function of id: 39.567msuncomposed function of id: 250.024mscomposed function of id: 40.501msuncomposed function of id: 258.685mscomposed function of id: 39.398msuncomposed function of id: 254.510mscomposed function of id: 40.280msuncomposed function of id: 266.085mscomposed function of id: 39.970msuncomposed function of id: 255.288mscomposed function of id: 40.891msuncomposed function of id: 252.170mscomposed function of id: 39.483msuncomposed function of id: 262.167mscomposed function of id: 40.250msuncomposed function of id: 253.815ms`
Like what you read? Give chris__bacon a round of applause.

From a quick cheer to a standing ovation, clap to show how much you enjoyed this story.