Skip to main content

Monads

Eugenio Moggi

(Eugenio Moggi is a professor of computer science at the University of Genoa, Italy. He first described the general use of monads to structure programs)

Philip Lee Wadler

(Philip Lee Wadler is an American computer scientist known for his contributions to programming language design and type theory)

In the last chapter we have seen how we can compose an effectful program f: (a: A) => F<B> with an n-ary pure program g, if and only if the type constructor F admits an applicative functor instance:

Program fProgram gComposition
purepureg ∘ f
effectfulpure (unary)map(g) ∘ f
effectfulpure, n-aryliftAn(g) ∘ f

But we need to solve one last, quite common, case: when both programs are effectful:

f: (a: A) => F<B>
g: (b: B) => F<C>

What is the composition of f and g?

The problem with nested contexts​

Let's see few examples on why we need something more.

Example (F = Array)

Suppose we want to get followers' followers.

import { pipe } from 'fp-ts/function'
import * as A from 'fp-ts/ReadonlyArray'

interface User {
  readonly id: number
  readonly name: string
  readonly followers: ReadonlyArray<User>
}

const getFollowers = (user: User): ReadonlyArray<User> => user.followers

declare const user: User

// followersOfFollowers: ReadonlyArray<ReadonlyArray<User>>
const followersOfFollowers = pipe(user, getFollowers, A.map(getFollowers))

There's something wrong here, followersOfFollowers has a type ReadonlyArray<ReadonlyArray<User>> but we want ReadonlyArray<User>.

We need to flatten nested arrays.

The function flatten: <A>(mma: ReadonlyArray<ReadonlyArray<A>>) => ReadonlyArray<A> exported by the fp-ts/ReadonlyArray is exactly what we need:

// followersOfFollowers: ReadonlyArray<User>
const followersOfFollowers = pipe(
  user,
  getFollowers,
  A.map(getFollowers),
  A.flatten
)

Cool! Let's see some other data type.

Example (F = Option) Suppose you want to calculate the reciprocal of the first element of a numerical array:

import { pipe } from 'fp-ts/function'
import * as O from 'fp-ts/Option'
import * as A from 'fp-ts/ReadonlyArray'

const inverse = (n: number): O.Option<number> =>
  n === 0 ? O.none : O.some(1 / n)

// inverseHead: O.Option<O.Option<number>>
const inverseHead = pipe([1, 2, 3], A.head, O.map(inverse))

Oops, it happened again, inverseHead has type Option<Option<number>> but we want Option<number>.

We need to flatten again the nested Options.

The flatten: <A>(mma: Option<Option<A>>) => Option<A> function exported by the fp-ts/Option module is what we need:

// inverseHead: O.Option<number>
const inverseHead = pipe([1, 2, 3], A.head, O.map(inverse), O.flatten)

All of those flatten funcitons...They aren't a coincidence, there is a functional pattern behind the scenes: both the type constructors ReadonlyArray and Option (and many others) admit a monad instance and

flatten is the most peculiar operation of monads

Note. A common synonym of flatten is join.

So, what is a monad?

Here is how they are often presented...

Monad Definition​

Definition. A monad is defined by three things:

(1) a type constructor M admitting a functor instance

(2) a function of (also called pure or return) with the following signature:

of: <A>(a: A) => M<A>

(3) a chain function (also called flatMap or bind) with the following signature:

chain: <A, B>(f: (a: A) => M<B>) => (ma: M<A>) => M<B>

The of and chain functions need to obey three laws:

  • chain(of) ∘ f = f (Left identity)
  • chain(f) ∘ of = f (Right identity)
  • chain(h) ∘ (chain(g) ∘ f) = chain((chain(h) ∘ g)) ∘ f (Associativity)

where f, g, h are all effectful functions and ∘ is the usual function composition.

When I saw this definition for the first time I had many questions:

  • why exactly those two operation of and chain? and why to they have those signatures?
  • why do they have those synonyms like "pure" or "flatMap"?
  • why does laws need to hold true? What do they mean?
  • if flatten is so important for monads, why it doesn't compare in its definition?

This chapter will try to answer all of these questions.

Let's get back to the core problem: what is the composition of two effectful functions f and g?

two Kleisli arrows, what's their composition?
(two Kleisli Arrows)

Note. An effectful function is also called Kleisli arrow.

For the time being I don't even know the type of such composition.

But we've already seen some abstractions that talks specifically about composition. Do you remember what we said about categories?

Categories capture the essence of composition

We can transform our problem into a category problem, meaning: can we find a category that models the composition of Kleisli arrows?

The Kleisli category​

Heinrich Kleisli

(Heinrich Kleisli, Swiss mathematician)

Let's try building a category K (called Kleisli category) which contains only Kleisli arrows:

  • objects will be the same objects of the TS category, so all TypeScript types.
  • morphisms are built like this: every time there is a Kleisli arrow f: A ⟼ M<B> in TS we draw an arrow f': A ⟼ B in K
above the TS category, below the K construction

(above the composition in the TS category, below the composition in the K construction)

So what would be the composition of f and g in K? It's th red arrow called h' in the image below:

above the composition in the TS category, below the composition in the K construction

(above the composition in the TS category, below the composition in the K construction)

Given that h' is an arrow from A to C in K, we can find a corresponding function h from A to M<C> in TS.

Thus, a good candidate for the following composition of f and g in TS is still a Kleisli arrow with the following signature: (a: A) => M<C>.

Let's try implementing such a function.

Defining chain step by step​

The first point (1) of the monad definition tells us that M admits a functor instance, thus we can use the map function to transform the function g: (b: B) => M<C> into a function map(g): (mb: M<B>) => M<M<C>>

where chain comes from

(how to obtain the h function)

We're stuck now though: there is no legal operation for the functor instance that allows us to flatten a value of type M<M<C>> into a value of type M<C>, we need an additional operation, let's call it flatten.

If we can define such operation then we can find the composition we were looking for:

h = flatten ∘ map(g) ∘ f

By joining the flatten ∘ map(g) names we get "flatMap", hence the name!

Thus we can get chain in this way

chain = flatten ∘ map(g)
how chain operates on the function g

(how chain operates on the function g)

Now we can update our composition table

Program fProgram gComposition
purepureg ∘ f
effectfulpure (unary)map(g) ∘ f
effectfulpure, n-aryliftAn(g) ∘ f
effectfuleffectfulchain(g) ∘ f

What about of? Well, of comes from the identity morphisms in K: for every identity morphism 1A in K there has to be a corresponding function from A to M<A> (that is, of: <A>(a: A) => M<A>).

where of comes from

(where of comes from)

The fact that of is the neutral element for chain allows this kind of flux control (pretty common):

pipe(
  mb,
  M.chain((b) => (predicate(b) ? M.of(b) : g(b)))
)

where predicate: (b: B) => boolean, mb: M<B> and g: (b: B) => M<B>.

Last question: where do the laws come from? They are nothing else but the categorical laws in K translated to TS:

LawKTS
Left identity1B ∘ f' = f'chain(of) ∘ f = f
Right identityf' ∘ 1A = f'chain(f) ∘ of = f
Associativityh' ∘ (g' ∘ f') = (h' ∘ g') ∘ f'chain(h) ∘ (chain(g) ∘ f) = chain((chain(h) ∘ g)) ∘ f

If we now go back to the examples that showed the problem with nested contexts we can solve them using chain:

import { pipe } from 'fp-ts/function'
import * as O from 'fp-ts/Option'
import * as A from 'fp-ts/ReadonlyArray'

interface User {
  readonly id: number
  readonly name: string
  readonly followers: ReadonlyArray<User>
}

const getFollowers = (user: User): ReadonlyArray<User> => user.followers

declare const user: User

const followersOfFollowers: ReadonlyArray<User> = pipe(
  user,
  getFollowers,
  A.chain(getFollowers)
)

const inverse = (n: number): O.Option<number> =>
  n === 0 ? O.none : O.some(1 / n)

const inverseHead: O.Option<number> = pipe([1, 2, 3], A.head, O.chain(inverse))

Let's see how chain is implemented for the usual type constructors we've already seen:

Example (F = ReadonlyArray)

// transforms functions `B -> ReadonlyArray<C>` into functions `ReadonlyArray<B> -> ReadonlyArray<C>`
const chain = <B, C>(g: (b: B) => ReadonlyArray<C>) => (
  mb: ReadonlyArray<B>
): ReadonlyArray<C> => {
  const out: Array<C> = []
  for (const b of mb) {
    out.push(...g(b))
  }
  return out
}

Example (F = Option)

import { match, none, Option } from 'fp-ts/Option'

// transforms functions `B -> Option<C>` into functions `Option<B> -> Option<C>`
const chain = <B, C>(g: (b: B) => Option<C>): ((mb: Option<B>) => Option<C>) =>
  match(() => none, g)

Example (F = IO)

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

// transforms functions `B -> IO<C>` into functions `IO<B> -> IO<C>`
const chain = <B, C>(g: (b: B) => IO<C>) => (mb: IO<B>): IO<C> => () =>
  g(mb())()

Example (F = Task)

import { Task } from 'fp-ts/Task'

// transforms functions `B -> Task<C>` into functions `Task<B> -> Task<C>`
const chain = <B, C>(g: (b: B) => Task<C>) => (mb: Task<B>): Task<C> => () =>
  mb().then((b) => g(b)())

Example (F = Reader)

import { Reader } from 'fp-ts/Reader'

// transforms functions `B -> Reader<R, C>` into functions `Reader<R, B> -> Reader<R, C>`
const chain = <B, R, C>(g: (b: B) => Reader<R, C>) => (
  mb: Reader<R, B>
): Reader<R, C> => (r) => g(mb(r))(r)

Manipulating programs​

Let's see now, how thanks to referential transparency and the monad concept we can programmaticaly manipulate programs.

Here's a small program that reads / writes a file:

import { log } from 'fp-ts/Console'
import { IO, chain } from 'fp-ts/IO'
import { pipe } from 'fp-ts/function'
import * as fs from 'fs'

// -----------------------------------------
// library functions
// -----------------------------------------

const readFile = (filename: string): IO<string> => () =>
  fs.readFileSync(filename, 'utf-8')

const writeFile = (filename: string, data: string): IO<void> => () =>
  fs.writeFileSync(filename, data, { encoding: 'utf-8' })

// API derived from the previous functions
const modifyFile = (filename: string, f: (s: string) => string): IO<void> =>
  pipe(
    readFile(filename),
    chain((s) => writeFile(filename, f(s)))
  )

// -----------------------------------------
// program
// -----------------------------------------

const program1 = pipe(
  readFile('file.txt'),
  chain(log),
  chain(() => modifyFile('file.txt', (s) => s + '\n// eof')),
  chain(() => readFile('file.txt')),
  chain(log)
)

The actions:

pipe(readFile('file.txt'), chain(log))

is repeated more than once in the program, but given that referential transparency holds we can factor it and assign it to a constant:

const read = pipe(readFile('file.txt'), chain(log))
const modify = modifyFile('file.txt', (s) => s + '\n// eof')

const program2 = pipe(
  read,
  chain(() => modify),
  chain(() => read)
)

We can even define a combinator and leverage it to make the code more compact:

const interleave = <A, B>(action: IO<A>, middle: IO<B>): IO<A> =>
  pipe(
    action,
    chain(() => middle),
    chain(() => action)
  )

const program3 = interleave(read, modify)

Another example: implementing a function similar to Unix' time (the part related to the execution time) for IO.

import * as IO from 'fp-ts/IO'
import { now } from 'fp-ts/Date'
import { log } from 'fp-ts/Console'
import { pipe } from 'fp-ts/function'

// logs the computation lenght in milliseconds
export const time = <A>(ma: IO.IO<A>): IO.IO<A> =>
  pipe(
    now,
    IO.chain((startMillis) =>
      pipe(
        ma,
        IO.chain((a) =>
          pipe(
            now,
            IO.chain((endMillis) =>
              pipe(
                log(`Elapsed: ${endMillis - startMillis}`),
                IO.map(() => a)
              )
            )
          )
        )
      )
    )
  )

Digression. As you can notice, using chain when it is required to maintain a scope leads to verbose code. In languages that support monadic style natively there is often syntax support that goes by the name of "do notation" which eases this kind of situations.

Let's see a Haskell example

now :: IO Int
now = undefined -- `undefined` in Haskell is equivalent to TypeScript's declare

log :: String -> IO ()
log = undefined

time :: IO a -> IO a
time ma = do
  startMillis <- now
  a <- ma
  endMillis <- now
  log ("Elapsed:" ++ show (endMillis - startMillis))
  return a

TypeScript does not support such syntax, but it can be emulated with something similar:

import { log } from 'fp-ts/Console'
import { now } from 'fp-ts/Date'
import { pipe } from 'fp-ts/function'
import * as IO from 'fp-ts/IO'

// logs the computation lenght in milliseconds
export const time = <A>(ma: IO.IO<A>): IO.IO<A> =>
  pipe(
    IO.Do,
    IO.bind('startMillis', () => now),
    IO.bind('a', () => ma),
    IO.bind('endMillis', () => now),
    IO.chainFirst(({ endMillis, startMillis }) =>
      log(`Elapsed: ${endMillis - startMillis}`)
    ),
    IO.map(({ a }) => a)
  )

Let's see a usage example of the time combinator:

import { randomInt } from 'fp-ts/Random'
import { Monoid, concatAll } from 'fp-ts/Monoid'
import { replicate } from 'fp-ts/ReadonlyArray'

const fib = (n: number): number => (n <= 1 ? 1 : fib(n - 1) + fib(n - 2))

// launches `fib` with a random integer between 30 and 35
// logging both the input and output
const randomFib: IO.IO<void> = pipe(
  randomInt(30, 35),
  IO.chain((n) => log([n, fib(n)]))
)

// a monoid instance for `IO<void>`
const MonoidIO: Monoid<IO.IO<void>> = {
  concat: (first, second) => () => {
    first()
    second()
  },
  empty: IO.of(undefined)
}

// executes `n` times the `mv` computation
const replicateIO = (n: number, mv: IO.IO<void>): IO.IO<void> =>
  concatAll(MonoidIO)(replicate(n, mv))

// -------------------
// usage example
// -------------------

time(replicateIO(3, randomFib))()
/*
[ 31, 2178309 ]
[ 33, 5702887 ]
[ 30, 1346269 ]
Elapsed: 89
*/

Logs also the partial:

time(replicateIO(3, time(randomFib)))()
/*
[ 33, 5702887 ]
Elapsed: 54
[ 30, 1346269 ]
Elapsed: 13
[ 32, 3524578 ]
Elapsed: 39
Elapsed: 106
*/

One of the most interesting aspects of working with the monadic interface (map, of, chain) is the possibility to inject dependencies which the program needs, including the way of concatenating different computations.

To see that, let's refactor the small program that reads and writes a file:

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

// -----------------------------------------
// Deps interface, what we would call a "port" in the Hexagonal Architecture
// -----------------------------------------

interface Deps {
  readonly readFile: (filename: string) => IO<string>
  readonly writeFile: (filename: string, data: string) => IO<void>
  readonly log: <A>(a: A) => IO<void>
  readonly chain: <A, B>(f: (a: A) => IO<B>) => (ma: IO<A>) => IO<B>
}

// -----------------------------------------
// program
// -----------------------------------------

const program4 = (D: Deps) => {
  const modifyFile = (filename: string, f: (s: string) => string) =>
    pipe(
      D.readFile(filename),
      D.chain((s) => D.writeFile(filename, f(s)))
    )

  return pipe(
    D.readFile('file.txt'),
    D.chain(D.log),
    D.chain(() => modifyFile('file.txt', (s) => s + '\n// eof')),
    D.chain(() => D.readFile('file.txt')),
    D.chain(D.log)
  )
}

// -----------------------------------------
// a `Deps` instance, what we would call an "adapter" in the Hexagonal Architecture
// -----------------------------------------

import * as fs from 'fs'
import { log } from 'fp-ts/Console'
import { chain } from 'fp-ts/IO'

const DepsSync: Deps = {
  readFile: (filename) => () => fs.readFileSync(filename, 'utf-8'),
  writeFile: (filename: string, data: string) => () =>
    fs.writeFileSync(filename, data, { encoding: 'utf-8' }),
  log,
  chain
}

// dependency injection
program4(DepsSync)()

There's more, we can even abstract the effect in which the program runs. We can define our own FileSystem effect (the effect representing read-write operations over the file system):

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

// -----------------------------------------
// our program's effect
// -----------------------------------------

interface FileSystem<A> extends IO<A> {}

// -----------------------------------------
// dependencies
// -----------------------------------------

interface Deps {
  readonly readFile: (filename: string) => FileSystem<string>
  readonly writeFile: (filename: string, data: string) => FileSystem<void>
  readonly log: <A>(a: A) => FileSystem<void>
  readonly chain: <A, B>(
    f: (a: A) => FileSystem<B>
  ) => (ma: FileSystem<A>) => FileSystem<B>
}

// -----------------------------------------
// program
// -----------------------------------------

const program4 = (D: Deps) => {
  const modifyFile = (filename: string, f: (s: string) => string) =>
    pipe(
      D.readFile(filename),
      D.chain((s) => D.writeFile(filename, f(s)))
    )

  return pipe(
    D.readFile('file.txt'),
    D.chain(D.log),
    D.chain(() => modifyFile('file.txt', (s) => s + '\n// eof')),
    D.chain(() => D.readFile('file.txt')),
    D.chain(D.log)
  )
}

With a simple change in the definition of the FileSystem effect. we can modify the program to make it run asynchronously

// -----------------------------------------
// our program's effect
// -----------------------------------------

-interface FileSystem<A> extends IO<A> {}
+interface FileSystem<A> extends Task<A> {}

now all there's left is to modify the Deps instance to adapt to the new definition.

import { Task } from 'fp-ts/Task'
import { pipe } from 'fp-ts/function'

// -----------------------------------------
// our program's effect (modified)
// -----------------------------------------

interface FileSystem<A> extends Task<A> {}

// -----------------------------------------
// dependencies (NOT modified)
// -----------------------------------------

interface Deps {
  readonly readFile: (filename: string) => FileSystem<string>
  readonly writeFile: (filename: string, data: string) => FileSystem<void>
  readonly log: <A>(a: A) => FileSystem<void>
  readonly chain: <A, B>(
    f: (a: A) => FileSystem<B>
  ) => (ma: FileSystem<A>) => FileSystem<B>
}

// -----------------------------------------
// program (NOT modified)
// -----------------------------------------

const program5 = (D: Deps) => {
  const modifyFile = (filename: string, f: (s: string) => string) =>
    pipe(
      D.readFile(filename),
      D.chain((s) => D.writeFile(filename, f(s)))
    )

  return pipe(
    D.readFile('file.txt'),
    D.chain(D.log),
    D.chain(() => modifyFile('file.txt', (s) => s + '\n// eof')),
    D.chain(() => D.readFile('file.txt')),
    D.chain(D.log)
  )
}

// -----------------------------------------
// a `Deps` instance (modified)
// -----------------------------------------

import * as fs from 'fs'
import { log } from 'fp-ts/Console'
import { chain, fromIO } from 'fp-ts/Task'

const DepsAsync: Deps = {
  readFile: (filename) => () =>
    new Promise((resolve) =>
      fs.readFile(filename, { encoding: 'utf-8' }, (_, s) => resolve(s))
    ),
  writeFile: (filename: string, data: string) => () =>
    new Promise((resolve) => fs.writeFile(filename, data, () => resolve())),
  log: (a) => fromIO(log(a)),
  chain
}

// dependency injection
program5(DepsAsync)()

Quiz. The previous examples overlook, on purpose, possible errors. Example give: the file we're operating on may not exist at all. How could we modify the FileSystem effect to take this into account?

import { Task } from 'fp-ts/Task'
import { pipe } from 'fp-ts/function'
import * as E from 'fp-ts/Either'

// -----------------------------------------
// our program's effect (modified)
// -----------------------------------------

interface FileSystem<A> extends Task<E.Either<Error, A>> {}

// -----------------------------------------
// dependencies (NOT modified)
// -----------------------------------------

interface Deps {
  readonly readFile: (filename: string) => FileSystem<string>
  readonly writeFile: (filename: string, data: string) => FileSystem<void>
  readonly log: <A>(a: A) => FileSystem<void>
  readonly chain: <A, B>(
    f: (a: A) => FileSystem<B>
  ) => (ma: FileSystem<A>) => FileSystem<B>
}

// -----------------------------------------
// program (NOT modified)
// -----------------------------------------

const program5 = (D: Deps) => {
  const modifyFile = (filename: string, f: (s: string) => string) =>
    pipe(
      D.readFile(filename),
      D.chain((s) => D.writeFile(filename, f(s)))
    )

  return pipe(
    D.readFile('-.txt'),
    D.chain(D.log),
    D.chain(() => modifyFile('file.txt', (s) => s + '\n// eof')),
    D.chain(() => D.readFile('file.txt')),
    D.chain(D.log)
  )
}

// -----------------------------------------
// `Deps` instance (modified)
// -----------------------------------------

import * as fs from 'fs'
import { log } from 'fp-ts/Console'
import { chain, fromIO } from 'fp-ts/TaskEither'

const DepsAsync: Deps = {
  readFile: (filename) => () =>
    new Promise((resolve) =>
      fs.readFile(filename, { encoding: 'utf-8' }, (err, s) => {
        if (err !== null) {
          resolve(E.left(err))
        } else {
          resolve(E.right(s))
        }
      })
    ),
  writeFile: (filename: string, data: string) => () =>
    new Promise((resolve) =>
      fs.writeFile(filename, data, (err) => {
        if (err !== null) {
          resolve(E.left(err))
        } else {
          resolve(E.right(undefined))
        }
      })
    ),
  log: (a) => fromIO(log(a)),
  chain
}

// dependency injection
program5(DepsAsync)().then(console.log)

Demo

06_game.ts