Category theory

Short synopsis on lectures about Category theory and programming

Vasya Drobushkov
8 min readApr 26, 2020


This is short synopsis of great set of lectures. What is written here is by no means true, one should refer to original lectures or some books etc. This is written mostly for myself in case I wanted to revisit the topic in the future.
Everything below is not “what it is” but mostly “how I understood that”. So, there might be mistakes and so on.


Category consists of:

  • objects / dots (a, b, c, …)
  • morphisims / arrows (f, g, …).
morphism from a into b, connects two objects
  • composition
apply g after f

And should:

  • be associative:
Order of composition doesn’t matter
  • have identity morphism
There is an arrow to itself

Category examples

Category 0 (empty)

  • no objects
  • no morphisms

Category 1 (singleton)

  • 1 object
  • 1 identity morphism

Category with 2 objects and 1 morphism

  • 2 objects
  • 1 morphism from one object to another
  • 2 identity morphisms
Applying identity morphisms to any morphism is equivalent to that morphism itself

Universal construction

  • identify pattern
  • define ranking
  • define best

Iso- / mono- / epi- morphisms


f is isomorfism
Isomorphic implies inverse morphism

Injective / monic / monomorphism

f is monomorphism

Surjective / epic / epimorphism

Order relation

Hom-set — set of all arrows from a to b.


Hom-set is either empty or singleton. Can contain loops.

Example: “less or equal” order relation.

All these arrows can hold, and there is a loop between a and b

Partial order

Pre-order without loops.

Example: “less” order relation.

Total order

All objects have relations


Category with 1 object and many morphisms from that object to itself.

Hom-set: M(m, m) — set of all arrows.

Terminal and initial objects

Terminal object — object to which there is arrow from any other object in category.

Initial object — object from which there is an arrow to any other object in category.

Opposite category is a category with “reversed arrows”. Terminal object is initial in opposite category.


c is a better product than c’ (in terms of order relation)

p, q — projections

Product in programming is a Pair:

data class Pair<A : Any, B : Any>(
val fst: A,
val snd: B

Sum (Co-Product)

Similar to Product, with reversing arrows

i, j — injections

In programming it can be described as Either:

class Either<A: Any, B: Any> 
private constructor(private val a: A?, private val b: B?) {
companion object {

fun <A: Any, B: Any> left(a: A): Either<A, B> {
return Either(a, null)

fun <A: Any, B: Any> right(b: B): Either<A, B> {
return Either(null, b)

Algebraic Data Types


  • symmetry
  • associativity
  • identity


  • symmetry
  • associativity
  • identity

Product and Sum

  • distribution
  • annihilation


With defined product and sum (without inverse operations) we get Semiring.

Example 1 Boolean

Example 2 Option

Example 3 List


Functor — mapping from one category to another with preserving structure.
Objects are mapped into objects, morphisms into morphisms.
Preserving structure means that composition and identity is preserved.

Functor can be though as a container.

Special Types of Functors

  • Faithful — injective on all hom-sets
  • Full — surjective on all hom-sets
  • Constant Δc — functor which maps all objects into single object c and all morphisms into single morphism idc
  • Endofunctor — functor from one category to the same category

Example 1 Option

  • mapping objects
  • mapping morphisms
  • preserve identity
  • preserve composition

Example 2 List

  • mapping objects

Functor in programming

interface Functor<A> {
fun <B> map(f: (A) -> B): Functor<B>



Cat — category of categories

  • objects are categories
  • morphisms are functors

Product Category


BiFunctor is mapping from product category into another category.

Sum is also a BiFunctor

BiFunctor in programming

interface Bifunctor<A : Any, B: Any> {

fun <C : Any> first(f: (A) -> C): Bifunctor<C, B>

fun <D : Any> second(f: (B) -> D): Bifunctor<A, D>

fun <C : Any, D : Any> bimap(f: (A) -> C, g: (B) -> D): Bifunctor<C, D>


ADT construction via composition

Constant Functor

data class Const<C : Any, A : Any>(val c: C): Functor<A> {

override fun <B : Any> fmap(f: (A) -> B): Const<C, B> {
return Const<C, B>(c)

Identity Functor

data class Just<A : Any>(val a: A) : Functor<A> {

override fun <B : Any> fmap(f: (A) -> B): Just<B> {
return Just(f(a))

Maybe via composition

class Maybe<A> = Either(Const<Unit, A>, Identity<A>)

Either is a BiFunctor, Const and Identity are Functors.


ProFunctor — mapping from product of category with its opposite category to that category.

interface Contravariant<A : Any> {

fun <B : Any> contramap(f: (B) -> A): Contravariant<B>

ProFunctor in programming

interface Profunctor<A : Any, B : Any> {

fun <C : Any> lmap(f: (C) -> A): Profunctor<C, B>

fun <D : Any> rmap(f: (B) -> D): Profunctor<A, D>

fun <C : Any, D : Any> dimap(f: (C) -> A, g: (B) -> D): Profunctor<C, D>



fun <A, B, C> curry(f: (Pair<A, B>) -> C): (A) -> ((B) -> C)
fun <A, B, C> uncurry(f: (A) -> ((B) -> C)): (Pair<A, B>) -> C

Cartesian Closed Category (CCC)

Category is CCC if it has:

  • product
  • exponential
  • terminal object



Proposition of types / Curry-Howard-Lambok isomorphism

Natural transformation

Natural transformation — mapping between Functors (or objects to morphisms).

Naturality square

Natural transformation is isomorphic if all components are isomorphic.

Naturatlity condition

Natural transformation in programming

NT in programming is polymorphic function.


fun <A> List<A>.head(): Option<A> {
return if (this.isEmpty()) None else Just(this.first())
// list.fmap().head() == list.head().fmap()

Reversing order of function application can be used in optimizations.


Functor — map container contents

Natural transformation — map container

Naturality condition says that it doesn’t matter what to do first and what second: map container or map container contents.

Examples of Natural Transformations


Monad — Monoid in category of endofunctors


Monoid object in category [C, C] (category of endofunctors) is a Monad


Applicative is a functor with:


Monad is Applicative with:

Other functions:

Final words

Lectures were great, a lot of insides on the how world is constructed, how other math disciplines are based on these very high-level thoughts. And how all of this is related to programming, which is for sure a computer science.

To make a bit of a practice made few implementations of things which were an examples throughout the course. For sure, implementation is not that great, but it is in Kotlin which is more functional than Java (but not that as Scala or Haskell). Implementations are just examples and have no real usage. If one is interested in better implementations I think it is good to take a look at arrow-kt.

Happy coding

Thanks for reading!
If you enjoyed this article you can like it by
clicking on the👏 button (up to 50 times!), also you can share this article to help others.

Have you any feedback, feel free to reach me on twitter, facebook