# Function Combinators

Section 2.1 of the book
Software Design for Flexibility
(SDF) by Chris Hanson and Gerald Jay Sussman
introduces function combinators that allow a programmer
to describe basic functional components and *combine*
them in order build a more complex system. The presented combinators compose
functions in various ways,
rearrange their arguments and curry them, and thus they let the
programmer mix-and-match the basic functional components. The SDF authors compare this
approach to biological systems that adapt to their environment by configuring
their basic components (such as cells) in response to environmental changes.

In this blog post, I translate most examples from SDF Section 2.1 into JavaScript.
The translation demonstrates the use of JavaScript’s rest and spread operators for
defining a library of function combinators. Since these operators use arrays
instead of Scheme’s lists, you get to see some JavaScript array processing,
for example various ways to use the `splice`

method for arrays.
To keep things simple, I don’t cover
the arity manipulation mechanisms of SDF Section 2.1. I skip the examples of
the section *Multiple values* because JavaScript does not have a
multiple-value return mechanism.

As usual, you can click on the links to play with the programs.

## Composition of functions

The first combinator
composes two functions. The composition
yields a function `c`

that first applies a given function `g`

to `c`

’s
arguments, and then applies a given function `f`

to the result,
as shown in the following diagram (Figure 2.1 of SDF).

The
JavaScript implementation of `compose`

uses JavaScript’s *rest*
syntax to gather the arguments of the composition into an array
`args`

, and the *spread* syntax to pass each component of the
`args`

array as a separate argument to `g`

.

```
function compose(f, g) {
return (...args) => f(g(...args));
}
```

The following example demonstrates the use of `compose`

.

```
compose(x => ["foo", x],
(x, y, z) => ["bar", x, y, z])("a", "b", "c");
// result: ["foo", ["bar", "a", "b", "c"]]
```

**A digression:** I personally find the asymmetry of this `compose`

function quite unfortunate: `g`

can take multiple arguments, but
`f`

only takes one. SDF mitigates the issue using
Scheme’s multiple-value return mechanism later in Section 2.1.
I find that mechanism
rather cumbersome and much prefer the approach taken by “modern”
functional programming languages such as OCaml and Haskell,
where all functions take exactly one argument. Multiple arguments
are passed either in compound data structures or by currying.
Then the asymmetry
disappears, and the combinators of this blog post all operate
on compound data or curried functions
that combine the intended arguments, rather than
using JavaScript’s rest and spread operators or Scheme’s dot notation.
Of course, that would require a major redesign of JavaScript/Scheme…

Unary functions (functions that take only one argument) can
be repeatedly applied using the following function `iterate`

.

```
function iterate(n) {
return f =>
n === 0
? identity
: compose(f, iterate(n - 1)(f));
}
```

The
function `iterate`

takes a number `n`

as argument and
returns a function that takes a function `f`

as argument.
When applied to a unary function as `f`

, the result is
a function that applies `f`

as often to its argument
as indicated by the number `n`

. If `n`

is 0, the
result is the identity function (which applies `f`

zero times).

```
function identity(x) {
return x;
}
```

Here is the example of SDF.

```
function square(x) {
return x * x;
}
iterate(3)(square)(5);
// result: 390625
```

## Parallel and spread combiners

The next combinator applies two functions `f`

and
`g`

separately to the given arguments, and then combines
the results using another function `h`

, as shown in
the following diagram (Figure 2.2 of SDF).

The implementation is straightforward.

```
function parallel_combine(h, f, g) {
return (...args) =>
h(f(...args), g(...args));
}
```

The following example is also from SDF.

```
parallel_combine((x, y) => [x, y],
(x, y, z) => ["foo", x, y, z],
(u, v, w) => ["bar", u, v, w])
("a", "b", "c");
// result: [["foo", "a", "b", "c"], ["bar", "a", "b", "c"]]
```

The variant `spread_combine`

distributes the
given arguments to `f`

and `g`

, as depicted in the following
diagram (Figure 2.3 of SDF).

The
implementation
uses the `length`

attribute of functions
to access their arity.

```
function spread_combine(h, f, g) {
const f_arity = f.length;
return (...args) =>
h(f(...array_take(args, f_arity)),
g(...array_drop(args, f_arity)));
}
```

The following example is from SDF.

```
spread_combine((x, y) => [x, y],
(x, y) => ["foo", x, y],
(u, v, w) => ["bar", u, v, w])
("a", "b", "c", "d", "e");
// result: [["foo", "a", "b"], ["bar", "c", "d", "e"]]
```

The function `array_take`

returns an array that contains
the first `n`

components of the given array, and the
function `array_drop`

returns an array in which the
first `n`

components of the given array are missing.

```
function array_take(a, n) {
const a_copy = [...a];
a_copy.splice(n, a.length - n);
return a_copy;
}
array_take([1,2,3,4], 2);
// result: [1, 2]
function array_drop(a, n) {
const a_copy = [...a];
a_copy.splice(0, n);
return a_copy;
}
array_drop([1,2,3,4], 1);
// result: [2, 3, 4]
```

Note that both functions take care not to change
the original array `a`

, by applying the destructive
JavaScript array method `splice`

to a copy of the given
array. This non-destructive behavior
is important for `spread_combine`

to work as intended.

## Discarding and currying an argument

The next combinator returns a function that applies
a given function `f`

to all given arguments except the
argument at a given position, as depicted in the following
diagram (Figure 2.5 of SDF).

The
implementation
uses a non-destructive
`array_remove`

function.

```
function discard_argument(i) {
return f => (...args) => f(...array_remove(args, i));
}
```

The following example is from SDF.

```
discard_argument
(2)
((x, y, z) => ["foo", x, y, z])
("a", "b", "c", "d");
// result: ["foo", "a", "b", "d"]
```

The `array_remove`

function is another example for
the versatile `splice`

method supported by JavaScript arrays.

```
function array_remove(a, n) {
const a_copy = [...a];
a_copy.splice(n, 1);
return a_copy;
}
array_remove([1,2,3,4], 1);
// result: [1, 3, 4]
```

The following version of the technique of *currying*
supplies all given arguments except one to the given function
`f`

. The missing argument is then passed separately to
the result function, as depicted in the following diagram
(Figure 2.6 of SDF).

The
implementation
uses a non-destructive `array_insert`

method.

```
function curry_argument(i) {
return (...args) =>
f =>
x =>
f(...array_insert(args, i, x));
}
```

As usual, the following example is taken from SDF:

```
curry_argument
(2)
("a", "b", "c")
((x, y, z, w) => ["foo", x, y, z, w])
("d");
// result: ["foo", "a", "b", "d", "c"]
```

The `array_insert`

function provides yet another
example for the `splice`

method.

```
function array_insert(a, index, value) {
const a_copy = [...a];
a_copy.splice(index, 0, value);
return a_copy;
}
array_insert([1,2,3,4], 2, 44);
// result: [1, 2, 44, 3, 4]
```

The final combinator of this post allows the programmer to rearrange the arguments to be passed to a given function, following a specified permutation, as depicted in the following diagram (Figure 2.7 in SDF).

The
implementation
uses a `make_permutation`

function
that returns the actual `permute`

function, which
performs the argument permutation according to the
given specification.

```
function permute_arguments(...permspec) {
const permute = make_permutation(permspec);
return f =>
(...args) => f(...permute(args));
}
```

As usual, the following example is taken from SDF:

```
permute_arguments
(1, 2, 0, 3)
((x, y, z, w) => ["foo", x, y, z, w])
("a", "b", "c", "d");
// result: ["foo", "b", "c", "a", "d"]
```

The `make_permutation`

function is straightforward.

```
function make_permutation(permspec) {
return a => {
const result = [];
const a_len = permspec.length;
for (let i = 0; i < a_len; i = i + 1) {
result[i] = a[permspec[i]];
}
return result;
};
}
make_permutation
([1,2,0,3])
(["a", "b", "c", "d"]);
// result: ["b", "c", "a", "d"]
```