Functional programming is infamously known for its cryptic math-like jargon: terms like monads, monoids, functors and isomorphisms seem to be very intimidating for inexperienced developers. But if we take a look at those concepts as programming patterns, everything becomes much clearer. Let’s take a look at those terms which you may encounter when using FP libraries like fp-ts, effect-ts or sanctuary, and code examples which illustrate them.

Algebraic Data Type (ADT)

We start with algebraic data types. A data type is called algebraic if it’s composed of product types (interfaces in TypeScript terminology) and sum types (unions, enumerations). Here’s an example of a small ADT:

// Product types — interfaces:
interface Nothing {
  readonly tag: 'Nothing';
}

interface Just<T> {
  readonly tag: 'Just';
  readonly value: T;
}

// Sum type — union:
type Maybe<T> = Nothing | Just<T>;

Algebraic data types got their name due to their mathematical properties, and it relates to counting type inhabitants. Product types — interfaces, or records, — got their name because the number of possible type inhabitants is equal to the product of inhabitants of each field. Say, type { foo: boolean, bar: boolean | null } will have a number of its inhabitants equal to 6 — 2 for foo times 3 for bar. The number of inhabitants for sum types, as you probably have already guessed, is equal to the sum of inhabitants for each union member. Type boolean | null will have exactly 3 inhabitants: 2 for boolean plus 1 for null.

These properties preserve even further. Here’s a riddle for you: can you guess which data type corresponds to an exponent A^B?

Algebraic data types are the core tool of data modelling. The ultimate goal of data modelling in FP is to write so precise types that it’s impossible to construct bad data. This is known as the principle of making illegal states unrepresentable, and I talked about it in my previous article.

Laws

A special term you will encounter quite often is law. Law is a special property which should hold for some type. For example, Array.prototype.reverse should hold a “double application identity law”: arr.reverse().reverse() should be structurally equal to just arr, i.e. all elements should return to their places after a second reverse.

When you write your own functional structures and want to test that it holds some laws, it is good to use some property-based testing library to test your program on myriad of randomised inputs — for free! Are you interested in learning more about this kind of testing? Then keep an eye on this blog! ;-)

Domain and codomain of a function

A domain of a function is a type of its argument. A codomain, correspondingly, is a type of its result. An example: for f: (x: number) => string its domain will be number, and its codomain will be string.

Injection, surjection, bijection

These terms are rate, but they are tightly tied to the terms “domain” and “codomain”, and you still can meet them in some discussions, so I decided to showcase them as well.

A function is injective if each of the elements from its domain is uniquely mapped to an element from its codomain. To put it simply, if no two elements from the domain are mapped to the same element from the codomain, then the function is injective (or “is an injection”):

const injection = (x: number): string => x.toString(); // no different two numbers are mapped to a same string

const notInjection = (x: number): number => Math.abs(x); // e.g., both 2 and -2 are mapped to 2

A function is surjective if it fully covers all possible values of its codomain, i.e. there’s no such x that f(x) is not defined:

const surjection = (x: number): number => x * x; // for each and every `x` there exists `x²`

Finally, a function which is injective and surjective simultaneously is called a bijection (or “is bijective”). It is also known as “one-to-one correspondence” or “invertible function”. We will meet such functions in this text — can you find them?

What are String.prototype.toUpperCase and String.prototype.toLowerCase: injective, surjective, bijective, something else?

Morphism, endomorphism, isomorphism

A morphism is a term originated from Category Theory and applied to programming it means… just a function:

type Morphism<A, B> = (a: A) => B;

A special case of morphisms you may encounter is called endomorphism. It’s a function from some type back to that exact type:

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

If you immediately thought of identity function, you are correct, but it’s just a particular example of endomorphism. Functions like String.prototype.toUpperCase, or Array.prototype.reverse are examples of endomorphisms as well.

You may also meet the term “isomorphism”, or the phrase “X isomorphic to Y”. An isomorphism is a function which has a reverse operation. In TypeScript, isomorphism is usually modelled using a pair of functions, which hold together a law of information preserving:

interface Isomorphism<A, B> {
  readonly to: (a: A) => B;
  readonly from: (b: B) => A;
}

// Law 1: `to(from(x))` is the same as `identity(x)` — or just `x`.
// Law 2: `from(to(x))` is the same as `identity(x)` — or just `x`, as well.

When you hear that “X isomorphic to Y”, you can translate this as “X is reversibly transformable into Y, and vice versa”. One of the core principles of isomorphism — it should not lose any information.

An exercise for the curious ones: can functions String.toLowerCase and String.toUpperCase form an isomorphism? What about Date.prototype.toISOString and new Date constructor?

Natural transformation

A natural transformation can be thought of as a function which can replace type constructors, and this time we will need to get some help from fp-ts and its notation of higher-order types. Please refer to this article to get a better understanding of how higher-order and higher-kinded types are implemented. The definition of a natural transformation can be written like this:

type NaturalTransformation<F, G> = <A>(fx: HKT<F, A>) => HKT<G, A>;

// or in imaginary "TypeScript with kinds" syntax:

type NaturalTransformation<F, G> = (fx: F<_>) => G<_>;

Let take a look at some examples. We can create a natural transformation between an array and a set:

const arrayToSet = <A>(arr: Array<A>): Set<A> => new Set(arr);

Note that arrayToSet will replace the type of container, but leave the type of content intact.

A fun example: define an isomorphism between some arbitrary type T and its lazy representation Lazy<T>, where type Lazy<A> = () => A. What if we swap the direction — can you define an isomorphism between Lazy<T> and T?

Another important note: our arrayToSet implementation will lose data, but note that the definition of a natural transformation said nothing about information preserving! But if we insist on adding a law of information preserving, we will eventually arrive at the definition of a natural isomorphism — a reversible transformation between two type constructors:

interface NaturalIsomorphism<F, G> {
  readonly to: <A>(fx: HKT<F, A>) => HKT<G, A>;
  readonly from: <A>(fx: HKT<G, A>) => HKT<F, A>;
}

const arrayMapIsomorphism: NaturalIsomorphism<'Array', 'Map'> = {
  to: <A>(arr: Array<A>): Map<number, A> => new Map(arr.map((el, idx) => [idx, el])),
  from: <A>(map: Map<number, A>): Array<A> => Array.from(map.values()),
};

Can you write a natural isomorphism between an Array and a Set? Which laws can you come up with for it?

Functor

A functor is also a term from Category Theory, and it means “structure-preserving mapping”. Imagine Array.prototype.map function, or its equivalent for Map or Tree, plus add some laws, and you get yourself a functor! We cannot define a generic functor in pure TypeScript, but thanks to HKT notation of fp-ts we can write this definition:

interface Functor<F> {
  readonly map: <A, B>(f: (a: A) => B) => (fa: HKT<F, A>) => HKT<F, B>;

  // Law 1: `pipe(fa, map(identity))` is equal to just `fa`
  // Law 2: `pipe(fa, map(f), map(g))` is equal to `pipe(fa, map(compose(f, g)))`
}

N.B.: I intentionally simplify these examples, because in fp-ts the Functor interface is defined for types of higher kinds — from 1-parameteric to 4-parametric, named Functor1 to Functor4, correspondingly, plus one numberless which operates on HKT and not KindX. My examples show only interfaces with HKT to declutter the code.

For a higher-order type — like our Maybe example from the ADT section up above — we usually can define a functor:

// First we need to show fp-ts that Maybe is higher-order type:

declare 'fp-ts/HKT' {
  interface URItoKind<A> {
    readonly Maybe: Maybe<A>;
  }
}

const maybeFunctor: Functor<'Maybe'> = {
  map: <A, B>(f: (a: A) => B) => (maybeA: Maybe<A>): Maybe<B> => {
    switch (maybeA.tag) {
      case 'Nothing': return { tag: 'Nothing' };
      case 'Some':    return { tag: 'Some', value: f(maybeA.value) };
    }
  }
};

// Usage examples:

const someX: Maybe<number> = { tag: 'Some', value: 20 };
const someY: Maybe<number> = { tag: 'Nothing' };

const stringifyX = pipe(someX, maybeFunctor.map(n => n.toString())); // => { tag: 'Some', value: '20' }
const stringifyY = pipe(someY, maybeFunctor.map(n => n.toString())); // => { tag: 'Nothing' }

A functor is an example of a type class. I’ve talked about what is it and how to define them in this article — check it out!

This is the first article of the series. In the next instalment, we will get familiar with more complex terms — magmas, semigroups, monoids, rings and much more, so stay tuned!