Functional design: combinators
Tags: functional, typescript
Published: 2019-02-19 09:14:37

---
title: Functional design: combinators
published: true
description:
tags: functional, typescript
series: Functional design
---

In this article the term "combinator" refers to the [combinator pattern](https://wiki.haskell.org/Combinator)

> 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

```ts
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: `Eq`

The `getEq` combinator: given an instance of `Eq` for `A`, we can derive an instance of `Eq` for `ReadonlyArray<A>`

```ts
import { Eq, fromEquals } from 'fp-ts/Eq'

export function getEq<A>(E: Eq<A>): Eq<ReadonlyArray<A>> {
  return fromEquals(
    (xs, ys) =>
      xs.length === ys.length && xs.every((x, i) => E.equals(x, ys[i]))
  )
}
```

Usage

```ts
/** a primitive `Eq` instance for `number` */
export const eqNumber: Eq<number> = {
  equals: (x, y) => x === y
}

// derived
export const eqNumbers: Eq<ReadonlyArray<number>> = getEq(eqNumber)

// derived
export const eqNumbersNumbers: Eq<ReadonlyArray<ReadonlyArray<number>>> = getEq(
  eqNumbers
)

// derived
export const eqNumbersNumbersNumbers: Eq<ReadonlyArray<
  ReadonlyArray<ReadonlyArray<number>>
>> = getEq(eqNumbersNumbers)

// etc...
```

Another combinator, `contramap`: given an instance of `Eq` for `A` and a function from `B` to `A`, we can derive an instance of `Eq` for `B`

```ts
import { Eq, fromEquals } from 'fp-ts/Eq'

export const contramap = <A, B>(f: (b: B) => A) => (E: Eq<A>): Eq<B> =>
  fromEquals((x, y) => E.equals(f(x), f(y)))
```

Usage

```ts
import { contramap, Eq } from 'fp-ts/Eq'
import { pipe } from 'fp-ts/function'
import * as N from 'fp-ts/number'
import * as RA from 'fp-ts/ReadonlyArray'

export interface User {
  id: number
  name: string
}

export const eqUser: Eq<User> = pipe(
  N.Eq,
  contramap((user: User) => user.id)
)

export const eqUsers: Eq<Array<User>> = RA.getEq(eqUser)
```

## Example 2: `Monoid`

The `getMonoid` combinator: given an instance of `Monoid` for `A`, we can derive an instance of `Monoid` for `IO<A>`

```ts
import { IO } from 'fp-ts/IO'
import { Monoid } from 'fp-ts/Monoid'

export function getMonoid<A>(M: Monoid<A>): Monoid<IO<A>> {
  return {
    concat: (x, y) => () => M.concat(x(), y()),
    empty: () => M.empty
  }
}
```

We can use `getMonoid` 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`

```ts
import { concatAll } from 'fp-ts/Monoid'
import { replicate } from 'fp-ts/ReadonlyArray'

/** 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 concatAll(getMonoid(monoidVoid))(replicate(n, mv))
}
```

Usage

```ts
//
// helpers
//

/** logs to the console */
export function log(message: unknown): IO<void> {
  return () => console.log(message)
}

/** returns a random integer between `low` and `high` */
export const randomInt = (low: number, high: number): IO<number> => {
  return () => Math.floor((high - low + 1) * Math.random() + low)
}

//
// program
//
import { chain } from 'fp-ts/IO'
import { pipe } from 'fp-ts/function'

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> = pipe(
  randomInt(30, 35),
  chain((n) => log(fib(n)))
)

replicateIO(3, printFib)()
/*
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

```ts
import { IO, Monad } from 'fp-ts/IO'
import { now } from 'fp-ts/Date'
import { log } from 'fp-ts/Console'

export function time<A>(ma: IO<A>): IO<A> {
  return Monad.chain(now, (start) =>
    Monad.chain(ma, (a) =>
      Monad.chain(now, (end) =>
        Monad.map(log(`Elapsed: ${end - start}`), () => a)
      )
    )
  )
}
```

Usage

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

With partials...

```ts
time(replicateIO(3, time(printFib)))()
/*
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](https://dev.to/gcanti/functional-design-how-to-make-the-time-combinator-more-general-3fge).