# Functional design: combinators

###
Giulio Canti
Feb 19
*Updated on Apr 09, 2019 *
・3 min read

In this article the term "combinator" refers to the combinator pattern

A style of organizing libraries centered around the idea of combining things. Usually there is some type

`T`

, some "primitive" values of type`T`

, and some "combinators" which can combine values of type`T`

in various ways to build up more complex values of type`T`

So the general shape of a combinator is

```
combinator: Thing -> Thing
```

The goal of a combinator is to create new "things" from previously defined "things".

Since the result can be passed back as input, you get a combinatorial explosion of possibilities, which makes this pattern very powerful.

If you mix and match several combinators together, you get an even larger combinatorial explosion.

So a design that you may often find in a functional module is

- a small set of very simple "primitives"
- a set of "combinators" for combining them into more complicated structures

Let's see some examples.

##
Example 1: `Setoid`

The `getArraySetoid`

combinator: given an instance of `Setoid`

for `A`

, we can derive an instance of `Setoid`

for `Array<A>`

```
import { Setoid } from 'fp-ts/lib/Setoid'
export function getArraySetoid<A>(S: Setoid<A>): Setoid<Array<A>> {
return {
equals: (xs, ys) => xs.length === ys.length && xs.every((x, i) => S.equals(x, ys[i]))
}
}
```

Usage

```
/** a primitive `Setoid` instance for `number` */
export const setoidNumber: Setoid<number> = {
equals: (x, y) => x === y
}
// derived
export const setoidArrayOfNumber: Setoid<Array<number>> = getArraySetoid(setoidNumber)
// derived
export const setoidArrayOfArrayOfNumber: Setoid<Array<Array<number>>> = getArraySetoid(setoidArrayOfNumber)
// derived
export const setoidArrayOfArrayOfArrayOfNumber: Setoid<Array<Array<Array<number>>>> = getArraySetoid(setoidArrayOfArrayOfNumber)
// etc...
```

Another combinator, `contramap`

: given an instance of `Setoid`

for `A`

and a function from `B`

to `A`

, we can derive an instance of `Setoid`

for `B`

```
export const contramap = <A, B>(f: (b: B) => A, S: Setoid<A>): Setoid<B> => {
return {
equals: (x, y) => S.equals(f(x), f(y))
}
}
```

Usage

```
export interface User {
id: number,
name: string
}
export const setoidUser: Setoid<User> = contramap((user: User) => user.id, setoidNumber)
// mix with `getArraySetoid`
export const setoidArrayOfUser: Setoid<Array<User>> = getArraySetoid(setoidUser)
```

##
Example 2: `Monoid`

The `getIOMonoid`

combinator: given an instance of `Monoid`

for `A`

, we can derive an instance of `Monoid`

for `IO<A>`

```
import { IO } from 'fp-ts/lib/IO'
import { Monoid } from 'fp-ts/lib/Monoid'
export function getIOMonoid<A>(M: Monoid<A>): Monoid<IO<A>> {
return {
concat: (x, y) => new IO(() => M.concat(x.run(), y.run())),
empty: new IO(() => M.empty)
}
}
```

We can use `getIOMonoid`

to derive another combinator, `replicateIO`

: given a number `n`

and an action `mv`

of type `IO<void>`

, we can derive an action that performs `n`

times `mv`

```
import { fold } from 'fp-ts/lib/Monoid'
import { replicate } from 'fp-ts/lib/Array'
/** a primitive `Monoid` instance for `void` */
export const monoidVoid: Monoid<void> = {
concat: () => undefined,
empty: undefined
}
export function replicateIO(n: number, mv: IO<void>): IO<void> {
return fold(getIOMonoid(monoidVoid))(replicate(n, mv))
}
```

Usage

```
//
// helpers
//
/** logs to the console */
export function log(message: unknown): IO<void> {
return new IO(() => console.log(message))
}
/** returns a random integer between `low` and `high` */
export const randomInt = (low: number, high: number): IO<number> => {
return new IO(() => Math.floor((high - low + 1) * Math.random() + low))
}
//
// program
//
function fib(n: number): number {
return n <= 1 ? 1 : fib(n - 1) + fib(n - 2)
}
/** calculates a random fibonacci and prints the result to the console */
const printFib: IO<void> = randomInt(30, 35).chain(n => log(fib(n)))
replicateIO(3, printFib).run()
/*
1346269
9227465
3524578
*/
```

##
Example 3: `IO`

We can build many other combinators for `IO`

, for example the `time`

combinator mimics the analogous Unix command: given an action `IO<A>`

, we can derive an action `IO<A>`

that prints to the console the elapsed time

```
import { IO } from 'fp-ts/lib/IO'
/** returns the current time in millis */
export const now = new IO(() => new Date().getTime())
export function time<A>(ma: IO<A>): IO<A> {
return now.chain(start =>
ma.chain(a => now.chain(end => log(`Elapsed: ${end - start}`).map(() => a)))
)
}
```

Usage

```
time(replicateIO(3, printFib)).run()
/*
5702887
1346269
14930352
Elapsed: 193
*/
```

With partials...

```
time(replicateIO(3, time(printFib))).run()
/*
3524578
Elapsed: 32
14930352
Elapsed: 125
3524578
Elapsed: 32
Elapsed: 189
*/
```

Can we make the `time`

combinator more general? We'll see how in the next article.

I recently wrote about the combinator pattern in my article on property testing via JSVerify. I blinked just now at reading the phrase "combinatorial explosion" which we both used in our articles – but it turns out you wrote it first (Feb. vs Mar.)! Um, great minds think alike?

Anyway, combinators to me represent almost the entire point of FP – composition. The ability to connect pieces of code together seamlessly, building up complexity without getting lost in the wiring. This article has some nice examples.

I recently became aware of FP-TS from a tweet; it looks good! Might be the lever that finally pushes me into adopting TS itself, as FP in JS works but I miss the typing of e.g. Haskell. Enjoying your article series, thanks for posting it.

This seems to be a nice post, but typescript makes it so hard to read...