DEV Community

Giulio Canti
Giulio Canti

Posted on • Edited on

Functional design: combinators

#functional #typescript

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
Enter fullscreen mode Exit fullscreen mode

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]))
  )
}
Enter fullscreen mode Exit fullscreen mode

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...
Enter fullscreen mode Exit fullscreen mode

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)))
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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
  }
}
Enter fullscreen mode Exit fullscreen mode

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))
}
Enter fullscreen mode Exit fullscreen mode

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
*/
Enter fullscreen mode Exit fullscreen mode

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)
      )
    )
  )
}
Enter fullscreen mode Exit fullscreen mode

Usage

time(replicateIO(3, printFib))()
/*
5702887
1346269
14930352
Elapsed: 193
*/
Enter fullscreen mode Exit fullscreen mode

With partials...

time(replicateIO(3, time(printFib)))()
/*
3524578
Elapsed: 32
14930352
Elapsed: 125
3524578
Elapsed: 32
Elapsed: 189
*/
Enter fullscreen mode Exit fullscreen mode

Can we make the time combinator more general? We'll see how in the next article.

Top comments (10)

Collapse
 
glebec profile image
Gabriel Lebec •

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.

Collapse
 
newswim profile image
Dan Minshew •

Hey you might enjoy exploring how this term is used in a variety of contexts, it's quite useful!

google.com/search?q=combinatorial+...

Collapse
 
yakulu profile image
Fabien Bourgeois •

About you search on functional JS typing, you may already heard of Sanctuary-def. You loose static analysis but gain runtime (optional) type system. It supports Hindley-Milner like type signature.

Collapse
 
danielo515 profile image
Daniel Rodríguez Rivero •

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

Collapse
 
shnd profile image
SHND •

Seems one parentheses extra here?

export function replicateIO(n: number, mv: IO<void>): IO<void> {
  return concatAll(getMonoid(monoidVoid))(replicate(n, mv))
}
Enter fullscreen mode Exit fullscreen mode

to

export function replicateIO(n: number, mv: IO<void>): IO<void> {
  return concatAll(getMonoid(monoidVoid)(replicate(n, mv))
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
mrwensveen profile image
Matthijs Wensveen •

Just by looking at the number of open and close parens, it looks like your correction is incorrect.

Collapse
 
naorzr profile image
naorzr •

Great article,

Small correction, I believe "contramap" is logically wrong.
Just because we have a function from B->A doesn't necessarily means that applying these functions and then using equal is the same as applying equal to the instances of B.
it lacks assumptions for this to be true.
for example:
lets say B is simply numbers, and A are simply strings,
the function that converts these operate by the following logic, all positive numbers transformed to the latter 'p', and all the negatives to the latter 'n',
so,
f(2) === f(3)
but 2!==3.

Collapse
 
gcanti profile image
Giulio Canti •

but 2!==3

Actually they are equal, under the equivalence relation induced by the function f which is defined as:

x = y if and only if f(x) = f(y)

see "Equivalence kernel" here en.wikipedia.org/wiki/Equivalence_...

Collapse
 
muzietto profile image
Marco Faustinelli •

I don't see any "time" combinator here, and the reference to it in the next post isn't really coming from here. What am I missing?

Collapse
 
gcanti profile image
Giulio Canti •

Example 3 was missing, thanks for pointing out

Read next

sandrockjustin profile image

The Prisma ORM: A Brief Overview and Introduction

sandrockj -

rashedul_islam_rajj profile image

Setup Eslint Prettier in a TypeScript project with mongoose ODM

Rashedul Islam Rajj -

itamartati profile image

📚 Introduction to Angular Documentation

Itamar Tati -

niharikaa profile image

10 Advanced TypeScript Concepts Every Developer Should Know

Niharika Goulikar -