This repo introduces functional programming concepts using TypeScript and possibly libraries in the fp-ts ecosystem.

This fork is an edited translation of Giulio Canti's "Introduction to Functional Programming (Italian)". The author uses the original as a reference and supporting material for his lectures and workshops on functional programming.

The purpose of the edits is to expand on the material without changing the concepts nor structure, for more information about the edit's goals see the CONTRIBUTING file.

Read it Online

For a best reading experience, read it online via Gitbook.

• Quick-access side-bar
• In-browser exercises
• In-depth examples

Setup

git clone https://github.com/gcanti/functional-programming.git
cd functional-programming
npm i

What is functional programming

Functional Programming is programming with pure functions. Mathematical functions.

A quick search on the internet may lead you to the following definition:

A (pure) function is a procedure that given the same input always return the same output without any observable side-effect.

The term "side effect" does not yet have any specific meaning (we'll see in the future how to give a formal definition), what matters is to have some sort of intuition, think about opening a file or writing into a database.

For the time being we can limit ourselves to say that a side effect is anything a function does besides returning a value.

What is the structure of a program that uses exclusively pure functions?

A functional program tends to be written like a pipeline:

const program = pipe(
  input,
  f1, // pure function
  f2, // pure function
  f3, // pure function
  ...
)

What happens here is that input is passed to the first function f1, which returns a value that is passed to the second function f2, which returns a value that is passed as an argument to the third function f3, and so on.

Demo

00_pipe_and_flow.ts

We'll see how functional programming provides us with tools to structure our code in that style.

Other than understanding what functional programming is, it is also essential to understand what is it's goal.

Functional programming's goal is to tame a system's complexity through the use of formal models, and to give careful attention to code's properties and refactoring ease.

Functional programming will help teach people the mathematics behind program construction:

• how to write composable code
• how to reason about side effects
• how to write consistent, general, less ad-hoc APIs

What does it mean to give careful attention to code's properties? Let's see with an example:

Example

Why can we say that the Array's map method is "more functional" than a for loop?

// input
const xs: Array<number> = [1, 2, 3]

// transformation
const double = (n: number): number => n * 2

// result: I want an array where each `xs`' element is doubled
const ys: Array<number> = []
for (let i = 0; i <= xs.length; i++) {
  ys.push(double(xs[i]))
}

A for loop offers a lot of flexibility, I can modify:

• the starting index, let i = 0
• the looping condition, i < xs.length
• the step change, i++.

This also implies that I may introduce errors and that I have no guarantees about the returned value.

Quiz. Is the for loop correct?

See the answer here

Let's rewrite the same exercise using map.

// input
const xs: Array<number> = [1, 2, 3]

// transformation
const double = (n: number): number => n * 2

// result: I want an array where each `xs`' element is doubled
const ys: Array<number> = xs.map(double)

We can note how map lacks the same flexibility of a for loop, but it offers us some guarantees:

• all the elements of the input array will be processed
• the resulting array will always have the same number of elements as the starting one

In functional programming, where there's an emphasis on code properties rather than implementation details, the map operation is interesting due to its limitations

Think about how easier it is to review a PR that involves map rather than a for loop.

The two pillars of functional programming

Functional programming is based on the following two pillars:

• Referential transparency
• Composition (as universal design pattern)

All of the remaining content derives directly or indirectly from those two points.

Referential transparency

Definition. An expression is said to be referentially transparent if it can be replaced with its corresponding value without changing the program's behavior

Example (referential transparency implies the use of pure functions)

const double = (n: number): number => n * 2

const x = double(2)
const y = double(2)

The expression double(2) has the referential transparency property because it is replaceable with its value, the number 4.

Thus I can proceed with the following refactor

const x = 4
const y = x

Not every expression is referentially transparent, let's see an example.

Example (referential transparency implies not throwing exceptions)

const inverse = (n: number): number => {
  if (n === 0) throw new Error('cannot divide by zero')
  return 1 / n
}

const x = inverse(0) + 1

I can't replace inverse(0) with its value, thus it is not referentially transparent.

Example (referential transparency requires the use of immutable data structures)

const xs = [1, 2, 3]

const append = (xs: Array<number>): void => {
  xs.push(4)
}

append(xs)

const ys = xs

On the last line I cannot replace xs with its initial value [1, 2, 3] since it has been changed by calling append.

Why is referential transparency so important? Because it allows us to:

• reason about code locally, there is no need to know external context in order to understand a fragment of code
• refactor without changing our system's behaviour

Quiz. Suppose we have the following program:

// In TypeScript `declare` allows to introduce a definition without requiring an implementation
declare const question: (message: string) => Promise<string>

const x = await question('What is your name?')
const y = await question('What is your name?')

Can I refactor in this way? Does the program's behavior change or is it going to change?

const x = await question('What is your name?')
const y = x

The answer is: there's no way to know without reading question's implementation.

As you can see, refactoring a program including non-referentially transparent expressions might be challenging. In functional programming, where every expression is referentially transparent, the cognitive load required to make changes is severely reduced.

Composition

Functional programming's fundamental pattern is composition: we compose small units of code accomplishing very specific tasks into larger and complex units.

An example of a "from the smallest to the largest" composition pattern we can think of:

• composing two or more primitive values (numbers or strings)
• composing two or more functions
• composing entire programs

In the very last example we can speak of modular programming:

By modular programming I mean the process of building large programs by gluing together smaller programs - Simon Peyton Jones

This programming style is achievable through the use of combinators.

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

The general concept of a combinator is rather vague and it can appear in different forms, but the simplest one is this:

combinator: Thing -> Thing

Example. The function double combines two numbers.

The goal of a combinator is to create new Things from Things already defined.

Since the output of a combinator, the new Thing, can be passed around as input to other programs and combinators, we obtain a combinatorial explosion of opportunities, which makes this pattern extremely powerful.

Example

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

const double = (n: number): number => n * 2

console.log(pipe(2, double, double, double)) // => 16

Thus the usual design you can find in a functional module is:

• a model for some type T
• a small set of "primitives" of type T
• a set of combinators to combine the primitives in larger structures

Let's try to implement such a module:

Demo

01_retry.ts

As you can see from the previous demo, with merely 3 primitives and two combinators we've been able to express a pretty complex policy.

Think at how just adding a single new primitive, or a single combinator to those already defined, adds expressive possibilities exponentially.

Of the two combinators in 01_retry.ts a special mention goes to concat since it refers to a very powerful functional programming abstraction: semigroups.

Modelling composition with Semigroups

A semigroup is a recipe to combine two, or more, values.

A semigroup is an algebra, which is generally defined as a specific combination of:

• one or more sets
• one or more operations on those sets
• zero or more laws on the previous operations

Algebras are how mathematicians try to capture an idea in its purest form, eliminating everything that is superfluous.

When an algebra is modified the only allowed operations are those defined by the algebra itself according to its own laws

Algebras can be thought of as an abstraction of interfaces:

When an interface is modified the only allowed operations are those defined by the interface itself according to its own laws

Before getting into semigroups, let's see first an example of an algebra, a magma.

Definition of a Magma

A Magma is a very simple algebra:

• a set or type (A)
• a concat operation
• no laws to obey

Note: in most cases the terms set and type can be used interchangeably.

We can use a TypeScript interface to model a Magma.

interface Magma<A> {
  readonly concat: (first: A, second: A) => A
}

Thus, we have have the ingredients for an algebra:

• a set A
• an operation on the set A, concat. This operation is said to be closed on the set A which means that whichever elements A we apply the operation on the result will still be an element of A. Since the result is still an A, it can be used again as an input for concat and the operation can be repeated how many times we want. In other words concat is a combinator for the type A.

Let's implement a concrete instance of Magma<A> with A being the number type.

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

const MagmaSub: Magma<number> = {
  concat: (first, second) => first - second
}

// helper
const getPipeableConcat = <A>(M: Magma<A>) => (second: A) => (first: A): A =>
  M.concat(first, second)

const concat = getPipeableConcat(MagmaSub)

// usage example

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

pipe(10, concat(2), concat(3), concat(1), concat(2), console.log)
// => 2

Quiz. The fact that concat is a closed operation isn't a trivial detail. If A is the set of natural numbers (defined as positive integers) instead of the JavaScript number type (a set of positive and negative floats), could we define a Magma<Natural> with concat implemented like in MagmaSub? Can you think of any other concat operation on natural numbers for which the closure property isn't valid?

See the answer here

Definition. Given A a non empty set and * a binary operation closed on (or internal to) A, then the pair (A, *) is called a magma.

Magmas do not obey any law, they only have the closure requirement. Let's see an algebra that do requires another law: semigroups.

Definition of a Semigroup

Given a Magma if the concat operation is associative then it's a semigroup.

The term "associative" means that the equation:

(x * y) * z = x * (y * z)

// or
concat(concat(a, b), c) = concat(a, concat(b, c))

holds for any x, y, z in A.

In layman terms associativity tells us that we do not have to worry about parentheses in expressions and that we can simply write x * y * z (there's no ambiguity).

Example

String concatenation benefits from associativity.

("a" + "b") + "c" = "a" + ("b" + "c") = "abc"

Every semigroup is a magma, but not every magma is a semigroup.

Example

The previous MagmaSub is not a semigroup because its concat operation is not associative.

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

const MagmaSub: Magma<number> = {
  concat: (first, second) => first - second
}

pipe(MagmaSub.concat(MagmaSub.concat(1, 2), 3), console.log) // => -4
pipe(MagmaSub.concat(1, MagmaSub.concat(2, 3)), console.log) // => 2

Semigroups capture the essence of parallelizable operations

If we know that there is such an operation that follows the associativity law, we can further split a computation into two sub computations, each of them could be further split into sub computations.

a * b * c * d * e * f * g * h = ((a * b) * (c * d)) * ((e * f) * (g * h))

Sub computations can be run in parallel mode.

As for Magma, Semigroups are implemented through a TypeScript interface:

// fp-ts/lib/Semigroup.ts

interface Semigroup<A> extends Magma<A> {}

The following law has to hold true:

• Associativity: If S is a semigroup the following has to hold true:

S.concat(S.concat(x, y), z) = S.concat(x, S.concat(y, z))

for every x, y, z of type A

Note. Sadly it is not possible to encode this law using TypeScript's type system.

Let's implement a semigroup for some ReadonlyArray<string>:

import * as Se from 'fp-ts/Semigroup'

const Semigroup: Se.Semigroup<ReadonlyArray<string>> = {
  concat: (first, second) => first.concat(second)
}

The name concat makes sense for arrays (as we'll see later) but, depending on the context and the type A on whom we're implementing an instance, the concat semigroup operation may have different interpretations and meanings:

• "concatenation"
• "combination"
• "merging"
• "fusion"
• "selection"
• "sum"
• "substitution"

and many others.

Example

This is how to implement the semigroup (number, +) where + is the usual addition of numbers:

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

/** number `Semigroup` under addition */
const SemigroupSum: Semigroup<number> = {
  concat: (first, second) => first + second
}

Quiz. Can the concat combinator defined in the demo 01_retry.ts be used to define a Semigroup instance for the RetryPolicy type?

See the answer here

This is the implementation for the semigroup (number, *) where * is the usual number multiplication:

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

/** number `Semigroup` under multiplication */
const SemigroupProduct: Semigroup<number> = {
  concat: (first, second) => first * second
}

Note It is a common mistake to think about the semigroup of numbers, but for the same type A it is possible to define more instances of Semigroup<A>. We've seen how for number we can define a semigroup under addition and multiplication. It is also possible to have Semigroups that share the same operation but differ in types. SemigroupSum could've been implemented on natural numbers instead of unsigned floats like number.

Another example, with the string type:

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

const SemigroupString: Semigroup<string> = {
  concat: (first, second) => first + second
}

Another two examples, this time with the boolean type:

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

const SemigroupAll: Semigroup<boolean> = {
  concat: (first, second) => first && second
}

const SemigroupAny: Semigroup<boolean> = {
  concat: (first, second) => first || second
}

The concatAll function

By definition concat combines merely two elements of A every time. Is it possible to combine any number of them?

The concatAll function takes:

• an instance of a semigroup
• an initial value
• an array of elements

import * as S from 'fp-ts/Semigroup'
import * as N from 'fp-ts/number'

const sum = S.concatAll(N.SemigroupSum)(2)

console.log(sum([1, 2, 3, 4])) // => 12

const product = S.concatAll(N.SemigroupProduct)(3)

console.log(product([1, 2, 3, 4])) // => 72

Quiz. Why do I need to provide an initial value?

-> See the answer here

Example

Lets provide some applications of concatAll, by reimplementing some popular functions from the JavaScript standard library.

import * as B from 'fp-ts/boolean'
import { concatAll } from 'fp-ts/Semigroup'
import * as S from 'fp-ts/struct'

const every = <A>(predicate: (a: A) => boolean) => (
  as: ReadonlyArray<A>
): boolean => concatAll(B.SemigroupAll)(true)(as.map(predicate))

const some = <A>(predicate: (a: A) => boolean) => (
  as: ReadonlyArray<A>
): boolean => concatAll(B.SemigroupAny)(false)(as.map(predicate))

const assign: (as: ReadonlyArray<object>) => object = concatAll(
  S.getAssignSemigroup<object>()
)({})

Quiz. Is the following semigroup instance lawful (does it respect semigroup laws)?

See the answer here

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

/** Always return the first argument */
const first = <A>(): Semigroup<A> => ({
  concat: (first, _second) => first
})

Quiz. Is the following semigroup instance lawful?

See the answer here

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

/** Always return the second argument */
const last = <A>(): Semigroup<A> => ({
  concat: (_first, second) => second
})

The dual semigroup

Given a semigroup instance, it is possible to obtain a new semigroup instance by simply swapping the order in which the operands are combined:

import { pipe } from 'fp-ts/function'
import { Semigroup } from 'fp-ts/Semigroup'
import * as S from 'fp-ts/string'

// This is a Semigroup combinator
const reverse = <A>(S: Semigroup<A>): Semigroup<A> => ({
  concat: (first, second) => S.concat(second, first)
})

pipe(S.Semigroup.concat('a', 'b'), console.log) // => 'ab'
pipe(reverse(S.Semigroup).concat('a', 'b'), console.log) // => 'ba'

Quiz. This combinator makes sense because, generally speaking, the concat operation is not commutative, can you find an example where concat is commutative and one where it isn't?

See the answer here

Semigroup product

Let's try defining a semigroup instance for more complex types:

import * as N from 'fp-ts/number'
import { Semigroup } from 'fp-ts/Semigroup'

// models a vector starting at the origin
type Vector = {
  readonly x: number
  readonly y: number
}

// models a sum of two vectors
const SemigroupVector: Semigroup<Vector> = {
  concat: (first, second) => ({
    x: N.SemigroupSum.concat(first.x, second.x),
    y: N.SemigroupSum.concat(first.y, second.y)
  })
}

Example

const v1: Vector = { x: 1, y: 1 }
const v2: Vector = { x: 1, y: 2 }

console.log(SemigroupVector.concat(v1, v2)) // => { x: 2, y: 3 }

Too much boilerplate? The good news is that the mathematical theory behind semigroups tells us we can implement a semigroup instance for a struct like Vector if we can implement a semigroup instance for each of its fields.

Conveniently the fp-ts/Semigroup module exports a struct combinator:

import { struct } from 'fp-ts/Semigroup'

// models the sum of two vectors
const SemigroupVector: Semigroup<Vector> = struct({
  x: N.SemigroupSum,
  y: N.SemigroupSum
})

Note. There is a combinator similar to struct that works with tuples: tuple

import * as N from 'fp-ts/number'
import { Semigroup, tuple } from 'fp-ts/Semigroup'

// models a vector starting from origin
type Vector = readonly [number, number]

// models the sum of two vectors
const SemigroupVector: Semigroup<Vector> = tuple(N.SemigroupSum, N.SemigroupSum)

const v1: Vector = [1, 1]
const v2: Vector = [1, 2]

console.log(SemigroupVector.concat(v1, v2)) // => [2, 3]

Quiz. Is it true that given any Semigroup<A> and having chosen any middle of A, if I insert it between the two concat parameters the result is still a semigroup?

import { pipe } from 'fp-ts/function'
import { Semigroup } from 'fp-ts/Semigroup'
import * as S from 'fp-ts/string'

export const intercalate = <A>(middle: A) => (
  S: Semigroup<A>
): Semigroup<A> => ({
  concat: (first, second) => S.concat(S.concat(first, middle), second)
})

const SemigroupIntercalate = pipe(S.Semigroup, intercalate('|'))

pipe(
  SemigroupIntercalate.concat('a', SemigroupIntercalate.concat('b', 'c')),
  console.log
) // => 'a|b|c'

Finding a Semigroup instance for any type

The associativity property is a very strong requirement, what happens if, given a specific type A we can't find an associative operation on A?

Suppose we have a type User defined as:

type User = {
  readonly id: number
  readonly name: string
}

and that inside my database we have multiple copies of the same User (e.g. they could be historical entries of its modifications).

// internal APIs
declare const getCurrent: (id: number) => User
declare const getHistory: (id: number) => ReadonlyArray<User>

and that we need to implement a public API

export declare const getUser: (id: number) => User

which takes into account all of its copies depending on some criteria. The criteria should be to return the most recent copy, or the oldest one, or the current one, etc..

Naturally we can define a specific API for each of these criterias:

export declare const getMostRecentUser: (id: number) => User
export declare const getLeastRecentUser: (id: number) => User
export declare const getCurrentUser: (id: number) => User
// etc...

Thus, to return a value of type User I need to consider all the copies and make a merge (or selection) of them, meaning I can model the criteria problem with a Semigroup<User>.

That being said, it is not really clear right now what it means to "merge two Users" nor if this merge operation is associative.

You can always define a Semigroup instance for any given type A by defining a semigroup instance not for A itself but for NonEmptyArray<A> called the free semigroup of A:

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

// represents a non-empty array, meaning an array that has at least one element A
type ReadonlyNonEmptyArray<A> = ReadonlyArray<A> & {
  readonly 0: A
}

// the concatenation of two NonEmptyArrays is still a NonEmptyArray
const getSemigroup = <A>(): Semigroup<ReadonlyNonEmptyArray<A>> => ({
  concat: (first, second) => [first[0], ...first.slice(1), ...second]
})

and then we can map the elements of A to "singletons" of ReadonlyNonEmptyArray<A>, meaning arrays with only one element.

// insert an element into a non empty array
const of = <A>(a: A): ReadonlyNonEmptyArray<A> => [a]

Let's apply this technique to the User type:

import {
  getSemigroup,
  of,
  ReadonlyNonEmptyArray
} from 'fp-ts/ReadonlyNonEmptyArray'
import { Semigroup } from 'fp-ts/Semigroup'

type User = {
  readonly id: number
  readonly name: string
}

// this semigroup is not for the `User` type but for `ReadonlyNonEmptyArray<User>`
const S: Semigroup<ReadonlyNonEmptyArray<User>> = getSemigroup<User>()

declare const user1: User
declare const user2: User
declare const user3: User

// const merge: ReadonlyNonEmptyArray<User>
const merge = S.concat(S.concat(of(user1), of(user2)), of(user3))

// I can get the same result by "packing" the users manually into an array
const merge2: ReadonlyNonEmptyArray<User> = [user1, user2, user3]

Thus, the free semigroup of A is merely another semigroup in which the elements are all possible, non empty, finite sequences of A.

The free semigroup of A can be seen as a lazy way to concatenate elements of type A while preserving their data content.

The merge value, containing [user1, user2, user3], tells us which are the elements to concatenate and in which order they are.

Now I have three possible options to design the getUser API:

1. I can define Semigroup<User> and I want to get straight into mergeing.

declare const SemigroupUser: Semigroup<User>

export const getUser = (id: number): User => {
  const current = getCurrent(id)
  const history = getHistory(id)
  return concatAll(SemigroupUser)(current)(history)
}

2. I can't define Semigroup<User> or I want to leave the merging strategy open to implementation, thus I'll ask it to the API consumer:

export const getUser = (SemigroupUser: Semigroup<User>) => (
  id: number
): User => {
  const current = getCurrent(id)
  const history = getHistory(id)
  // merge immediately
  return concatAll(SemigroupUser)(current)(history)
}

3. I can't define Semigroup<User> nor I want to require it.

In this case the free semigroup of User can come to the rescue:

export const getUser = (id: number): ReadonlyNonEmptyArray<User> => {
  const current = getCurrent(id)
  const history = getHistory(id)
  // I DO NOT proceed with merging and return the free semigroup of User
  return [current, ...history]
}

It should be noted that, even when I do have a Semigroup<A> instance, using a free semigroup might be still convenient for the following reasons:

• avoids executing possibly expensive and pointless computations
• avoids passing around the semigroup instance
• allows the API consumer to decide which is the correct merging strategy (by using concatAll).

Order-derivable Semigroups

Given that number is a total order (meaning that whichever x and y we choose, one of those two conditions has to hold true: x <= y or y <= x) we can define another two Semigroup<number> instances using the min or max operations.

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

const SemigroupMin: Semigroup<number> = {
  concat: (first, second) => Math.min(first, second)
}

const SemigroupMax: Semigroup<number> = {
  concat: (first, second) => Math.max(first, second)
}

Quiz. Why is it so important that number is a total order?

It would be very useful to define such semigroups (SemigroupMin and SemigroupMax) for different types than number.

Is it possible to capture the notion of being totally ordered for other types?

To speak about ordering we first need to capture the notion of equality.

Modelling equivalence with Eq

Yet again, we can model the notion of equality.

Equivalence relations capture the concept of equality of elements of the same type. The concept of an equivalence relation can be implemented in TypeScript with the following interface:

interface Eq<A> {
  readonly equals: (first: A, second: A) => boolean
}

Intuitively:

• if equals(x, y) = true then we say x and y are equal
• if equals(x, y) = false then we say x and y are different

Example

This is an instance of Eq for the number type:

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

const EqNumber: Eq<number> = {
  equals: (first, second) => first === second
}

pipe(EqNumber.equals(1, 1), console.log) // => true
pipe(EqNumber.equals(1, 2), console.log) // => false

The following laws have to hold true:

1. Reflexivity: equals(x, x) === true, for every x in A
2. Symmetry: equals(x, y) === equals(y, x), for every x, y in A
3. Transitivity: if equals(x, y) === true and equals(y, z) === true, then equals(x, z) === true, for every x, y, z in A

Quiz. Would a combinator reverse: <A>(E: Eq<A>) => Eq<A> make sense?

Quiz. Would a combinator not: <A>(E: Eq<A>) => Eq<A> make sense?

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

export const not = <A>(E: Eq<A>): Eq<A> => ({
  equals: (first, second) => !E.equals(first, second)
})

Example

Let's see the first example of the usage of the Eq abstraction by defining a function elem that checks whether a given value is an element of ReadonlyArray.

import { Eq } from 'fp-ts/Eq'
import { pipe } from 'fp-ts/function'
import * as N from 'fp-ts/number'

// returns `true` if the element `a` is included in the list `as`
const elem = <A>(E: Eq<A>) => (a: A) => (as: ReadonlyArray<A>): boolean =>
  as.some((e) => E.equals(a, e))

pipe([1, 2, 3], elem(N.Eq)(2), console.log) // => true
pipe([1, 2, 3], elem(N.Eq)(4), console.log) // => false

Why would we not use the native includes Array method?

console.log([1, 2, 3].includes(2)) // => true
console.log([1, 2, 3].includes(4)) // => false

Let's define some Eq instance for more complex types.

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

type Point = {
  readonly x: number
  readonly y: number
}

const EqPoint: Eq<Point> = {
  equals: (first, second) => first.x === second.x && first.y === second.y
}

console.log(EqPoint.equals({ x: 1, y: 2 }, { x: 1, y: 2 })) // => true
console.log(EqPoint.equals({ x: 1, y: 2 }, { x: 1, y: -2 })) // => false

and check the results of elem and includes

const points: ReadonlyArray<Point> = [
  { x: 0, y: 0 },
  { x: 1, y: 1 },
  { x: 2, y: 2 }
]

const search: Point = { x: 1, y: 1 }

console.log(points.includes(search)) // => false :(
console.log(pipe(points, elem(EqPoint)(search))) // => true :)

Quiz (JavaScript). Why does the includes method returns false?

-> See the answer here

Abstracting the concept of equality is of paramount importance, especially in a language like JavaScript where some data types do not offer handy APIs for checking user-defined equality.

The JavaScript native Set datatype suffers by the same issue:

type Point = {
  readonly x: number
  readonly y: number
}

const points: Set<Point> = new Set([{ x: 0, y: 0 }])

points.add({ x: 0, y: 0 })

console.log(points)
// => Set { { x: 0, y: 0 }, { x: 0, y: 0 } }

Given the fact that Set uses === ("strict equality") for comparing values, points now contains two identical copies of { x: 0, y: 0 }, a result we definitely did not want. Thus it is convenient to define a new API to add an element to a Set, one that leverages the Eq abstraction.

Quiz. What would be the signature of this API?

Does EqPoint require too much boilerplate? The good news is that theory offers us yet again the possibility of implementing an Eq instance for a struct like Point if we are able to define an Eq instance for each of its fields.

Conveniently the fp-ts/Eq module exports a struct combinator:

import { Eq, struct } from 'fp-ts/Eq'
import * as N from 'fp-ts/number'

type Point = {
  readonly x: number
  readonly y: number
}

const EqPoint: Eq<Point> = struct({
  x: N.Eq,
  y: N.Eq
})

Note. Like for Semigroup, we aren't limited to struct-like data types, we also have combinators for working with tuples: tuple

import { Eq, tuple } from 'fp-ts/Eq'
import * as N from 'fp-ts/number'

type Point = readonly [number, number]

const EqPoint: Eq<Point> = tuple(N.Eq, N.Eq)

console.log(EqPoint.equals([1, 2], [1, 2])) // => true
console.log(EqPoint.equals([1, 2], [1, -2])) // => false

There are other combinators exported by fp-ts, here we can see a combinator that allows us to derive an Eq instance for ReadonlyArrays.

import { Eq, tuple } from 'fp-ts/Eq'
import * as N from 'fp-ts/number'
import * as RA from 'fp-ts/ReadonlyArray'

type Point = readonly [number, number]

const EqPoint: Eq<Point> = tuple(N.Eq, N.Eq)

const EqPoints: Eq<ReadonlyArray<Point>> = RA.getEq(EqPoint)

Similarly to Semigroups, it is possible to define more than one Eq instance for the same given type. Suppose we have modeled a User with the following type:

type User = {
  readonly id: number
  readonly name: string
}

we can define a "standard" Eq<User> instance using the struct combinator:

import { Eq, struct } from 'fp-ts/Eq'
import * as N from 'fp-ts/number'
import * as S from 'fp-ts/string'

type User = {
  readonly id: number
  readonly name: string
}

const EqStandard: Eq<User> = struct({
  id: N.Eq,
  name: S.Eq
})

Several languages, even pure functional languages like Haskell, do not allow to have more than one Eq instance per data type. But we may have different contexts where the meaning of User equality might differ. One common context is where two Users are equal if their id field is equal.

/** two users are equal if their `id` fields are equal */
const EqID: Eq<User> = {
  equals: (first, second) => N.Eq.equals(first.id, second.id)
}

Now that we made an abstract concept concrete by representing it as a data structure, we can programmatically manipulate Eq instances like we do with other data structures. Let's see an example.

Example. Rather than manually defining EqId we can use the combinator contramap: given an instance Eq<A> and a function from B to A, we can derive an Eq<B>

import { Eq, struct, contramap } from 'fp-ts/Eq'
import { pipe } from 'fp-ts/function'
import * as N from 'fp-ts/number'
import * as S from 'fp-ts/string'

type User = {
  readonly id: number
  readonly name: string
}

const EqStandard: Eq<User> = struct({
  id: N.Eq,
  name: S.Eq
})

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

console.log(
  EqStandard.equals({ id: 1, name: 'Giulio' }, { id: 1, name: 'Giulio Canti' })
) // => false (because the `name` property differs)

console.log(
  EqID.equals({ id: 1, name: 'Giulio' }, { id: 1, name: 'Giulio Canti' })
) // => true (even though the `name` property differs)

console.log(EqID.equals({ id: 1, name: 'Giulio' }, { id: 2, name: 'Giulio' }))
// => false (even though the `name` property is equal)

Quiz. Given a data type A, is it possible to define a Semigroup<Eq<A>>? What could it represent?

Modeling ordering relations with Ord

In the previous chapter regarding Eq we were dealing with the concept of equality. In this one we'll deal with the concept of ordering.

The concept of a total order relation can be implemented in TypeScript as following:

import { Eq } from 'fp-ts/lib/Eq'

type Ordering = -1 | 0 | 1

interface Ord<A> extends Eq<A> {
  readonly compare: (x: A, y: A) => Ordering
}

Resulting in:

• x < y if and only if compare(x, y) = -1
• x = y if and only if compare(x, y) = 0
• x > y if and only if compare(x, y) = 1

Example

Let's try to define an Ord instance for the type number:

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

const OrdNumber: Ord<number> = {
  equals: (first, second) => first === second,
  compare: (first, second) => (first < second ? -1 : first > second ? 1 : 0)
}

The following laws have to hold true:

1. Reflexivity: compare(x, x) <= 0, for every x in A
2. Antisymmetry: if compare(x, y) <= 0 and compare(y, x) <= 0 then x = y, for every x, y in A
3. Transitivity: if compare(x, y) <= 0 and compare(y, z) <= 0 then compare(x, z) <= 0, for every x, y, z in A

compare has also to be compatible with the equals operation from Eq:

compare(x, y) === 0 if and only if equals(x, y) === true, for every x, y in A

Note. equals can be derived from compare in the following way:

equals: (first, second) => compare(first, second) === 0

In fact the fp-ts/Ord module exports a handy helper fromCompare which allows us to define an Ord instance simply by supplying the compare function:

import { Ord, fromCompare } from 'fp-ts/Ord'

const OrdNumber: Ord<number> = fromCompare((first, second) =>
  first < second ? -1 : first > second ? 1 : 0
)

Quiz. Is it possible to define an Ord instance for the game Rock-Paper-Scissor where move1 <= move2 if move2 beats move1?

Let's see a practical usage of an Ord instance by defining a sort function which orders the elements of a ReadonlyArray.

import { pipe } from 'fp-ts/function'
import * as N from 'fp-ts/number'
import { Ord } from 'fp-ts/Ord'

export const sort = <A>(O: Ord<A>) => (
  as: ReadonlyArray<A>
): ReadonlyArray<A> => as.slice().sort(O.compare)

pipe([3, 1, 2], sort(N.Ord), console.log) // => [1, 2, 3]

Quiz (JavaScript). Why does the implementation leverages the native Array slice method?

Let's see another Ord pratical usage by defining a min function that returns the smallest of two values:

import { pipe } from 'fp-ts/function'
import * as N from 'fp-ts/number'
import { Ord } from 'fp-ts/Ord'

const min = <A>(O: Ord<A>) => (second: A) => (first: A): A =>
  O.compare(first, second) === 1 ? second : first

pipe(2, min(N.Ord)(1), console.log) // => 1

Dual Ordering

In the same way we could invert the concat operation to obtain the dual semigroup using the reverse combinator, we can invert the compare operation to get the dual ordering.

Let's define the reverse combinator for Ord:

import { pipe } from 'fp-ts/function'
import * as N from 'fp-ts/number'
import { fromCompare, Ord } from 'fp-ts/Ord'

export const reverse = <A>(O: Ord<A>): Ord<A> =>
  fromCompare((first, second) => O.compare(second, first))

A usage example for reverse is obtaining a max function from the min one:

import { flow, pipe } from 'fp-ts/function'
import * as N from 'fp-ts/number'
import { Ord, reverse } from 'fp-ts/Ord'

const min = <A>(O: Ord<A>) => (second: A) => (first: A): A =>
  O.compare(first, second) === 1 ? second : first

// const max: <A>(O: Ord<A>) => (second: A) => (first: A) => A
const max = flow(reverse, min)

pipe(2, max(N.Ord)(1), console.log) // => 2

The totality of ordering (meaning that given any x and y, one of the two conditions needs to hold true: x <= y or y <= z) may appear obvious when speaking about numbers, but that's not always the case. Let's see a slightly more complex scenario:

type User = {
  readonly name: string
  readonly age: number
}

It's not really clear when a User is "smaller or equal" than another User.

How can we define an Ord<User> instance?

That depends on the context, but a possible choice might be ordering Users by their age:

import * as N from 'fp-ts/number'
import { fromCompare, Ord } from 'fp-ts/Ord'

type User = {
  readonly name: string
  readonly age: number
}

const byAge: Ord<User> = fromCompare((first, second) =>
  N.Ord.compare(first.age, second.age)
)

Again we can get rid of some boilerplate using the contramap combinatorL given an Ord<A> instance and a function from B to A, it is possible to derive Ord<B>:

import { pipe } from 'fp-ts/function'
import * as N from 'fp-ts/number'
import { contramap, Ord } from 'fp-ts/Ord'

type User = {
  readonly name: string
  readonly age: number
}

const byAge: Ord<User> = pipe(
  N.Ord,
  contramap((_: User) => _.age)
)

We can get the youngest of two Users using the previously defined min function.

// const getYounger: (second: User) => (first: User) => User
const getYounger = min(byAge)

pipe(
  { name: 'Guido', age: 50 },
  getYounger({ name: 'Giulio', age: 47 }),
  console.log
) // => { name: 'Giulio', age: 47 }

Quiz. In the fp-ts/ReadonlyMap module the following API is exposed:

/**
 * Get a sorted `ReadonlyArray` of the keys contained in a `ReadonlyMap`.
 */
declare const keys: <K>(
  O: Ord<K>
) => <A>(m: ReadonlyMap<K, A>) => ReadonlyArray<K>

why does this API requires an instance for Ord<K>?

Let's finally go back to the very first issue: defining two semigroups SemigroupMin and SemigroupMax for types different than number:

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

const SemigroupMin: Semigroup<number> = {
  concat: (first, second) => Math.min(first, second)
}

const SemigroupMax: Semigroup<number> = {
  concat: (first, second) => Math.max(first, second)
}

Now that we have the Ord abstraction we can do it:

import { pipe } from 'fp-ts/function'
import * as N from 'fp-ts/number'
import { Ord, contramap } from 'fp-ts/Ord'
import { Semigroup } from 'fp-ts/Semigroup'

export const min = <A>(O: Ord<A>): Semigroup<A> => ({
  concat: (first, second) => (O.compare(first, second) === 1 ? second : first)
})

export const max = <A>(O: Ord<A>): Semigroup<A> => ({
  concat: (first, second) => (O.compare(first, second) === 1 ? first : second)
})

type User = {
  readonly name: string
  readonly age: number
}

const byAge: Ord<User> = pipe(
  N.Ord,
  contramap((_: User) => _.age)
)

console.log(
  min(byAge).concat({ name: 'Guido', age: 50 }, { name: 'Giulio', age: 47 })
) // => { name: 'Giulio', age: 47 }
console.log(
  max(byAge).concat({ name: 'Guido', age: 50 }, { name: 'Giulio', age: 47 })
) // => { name: 'Guido', age: 50 }

Example

Let's recap all of this with one final example (adapted from Fantas, Eel, and Specification 4: Semigroup).

Suppose we need to build a system where, in a database, there are records of customers implemented in the following way:

interface Customer {
  readonly name: string
  readonly favouriteThings: ReadonlyArray<string>
  readonly registeredAt: number // since epoch
  readonly lastUpdatedAt: number // since epoch
  readonly hasMadePurchase: boolean
}

For some reason, there might be duplicate records for the same person.

We need a merging strategy. Well, that's Semigroup's bread and butter!

import * as B from 'fp-ts/boolean'
import { pipe } from 'fp-ts/function'
import * as N from 'fp-ts/number'
import { contramap } from 'fp-ts/Ord'
import * as RA from 'fp-ts/ReadonlyArray'
import { max, min, Semigroup, struct } from 'fp-ts/Semigroup'
import * as S from 'fp-ts/string'

interface Customer {
  readonly name: string
  readonly favouriteThings: ReadonlyArray<string>
  readonly registeredAt: number // since epoch
  readonly lastUpdatedAt: number // since epoch
  readonly hasMadePurchase: boolean
}

const SemigroupCustomer: Semigroup<Customer> = struct({
  // keep the longer name
  name: max(pipe(N.Ord, contramap(S.size))),
  // accumulate things
  favouriteThings: RA.getSemigroup<string>(),
  // keep the least recent date
  registeredAt: min(N.Ord),
  // keep the most recent date
  lastUpdatedAt: max(N.Ord),
  // boolean semigroup under disjunction
  hasMadePurchase: B.SemigroupAny
})

console.log(
  SemigroupCustomer.concat(
    {
      name: 'Giulio',
      favouriteThings: ['math', 'climbing'],
      registeredAt: new Date(2018, 1, 20).getTime(),
      lastUpdatedAt: new Date(2018, 2, 18).getTime(),
      hasMadePurchase: false
    },
    {
      name: 'Giulio Canti',
      favouriteThings: ['functional programming'],
      registeredAt: new Date(2018, 1, 22).getTime(),
      lastUpdatedAt: new Date(2018, 2, 9).getTime(),
      hasMadePurchase: true
    }
  )
)
/*
{ name: 'Giulio Canti',
  favouriteThings: [ 'math', 'climbing', 'functional programming' ],
  registeredAt: 1519081200000, // new Date(2018, 1, 20).getTime()
  lastUpdatedAt: 1521327600000, // new Date(2018, 2, 18).getTime()
  hasMadePurchase: true
}
*/

Quiz. Given a type A is it possible to define a Semigroup<Ord<A>> instance? What could it possibly represent?

Demo

Modeling composition through Monoids

Let's recap what we have seen till now.

We have seen how an algebra is a combination of:

• some type A
• some operations involving the type A
• some laws and properties for that combination.

The first algebra we have seen has been the magma, an algebra defined on some type A equipped with one operation called concat. There were no laws involved in Magma<A> the only requirement we had was that the concat operation had to be closed on A meaning that the result:

concat(first: A, second: A) => A

has still to be an element of the A type.

Later on we have seen how adding one simple requirement, associativity, allowed some Magma<A> to be further refined as a Semigroup<A>, and how associativity captures the possibility of computations to be parallelized.

Now we're going to add another condition on Semigroup.

Given a Semigroup defined on some set A with some concat operation, if there is some element in A – we'll call this element empty – such as for every element a in A the two following equations hold true:

• Right identity: concat(a, empty) = a
• Left identity: concat(empty, a) = a

then the Semigroup is also a Monoid.

Note: We'll call the empty element unit for the rest of this section. There's other synonyms in literature, some of the most common ones are neutral element and identity element.

We have seen how in TypeScript Magmas and Semigroups, can be modeled with interfaces, so it should not come as a surprise that the very same can be done for Monoids.

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

interface Monoid<A> extends Semigroup<A> {
  readonly empty: A
}

Many of the semigroups we have seen in the previous sections can be extended to become Monoids. All we need to find is some element of type A for which the Right and Left identities hold true.

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

/** number `Monoid` under addition */
const MonoidSum: Monoid<number> = {
  concat: (first, second) => first + second,
  empty: 0
}

/** number `Monoid` under multiplication */
const MonoidProduct: Monoid<number> = {
  concat: (first, second) => first * second,
  empty: 1
}

const MonoidString: Monoid<string> = {
  concat: (first, second) => first + second,
  empty: ''
}

/** boolean monoid under conjunction */
const MonoidAll: Monoid<boolean> = {
  concat: (first, second) => first && second,
  empty: true
}

/** boolean monoid under disjunction */
const MonoidAny: Monoid<boolean> = {
  concat: (first, second) => first || second,
  empty: false
}

Quiz. In the semigroup section we have seen how the type ReadonlyArray<string> admits a Semigroup instance:

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

const Semigroup: Semigroup<ReadonlyArray<string>> = {
  concat: (first, second) => first.concat(second)
}

Can you find the unit for this semigroup? If so, can we generalize the result not just for ReadonlyArray<string> but ReadonlyArray<A> as well?

Quiz (more complex). Prove that given a monoid, there can only be one unit.

The consequence of the previous proof is that there can be only one unit per monoid, once we find one we can stop searching.

We have seen how each semigroup was a magma, but not every magma was a semigroup. In the same way, each monoid is a semigroup, but not every semigroup is a monoid.

Example

Let's consider the following example:

import { pipe } from 'fp-ts/function'
import { intercalate } from 'fp-ts/Semigroup'
import * as S from 'fp-ts/string'

const SemigroupIntercalate = pipe(S.Semigroup, intercalate('|'))

console.log(S.Semigroup.concat('a', 'b')) // => 'ab'
console.log(SemigroupIntercalate.concat('a', 'b')) // => 'a|b'
console.log(SemigroupIntercalate.concat('a', '')) // => 'a|'

Note how for this Semigroup there's no such empty value of type string such as concat(a, empty) = a.

And now one final, slightly more "exotic" example, involving functions:

Example

An endomorphism is a function whose input and output type is the same:

type Endomorphism<A> = (a: A) => A

Given a type A, all endomorphisms defined on A are a monoid, such as:

• the concat operation is the usual function composition
• the unit, our empty value is the identity function

import { Endomorphism, flow, identity } from 'fp-ts/function'
import { Monoid } from 'fp-ts/Monoid'

export const getEndomorphismMonoid = <A>(): Monoid<Endomorphism<A>> => ({
  concat: flow,
  empty: identity
})

Note: The identity function has one, and only one possible implementation:

const identity = (a: A) => a

Whatever value we pass in input, it gives us the same value in output.

The concatAll function

One great property of monoids, compared to semigrops, is that the concatenation of multiple elements becomes even easier: it is not necessary anymore to provide an initial value.

import { concatAll } from 'fp-ts/Monoid'
import * as S from 'fp-ts/string'
import * as N from 'fp-ts/number'
import * as B from 'fp-ts/boolean'

console.log(concatAll(N.MonoidSum)([1, 2, 3, 4])) // => 10
console.log(concatAll(N.MonoidProduct)([1, 2, 3, 4])) // => 24
console.log(concatAll(S.Monoid)(['a', 'b', 'c'])) // => 'abc'
console.log(concatAll(B.MonoidAll)([true, false, true])) // => false
console.log(concatAll(B.MonoidAny)([true, false, true])) // => true

Quiz. Why is the initial value not needed anymore?

Product monoid

As we have already seen with semigroups, it is possible to define a monoid instance for a struct if we are able to define a monoid instance for each of its fields.

Example

import { Monoid, struct } from 'fp-ts/Monoid'
import * as N from 'fp-ts/number'

type Point = {
  readonly x: number
  readonly y: number
}

const Monoid: Monoid<Point> = struct({
  x: N.MonoidSum,
  y: N.MonoidSum
})

Note. There is a combinator similar to struct that works with tuples: tuple.

import { Monoid, tuple } from 'fp-ts/Monoid'
import * as N from 'fp-ts/number'

type Point = readonly [number, number]

const Monoid: Monoid<Point> = tuple(N.MonoidSum, N.MonoidSum)

Quiz. Is it possible to define a "free monoid" for a generic type A?

Demo (implementing a system to draw geoetric shapes on canvas)

03_shapes.ts

Pure and partial functions

In the first chapter we've seen an informal definition of a pure function:

A pure function is a procedure that given the same input always returns the same output and does not have any observable side effect.

Such an informal statement could leave space for some doubts, such as:

• what is a "side effect"?
• what does it means "observable"?
• what does it mean "same"?

Let's see a formal definition of the concept of a function.

Note. If X and Y are sets, then with X × Y we indicate their cartesian product, meaning the set

X × Y = { (x, y) | x ∈ X, y ∈ Y }

The following definition was given a century ago:

Definition. A _function: f: X ⟶ Y is a subset of X × Y such as for every x ∈ X there's exactly one y ∈ Y such that (x, y) ∈ f.

The set X is called the domain of f, Y is it's codomain.

Example

The function double: Nat ⟶ Nat is the subset of the cartesian product Nat × Nat given by { (1, 2), (2, 4), (3, 6), ...}.

In TypeScript we could define f as

const f: Record<number, number> = {
  1: 2,
  2: 4,
  3: 6
  ...
}

The one in the example is called an extensional definition of a function, meaning we enumerate one by one each of the elements of its domain and for each one of them we point the corresponding codomain element.

Naturally, when such a set is infinite this proves to be problematic. We can't list the entire domain and codomain of all functions.

We can get around this issue by introducing the one that is called intensional definition, meaning that we express a condition that has to hold for every couple (x, y) ∈ f meaning y = x * 2.

This the familiar form in which we write the double function and its definition in TypeScript:

const double = (x: number): number => x * 2

The definition of a function as a subset of a cartesian product shows how in mathematics every function is pure: there is no action, no state mutation or elements being modified. In functional programming the implementation of functions has to follow as much as possible this ideal model.

Quiz. Which of the following procedures are pure functions?

const coefficient1 = 2
export const f1 = (n: number) => n * coefficient1

// ------------------------------------------------------

let coefficient2 = 2
export const f2 = (n: number) => n * coefficient2++

// ------------------------------------------------------

let coefficient3 = 2
export const f3 = (n: number) => n * coefficient3

// ------------------------------------------------------

export const f4 = (n: number) => {
  const out = n * 2
  console.log(out)
  return out
}

// ------------------------------------------------------

interface User {
  readonly id: number
  readonly name: string
}

export declare const f5: (id: number) => Promise<User>

// ------------------------------------------------------

import * as fs from 'fs'

export const f6 = (path: string): string =>
  fs.readFileSync(path, { encoding: 'utf8' })

// ------------------------------------------------------

export const f7 = (
  path: string,
  callback: (err: Error | null, data: string) => void
): void => fs.readFile(path, { encoding: 'utf8' }, callback)

The fact that a function is pure does not imply automatically a ban on local mutability as long as it doesn't leaks out of its scope.

Example (Implementazion details of the concatAll function for monoids)

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

const concatAll = <A>(M: Monoid<A>) => (as: ReadonlyArray<A>): A => {
  let out: A = M.empty // <= local mutability
  for (const a of as) {
    out = M.concat(out, a)
  }
  return out
}

The ultimate goal is to guarantee: referential transparency.

The contract we sign with a user of our APIs is defined by the APIs signature:

declare const concatAll: <A>(M: Monoid<A>) => (as: ReadonlyArray<A>) => A

and by the promise of respecting referential transparency. The technical details of how the function is implemented are not relevant, thus there is maximum freedom implementation-wise.

Thus, how do we define a "side effect"? Simply by negating referential transparency:

An expression contains "side effects" if it doesn't benefit from referential transparency

Not only functions are a perfect example of one of the two pillars of functional programming, referential transparency, but they're also examples of the second pillar: composition.

Functions compose:

Definition. Given f: Y ⟶ Z and g: X ⟶ Y two functions, then the function h: X ⟶ Z defined by:

h(x) = f(g(x))

is called composition of f and g and is written h = f ∘ g

Please note that in order for f and g to combine, the domain of f has to be included in the codomain of g.

Definition. A function is said to be partial if it is not defined for each value of its domain.

Vice versa, a function defined for all values of its domain is said to be total

Example

f(x) = 1 / x

The function f: number ⟶ number is not defined for x = 0.

Example

// Get the first element of a `ReadonlyArray`
declare const head: <A>(as: ReadonlyArray<A>) => A

Quiz. Why is the head function partial?

Quiz. Is JSON.parse a total function?

parse: (text: string, reviver?: (this: any, key: string, value: any) => any) =>
  any

Quiz. Is JSON.stringify a total function?

stringify: (
  value: any,
  replacer?: (this: any, key: string, value: any) => any,
  space?: string | number
) => string

In functional programming there is a tendency to only define pure and total functions. From now on with the term function we'll be specifically referring to "pure and total function". So what do we do when we have a partial function in our applications?

A partial function f: X ⟶ Y can always be "brought back" to a total one by adding a special value, let's call it None, to the codomain and by assigning it to the output of f for every value of X where the function is not defined.

f': X ⟶ Y ∪ None

Let's call it Option(Y) = Y ∪ None.

f': X ⟶ Option(Y)

In functional programming the tendency is to define only pure and and total functions.

Is it possible to define Option in TypeScript? In the following chapters we'll see how to do it.

Algebraic Data Types

A good first step when writing an application or feature is to define it's domain model. TypeScript offers many tools that help accomplishing this task. Algebraic Data Types (in short, ADTs) are one of these tools.

What is an ADT?

In computer programming, especially functional programming and type theory, an algebraic data type is a kind of composite type, i.e., a type formed by combining other types.

Two common families of algebraic data types are:

• product types
• sum types

Let's begin with the more familiar ones: product types.

Product types

A product type is a collection of types T_i indexed by a set I.

Two members of this family are n-tuples, where I is an interval of natural numbers:

type Tuple1 = [string] // I = [0]
type Tuple2 = [string, number] // I = [0, 1]
type Tuple3 = [string, number, boolean] // I = [0, 1, 2]

// Accessing by index
type Fst = Tuple2[0] // string
type Snd = Tuple2[1] // number

and structs, where I is a set of labels:

// I = {"name", "age"}
interface Person {
  name: string
  age: number
}

// Accessing by label
type Name = Person['name'] // string
type Age = Person['age'] // number

Product types can be polimorphic.

Example

//                ↓ type parameter
type HttpResponse<A> = {
  readonly code: number
  readonly body: A
}

Why "product" types?

If we label with C(A) the number of elements of type A (also called in mathematics, cardinality), then the following equation hold true:

C([A, B]) = C(A) * C(B)

the cardinality of a product is the product of the cardinalities

Example

The null type has cardinality 1 because it has only one member: null.

Quiz: What is the cardinality of the boolean type.

Example

type Hour = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
type Period = 'AM' | 'PM'
type Clock = [Hour, Period]

Type Hour has 12 members. Type Period has 2 members. Thus type Clock has 12 * 2 = 24 elements.

Quiz: What is the cardinality of the following Clock type?

// same as before
type Hour = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
// same as before
type Period = 'AM' | 'PM'

// different encoding, no longer a Tuple
type Clock = {
  readonly hour: Hour
  readonly period: Period
}

When can I use a product type?

Each time it's components are independent.

type Clock = [Hour, Period]

Here Hour and Period are independent: the value of Hour does not change the value of Period. Every legal pair of [Hour, Period] makes "sense" and is legal.

Sum types

A sum type is a a data type that can hold a value of different (but limited) types. Only one of these types can be used in a single instance and there is generally a "tag" value differentiating those types.

In TypeScript's official docs they are called discriminated union.

It is important to note that the members of the union have to be disjoint, there can't be values that belong to more than one member.

Example

The type:

type StringsOrNumbers = ReadonlyArray<string> | ReadonlyArray<number>

declare const sn: StringsOrNumbers

sn.map() // error: This expression is not callable.

is not a disjoint union because the value [], the empty array, belongs to both members.

Quiz. Is the following union disjoint?

type Member1 = { readonly a: string }
type Member2 = { readonly b: number }
type MyUnion = Member1 | Member2

Disjoint unions are recurring in functional programming.

Fortunately TypeScript has a way to guarantee that a union is disjoint: add a specific field that works as a tag.

Note: Disjoint unions, sum types and tagged unions are used interchangeably to indicate the same thing.

Example (redux actions)

The Action sum type models a portion of the operation that the user can take i a todo app.

type Action =
  | {
      type: 'ADD_TODO'
      text: string
    }
  | {
      type: 'UPDATE_TODO'
      id: number
      text: string
      completed: boolean
    }
  | {
      type: 'DELETE_TODO'
      id: number
    }

The type tag makes sure every member of the union is disjointed.

Note. The name of the field that acts as a tag is chosen by the developer. It doesn't have to be "type". In fp-ts the convention is to use a _tag field.

Now that we've seen few examples we can define more explicitly what algebraic data types are:

In general, an algebraic data type specifies a sum of one or more alternatives, where each alternative is a product of zero or more fields.

Sum types can be polymorphic and recursive.

Example (linked list)

//               ↓ type parameter
export type List<A> =
  | { readonly _tag: 'Nil' }
  | { readonly _tag: 'Cons'; readonly head: A; readonly tail: List<A> }
//                                                              ↑ recursion

Quiz (TypeScript). Which of the following data types is a product or a sum type?

• ReadonlyArray<A>
• Record<string, A>
• Record<'k1' | 'k2', A>
• ReadonlyMap<string, A>
• ReadonlyMap<'k1' | 'k2', A>

Constructors

A sum type with n elements needs at least n constructors, one for each member:

Example (redux action creators)

export type Action =
  | {
      readonly type: 'ADD_TODO'
      readonly text: string
    }
  | {
      readonly type: 'UPDATE_TODO'
      readonly id: number
      readonly text: string
      readonly completed: boolean
    }
  | {
      readonly type: 'DELETE_TODO'
      readonly id: number
    }

export const add = (text: string): Action => ({
  type: 'ADD_TODO',
  text
})

export const update = (
  id: number,
  text: string,
  completed: boolean
): Action => ({
  type: 'UPDATE_TODO',
  id,
  text,
  completed
})

export const del = (id: number): Action => ({
  type: 'DELETE_TODO',
  id
})

Example (TypeScript, linked lists)

export type List<A> =
  | { readonly _tag: 'Nil' }
  | { readonly _tag: 'Cons'; readonly head: A; readonly tail: List<A> }

// a nullary constructor can be implemented as a constant
export const nil: List<never> = { _tag: 'Nil' }

export const cons = <A>(head: A, tail: List<A>): List<A> => ({
  _tag: 'Cons',
  head,
  tail
})

// equivalent to an array containing [1, 2, 3]
const myList = cons(1, cons(2, cons(3, nil)))

Pattern matching

JavaScript doesn't support pattern matching (neither does TypeScript) but we can simulate it with a match function.

Example (TypeScript, linked lists)

interface Nil {
  readonly _tag: 'Nil'
}

interface Cons<A> {
  readonly _tag: 'Cons'
  readonly head: A
  readonly tail: List<A>
}

export type List<A> = Nil | Cons<A>

export const match = <R, A>(
  onNil: () => R,
  onCons: (head: A, tail: List<A>) => R
) => (fa: List<A>): R => {
  switch (fa._tag) {
    case 'Nil':
      return onNil()
    case 'Cons':
      return onCons(fa.head, fa.tail)
  }
}

// returns `true` if the list is empty
export const isEmpty = match(
  () => true,
  () => false
)

// returns the first element of the list or `undefined`
export const head = match(
  () => undefined,
  (head, _tail) => head
)

// returns the length of the list, recursively
export const length: <A>(fa: List<A>) => number = match(
  () => 0,
  (_, tail) => 1 + length(tail)
)

Quiz. Why's the head API sub optimal?

-> See the answer here

Note. TypeScript offers a great feature for sum types: exhaustive check. The type checker can check, no pun intended, whether all the possible cases are handled by the switch defined in the body of the function.

Why "sum" types?

Because the following identity holds true:

C(A | B) = C(A) + C(B)

The sum of the cardinality is the sum of the cardinalities

Example (the Option type)

interface None {
  readonly _tag: 'None'
}

interface Some<A> {
  readonly _tag: 'Some'
  readonly value: A
}

type Option<A> = None | Some<A>

From the general formula C(Option<A>) = 1 + C(A) we can derive the cardinality of the Option<boolean> type: 1 + 2 = 3 members.

When should I use a sum type?

When the components would be dependent if implemented with a product type.

Example (React props)

import * as React from 'react'

interface Props {
  readonly editable: boolean
  readonly onChange?: (text: string) => void
}

class Textbox extends React.Component<Props> {
  render() {
    if (this.props.editable) {
      // error: Cannot invoke an object which is possibly 'undefined' :(
      this.props.onChange('a')
    }
    return <div />
  }
}

The problem here is that Props is modeled like a product, but onChange depends on editable.

A sum type fits the use case better:

import * as React from 'react'

type Props =
  | {
      readonly type: 'READONLY'
    }
  | {
      readonly type: 'EDITABLE'
      readonly onChange: (text: string) => void
    }

class Textbox extends React.Component<Props> {
  render() {
    switch (this.props.type) {
      case 'EDITABLE':
        this.props.onChange('a') // :)
    }
    return <div />
  }
}

Example (node callbacks)

declare function readFile(
  path: string,
  //         ↓ ---------- ↓ CallbackArgs
  callback: (err?: Error, data?: string) => void
): void

The result of the readFile operation is modeled like a product type (to be more precise, as a tuple) which is later on passed to the callback function:

type CallbackArgs = [Error | undefined, string | undefined]

the callback components though are dependent: we either get an Error or a string:

This API is clearly not modeled on the following premise:

Make impossible state unrepresentable

A sum type would've been a better choice, but which sum type? We'll see how to handle errors in a functional way.

Quiz. Recently API's based on callbacks have been largely replaced by their Promise equivalents.

declare function readFile(path: string): Promise<string>

Can you find some cons of the Promise solution when using static typing like in TypeScript?

Functional error handling

Let's see how to handle errors in a functional way.

A function that throws exceptions is an example of a partial function.

In the previous chapters we have seen that every partial function f can always be brought back to a total one f'.

f': X ⟶ Option(Y)

Now that we know a bit more about sum types in TypeScript we can define the Option without much issues.

The Option type

The type Option represents the effect of a computation which may fail (case None) or return a type A (case Some<A>):

// represents a failure
interface None {
  readonly _tag: 'None'
}

// represents a success
interface Some<A> {
  readonly _tag: 'Some'
  readonly value: A
}

type Option<A> = None | Some<A>

Constructors and pattern matching:

const none: Option<never> = { _tag: 'None' }

const some = <A>(value: A): Option<A> => ({ _tag: 'Some', value })

const match = <R, A>(onNone: () => R, onSome: (a: A) => R) => (
  fa: Option<A>
): R => {
  switch (fa._tag) {
    case 'None':
      return onNone()
    case 'Some':
      return onSome(fa.value)
  }
}

The Option type can be used to avoid throwing exceptions or representing the optional values, thus we can move from:

//                        this is a lie ↓
const head = <A>(as: ReadonlyArray<A>): A => {
  if (as.length === 0) {
    throw new Error('Empty array')
  }
  return as[0]
}

let s: string
try {
  s = String(head([]))
} catch (e) {
  s = e.message
}

where the type system is ignorant about the possibility of failure, to:

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

//                                      ↓ the type system "knows" that this computation may fail
const head = <A>(as: ReadonlyArray<A>): Option<A> =>
  as.length === 0 ? none : some(as[0])

declare const numbers: ReadonlyArray<number>

const result = pipe(
  head(numbers),
  match(
    () => 'Empty array',
    (n) => String(n)
  )
)

where the possibility of an error is encoded in the type system.

If we attempt to access the value property of an Option without checking in which case we are, the type system will warn us about the possibility of getting an error:

declare const numbers: ReadonlyArray<number>

const result = head(numbers)
result.value // type checker error: Property 'value' does not exist on type 'Option<number>'

The only way to access the value contained in an Option is to handle also the failure case using the match function.

pipe(result, match(
  () => ...handle error...
  (n) => ...go on with my business logic...
))

Is it possible to define instances for the abstractions we've seen in the chapters before? Let's begin with Eq.

An Eq instance

Suppose we have two values of type Option<string> and that we want to compare them to check if their equal:

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

declare const o1: Option<string>
declare const o2: Option<string>

const result: boolean = pipe(
  o1,
  match(
    // onNone o1
    () =>
      pipe(
        o2,
        match(
          // onNone o2
          () => true,
          // onSome o2
          () => false
        )
      ),
    // onSome o1
    (s1) =>
      pipe(
        o2,
        match(
          // onNone o2
          () => false,
          // onSome o2
          (s2) => s1 === s2 // <= qui uso l'uguaglianza tra stringhe
        )
      )
  )
)

What if we had two values of type Option<number>? It would be pretty annoying to write the same code we just wrote above, the only difference afterall would be how we compare the two values contained in the Option.

Thus we can generalize the necessary code by requiring the user to provide an Eq instance for A and then derive an Eq instance for Option<A>.

In other words we can define a combinator getEq: given an Eq<A> this combinator will return an Eq<Option<A>>:

import { Eq } from 'fp-ts/Eq'
import { pipe } from 'fp-ts/function'
import { match, Option, none, some } from 'fp-ts/Option'

export const getEq = <A>(E: Eq<A>): Eq<Option<A>> => ({
  equals: (first, second) =>
    pipe(
      first,
      match(
        () =>
          pipe(
            second,
            match(
              () => true,
              () => false
            )
          ),
        (a1) =>
          pipe(
            second,
            match(
              () => false,
              (a2) => E.equals(a1, a2) // <= here I use the `A` equality
            )
          )
      )
    )
})

import * as S from 'fp-ts/string'

const EqOptionString = getEq(S.Eq)

console.log(EqOptionString.equals(none, none)) // => true
console.log(EqOptionString.equals(none, some('b'))) // => false
console.log(EqOptionString.equals(some('a'), none)) // => false
console.log(EqOptionString.equals(some('a'), some('b'))) // => false
console.log(EqOptionString.equals(some('a'), some('a'))) // => true