Functional design: combinators
Giulio Canti
Posted on February 19, 2019
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 typeT, and some "combinators" which can combine values of typeTin various ways to build up more complex values of typeT
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: Eq
The getEq combinator: given an instance of Eq for A, we can derive an instance of Eq for ReadonlyArray<A>
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
/** 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
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
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>
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
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
//
// 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
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
time(replicateIO(3, printFib))()
/*
5702887
1346269
14930352
Elapsed: 193
*/
With partials...
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.
Posted on February 19, 2019
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.
Related
November 29, 2024
