Category Theory Fundamentals

This lecture introduces the mathematical foundations of functional programming through category theory.

“Category theory is the mathematics of composition: it explains why map, flatMap, and function composition work together so beautifully. Understanding the laws reveals that functional programming isn’t arbitrary—it’s fundamentally correct.” - AI Insight

What is Category Theory?

Category theory is like a universal language for understanding how things relate to each other. In programming, it helps us understand how functions, types, and data structures work together. Think of it as the “grammar” that explains why functional programming patterns work the way they do. It’s the mathematical foundation that makes functional programming so powerful and predictable.

Basic Concepts

Objects and Morphisms

In category theory, objects are like nouns (the things) and morphisms are like verbs (the actions). In programming, objects are types (like strings, numbers, arrays) and morphisms are functions that transform one type into another. This gives us a way to think about all the different kinds of data transformations in a unified way.

// A function is a morphism from an input type to an output type.
type Morphism<A, B> = (value: A) => B;

const stringLength: Morphism<string, number> = (value) => value.length;

Identity Morphism

Every object has an identity morphism - a function that does nothing, like a “do nothing” button. It’s like the number 1 in multiplication: multiplying by 1 doesn’t change anything. The identity function takes a value and returns it unchanged. This might seem trivial, but it’s essential for the mathematical structure to work properly.

const identity = <A>(value: A): A => value;

const compose = <A, B, C>(
  outer: Morphism<B, C>,
  inner: Morphism<A, B>
): Morphism<A, C> => (value) => outer(inner(value));

type Equal<A> = (left: A, right: A) => boolean;

const leftIdentity = <A, B>(
  f: Morphism<A, B>,
  value: A,
  equals: Equal<B>
): boolean => equals(identity(f(value)), f(value));

const rightIdentity = <A, B>(
  f: Morphism<A, B>,
  value: A,
  equals: Equal<B>
): boolean => equals(f(identity(value)), f(value));

Composition

Composition is like connecting pipes - you can take the output of one function and feed it into another function. The associativity law says that the order in which you group your compositions doesn’t matter, just like how (a + b) + c = a + (b + c) in addition. This ensures that function composition works predictably no matter how you organize it.

const associativity = <A, B, C, D>(
  f: Morphism<C, D>,
  g: Morphism<B, C>,
  h: Morphism<A, B>,
  value: A,
  equals: Equal<D>
): boolean => {
  const leftGrouped = compose(compose(f, g), h)(value);
  const rightGrouped = compose(f, compose(g, h))(value);
  return equals(leftGrouped, rightGrouped);
};

Functors

“Functors are structure-preserving transformations: map transforms the contents while preserving the container. Arrays, Promises, Maybe—all functors. Understanding functors means understanding why map works the same everywhere.” - AI Insight

Functors are like translators that preserve the structure of what they’re translating. In programming, a functor is something that can be “mapped over” - like arrays, where you can apply a function to every element. Functors maintain the shape and structure of the container while transforming what’s inside.

Functor Laws

Functors follow specific laws that ensure they work predictably. The identity law says that mapping the identity function does not change a value, and the composition law says that one map with a composed function is equivalent to two successive maps.

TypeScript does not natively support applying an arbitrary type parameter as F<A>. Libraries can encode higher-kinded types, but ordinary application code is often clearer when it states the concrete carrier. The following example is therefore a real, compilable Array functor rather than pretend TypeScript syntax.

Array Functor

Arrays are a perfect example of functors in programming. The map function applies a transformation to every element in the array while preserving the array structure. This is why arrays are so powerful for data transformation - they maintain their shape while letting you transform what’s inside.

interface ArrayFunctor {
  map<A, B>(
    values: ReadonlyArray<A>,
    transform: Morphism<A, B>
  ): ReadonlyArray<B>;
}

const arrayFunctor: ArrayFunctor = {
  map: (values, transform) => values.map(transform)
};

const arraysEqual = <A>(
  left: ReadonlyArray<A>,
  right: ReadonlyArray<A>,
  equals: Equal<A>
): boolean => left.length === right.length
  && left.every((value, index) => equals(value, right[index]!));

const arrayFunctorIdentity = <A>(
  values: ReadonlyArray<A>,
  equals: Equal<A>
): boolean => arraysEqual(
  arrayFunctor.map(values, identity),
  values,
  equals
);

const arrayFunctorComposition = <A, B, C>(
  values: ReadonlyArray<A>,
  first: Morphism<A, B>,
  second: Morphism<B, C>,
  equals: Equal<C>
): boolean => arraysEqual(
  arrayFunctor.map(values, compose(second, first)),
  arrayFunctor.map(arrayFunctor.map(values, first), second),
  equals
);

const numbers = [1, 2, 3, 4, 5] as const;
const doubled = arrayFunctor.map(numbers, (value) => value * 2);

console.log(doubled); // [2, 4, 6, 8, 10]
console.log(arrayFunctorIdentity(numbers, Object.is)); // true

Natural Transformations

Natural transformations are bridges between functors that do not inspect or change the element type. For example, maybeToArray consistently converts Just(value) to a one-element array and Nothing to an empty array. Its naturality law says that mapping before conversion has the same result as converting before mapping.

type Maybe<A> =
  | Readonly<{ kind: 'just'; value: A }>
  | Readonly<{ kind: 'nothing' }>;

const nothing: Maybe<never> = { kind: 'nothing' };
const just = <A>(value: A): Maybe<A> => ({ kind: 'just', value });

const mapMaybe = <A, B>(
  maybe: Maybe<A>,
  transform: Morphism<A, B>
): Maybe<B> => maybe.kind === 'nothing'
  ? nothing
  : just(transform(maybe.value));

const maybeToArray = <A>(maybe: Maybe<A>): ReadonlyArray<A> =>
  maybe.kind === 'nothing' ? [] : [maybe.value];

const naturalityHolds = <A, B>(
  maybe: Maybe<A>,
  transform: Morphism<A, B>,
  equals: Equal<B>
): boolean => arraysEqual(
  maybeToArray(mapMaybe(maybe, transform)),
  arrayFunctor.map(maybeToArray(maybe), transform),
  equals
);

Applicative Functors

Between a functor and a monad sits the applicative. A functor maps a plain function over one wrapped value. An applicative applies a wrapped function to a wrapped value, which lets you combine several independent wrapped values with an ordinary multi-argument function.

The distinction from a monad is the one that matters in practice: a monad’s chain makes each step depend on the previous value and short-circuits on the first failure; an applicative’s ap treats its arguments as independent and can therefore run all of them and combine their outcomes.

const apMaybe = <A, B>(
  wrappedFn: Maybe<Morphism<A, B>>,
  wrappedValue: Maybe<A>
): Maybe<B> => wrappedFn.kind === 'nothing' || wrappedValue.kind === 'nothing'
  ? nothing
  : just(wrappedFn.value(wrappedValue.value));

const liftA2Maybe = <A, B, C>(
  combine: (a: A) => (b: B) => C,
  first: Maybe<A>,
  second: Maybe<B>
): Maybe<C> => apMaybe(mapMaybe(first, combine), second);

// Applicative identity law: applying a wrapped identity changes nothing.
const applicativeIdentity = <A>(
  value: Maybe<A>,
  equals: Equal<A>
): boolean => maybeEquals(apMaybe(just(identity), value), value, equals);

Maybe’s applicative still short-circuits (either argument being Nothing yields Nothing), because Maybe carries no error to accumulate. The power of the applicative appears with a carrier that does — a Validation whose ap concatenates error lists. That is the abstraction the monads lecture develops for form and config validation, and its extra behavioral law is that ap accumulates and never short-circuits.

Monadic Unit, Join, and Chain

A monad adds unit (called just here) and join to a functor. join flattens one nested layer, while chain maps a function that returns the same carrier and then flattens. Concrete Maybe code keeps the laws executable without claiming TypeScript has native higher-kinded types.

const joinMaybe = <A>(nested: Maybe<Maybe<A>>): Maybe<A> =>
  nested.kind === 'nothing' ? nothing : nested.value;

const chainMaybe = <A, B>(
  maybe: Maybe<A>,
  next: Morphism<A, Maybe<B>>
): Maybe<B> => joinMaybe(mapMaybe(maybe, next));

const maybeEquals = <A>(
  left: Maybe<A>,
  right: Maybe<A>,
  equals: Equal<A>
): boolean => {
  if (left.kind === 'nothing' || right.kind === 'nothing') {
    return left.kind === right.kind;
  }
  return equals(left.value, right.value);
};

const monadLeftIdentity = <A, B>(
  value: A,
  next: Morphism<A, Maybe<B>>,
  equals: Equal<B>
): boolean => maybeEquals(
  chainMaybe(just(value), next),
  next(value),
  equals
);

const monadRightIdentity = <A>(
  maybe: Maybe<A>,
  equals: Equal<A>
): boolean => maybeEquals(chainMaybe(maybe, just), maybe, equals);

const monadAssociativity = <A, B, C>(
  maybe: Maybe<A>,
  first: Morphism<A, Maybe<B>>,
  second: Morphism<B, Maybe<C>>,
  equals: Equal<C>
): boolean => maybeEquals(
  chainMaybe(chainMaybe(maybe, first), second),
  chainMaybe(maybe, (value) => chainMaybe(first(value), second)),
  equals
);

Monoids

A monoid is the simplest structure in this lecture and one of the most reused: a type with an associative binary operation concat and an identity element empty. It is the algebra of combining many values of one type into one.

interface Monoid<A> {
  readonly empty: A;
  readonly concat: (left: A, right: A) => A;
}

const sumMonoid: Monoid<number> = { empty: 0, concat: (a, b) => a + b };
const stringMonoid: Monoid<string> = { empty: '', concat: (a, b) => a + b };
const arrayMonoid = <A>(): Monoid<ReadonlyArray<A>> => ({
  empty: [],
  concat: (a, b) => [...a, ...b],
});
const allMonoid: Monoid<boolean> = { empty: true, concat: (a, b) => a && b };

Monoid laws

const monoidLeftIdentity = <A>(m: Monoid<A>, value: A, equals: Equal<A>): boolean =>
  equals(m.concat(m.empty, value), value);

const monoidRightIdentity = <A>(m: Monoid<A>, value: A, equals: Equal<A>): boolean =>
  equals(m.concat(value, m.empty), value);

const monoidAssociativity = <A>(
  m: Monoid<A>,
  a: A, b: A, c: A,
  equals: Equal<A>
): boolean =>
  equals(m.concat(m.concat(a, b), c), m.concat(a, m.concat(b, c)));

Associativity is what makes foldMap correct regardless of grouping — and what licenses evaluating a large combination in parallel and merging the partial results:

const foldMap = <A, M>(
  monoid: Monoid<M>,
  transform: Morphism<A, M>,
  values: ReadonlyArray<A>
): M => values.reduce((accumulator, value) =>
  monoid.concat(accumulator, transform(value)), monoid.empty);

const totalLength = foldMap(sumMonoid, (word: string) => word.length, ['fp', 'laws']);
// 6

An empty input returns empty, never a special-cased null — the identity element is the base case. This is why allPass([]) is true and anyPass([]) is false: they are foldMap over the boolean-and and boolean-or monoids.

Real-World Applications

Type-Safe Data Processing

This example applies the same ideas to validation. safeProp represents absence with Maybe; Result preserves a typed validation error; and mapResult changes only a successful value. Validation constructs a complete User instead of asserting that a partial object is valid.

type Result<E, A> =
  | Readonly<{ kind: 'failure'; error: E }>
  | Readonly<{ kind: 'success'; value: A }>;

const failure = <E, A>(error: E): Result<E, A> => ({
  kind: 'failure',
  error
});

const success = <E, A>(value: A): Result<E, A> => ({
  kind: 'success',
  value
});

const mapResult = <E, A, B>(
  result: Result<E, A>,
  transform: Morphism<A, B>
): Result<E, B> => result.kind === 'failure'
  ? { kind: 'failure', error: result.error }
  : success<E, B>(transform(result.value));

const safeProp = <T, K extends keyof T>(
  object: T,
  key: K
): Maybe<T[K]> => {
  const value = object[key];
  return value === undefined ? nothing : just(value);
};

interface User {
  id: number;
  name: string;
  email: string;
}

type ValidationError =
  | 'A numeric id is required'
  | 'Name is required'
  | 'Email is required';

const validateUser = (
  input: Partial<User>
): Result<ValidationError, User> => {
  const { id, name, email } = input;

  if (typeof id !== 'number') {
    return failure('A numeric id is required');
  }
  if (typeof name !== 'string' || name.trim() === '') {
    return failure('Name is required');
  }
  if (typeof email !== 'string' || email.trim() === '') {
    return failure('Email is required');
  }

  return success({
    id,
    name,
    email
  });
};

const processUser = (
  input: Partial<User>
): Result<ValidationError, User> => mapResult(
  validateUser(input),
  (user) => ({ ...user, name: user.name.toUpperCase() })
);

This validateUser is fail-fast: the first failing check returns and the rest never run, so the caller sees one error at a time. That is monadic sequencing, and it is correct when a later check genuinely cannot run until an earlier one passes. When the checks are independent — as id, name, and email are here — the applicative shape is preferable: run every check and concatenate the errors through the Validation monoid so the user sees all three problems at once. The functor collects, the applicative combines, the monad sequences; choosing among them is choosing how failure composes.

Exercise

Implement a Kleisli category for monadic composition and prove the monad laws.

Resources