• Programming evolved from imperative, low-level (assembly) to more reusable (procedural, object oriented) languages
• Object oriented languages don't play well with concurrency, because they hide the wrong things: mutation and resource sharing between each other.

Mixing mutation and resource sharing: "Data races"

• Functional programming abstracts everything into functions, avoids mutations
• Every language has limits of what you can abstract "barrier of abstraction", even in haskell this is a very active frontier
• Here category theory becomes important: "Category theory is the higher level language above haskell, ml, assembly …"
• Highest possible level of abstraction that percolates down to even languages like javascript, assembly

• Category theory found similarities between many fields of mathematics ("essentially all areas of mathematics")
• Type theory not invented for computer science, but to push other frontiers in mathematics. E.g. to talk about paradoxes (e.g. Russels, barber paradox)
• Russel initiated type theory
• Curry–Howard–Lambek correspondence describes an isomorphism between logic, type theory, and category theory
• The human brain evolved to solve problems by dividing them into smaller problems, which is why these seperate fields evolved

without first seeing the "bigger" field/ theory.

• Maybe seperability / composability are not the properties of the true nature of the universe, but our brains are just built in a way that they have to see structure everywhere

The major tools in the "Toolbox" of our brain are

• Abstractiont
• Composition
• Identity (are two things replaceable on a level of abstraction) (-> Homotype type theory is a hot topic around this)

Composition and identity define category theory

A category is a "bunch" of objects. -> We don't say a "set" of objects, because of the limitations of set theory (paradoxes, sets of sets, does a set contain itself etc.) Morphisms are arrows between the objects.

Objects and morphisms are primitives of this theory with out any properties, other than arrows are between objects.

• You can have 0 or more morphisms between objects, even uncountable number of arrows. In both directions.
• Morphisms can point from an object to that same object.

• Composition in this context means: Arrows for the "transitive closure" exist.
• Objects, morphisms and there composition completely define a category.
• For every object, an identity morphism \(id\) exists that points from an object to itself.
• \(id\) obeys left and right identity law
• Morphisms also obey associativity: \((h \circ g) \circ f = h \circ (g \circ f)\)

On the side, if objects can form a set, the category is called small otherwise large.

Categories seem similar to an algebraic group, but they are not the same:

• A group would be a category with one object
• The biggest distinction is that in categories, not everything is composeable

Relation to programing: "A function is a morphism between two types"

What are types in programming languages? Simple definition: Types are sets, functions map between sets. -> When building a category to model this, we "forget" about the set elements and view these sets as "atoms" (objects). This is the "Set" category.

We throw all information away except morphisms

lambda x: x

lambda f,g:lambda x: g(f(x)) 

id = lambda x: x
comp = lambda f,g:lambda x: g(f(x)) 
plus1 = lambda x: x+1
for i in range(100):
    assert comp(plus1, id)(i) = i + 1
    assert comp(id, plus1)(i) = i + 1

from functools import lru_cache
import time
from random import randint

memoize = lru_cache(maxsize=None)


def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)


fib = memoize(fib)

before = time.time()
print(fib(333))
after = time.time()
print("memoized fib took ", after - before, " s")

randint = memoize(randint)

print(randint(1, 100))
print(randint(1, 100))
print(randint(1, 100))

import random

# if we memoize the seed it obviously works 
# because random() is deterministic
# in python we can also use Random's state:

def rand_gen(state):
    rand = random.Random()
    rand.setstate(state)
    return rand.random(), rand.getstate()


rand_gen = memoize(rand_gen)  # hash == state

state = random.Random().getstate()
result, next_state = rand_gen(state)
print(result)
result, next_state = rand_gen(next_state)
print(result)

1751455877444438095408940282208383549115781784912085789506677971125378
memoized fib took  0.0004699230194091797  s
3
3
3
0.12093689803904528
0.10506973478577686

A function is defined between sets / types where

• the set the function is defined for is the domain
• the set of reachable values is the image that is a subset of the codomain

• Void correspondence to the empty set (Falsity in logic), can be never constructed
• () is the singleton, can be always created
• functions from sinlgeton type to any type enumerate that type
• other types can be built of these two simple types

• Zero category: no objects
• One object category: One dot with one arrow to itself
• Monoid: one object arbitrarily many morphisms to itself. This is the same as a monoid in group theory,

from the category theory perspective: The associative operation is induced by composition in \(HomSet\), and the identity element is provided by \(id\). We can always extract a "classical" monoid from a "category" monoid.

• Graphs can be categories, or made into categories (nodes are objects, links are morphisms) (called "free" categories)
• The category of all categories also exists (in this context, above simple categories become important)
• \(\leq\) is also a category (preorder). Categories that correspond to preorder are called "thin" categories: Zero or one arrows between all objects.

More specific: \(\forall a,b: |C(a,b)| = 0\) or \(|C(a,b)| = 1\) where \(C(a,b)\) is the Hom-set (set of arrows) from a to b. This category gives a good example for the fact that a morphism that is mono and epic, is not invertible.