1 of 35

Categories For Noobs

Vlad Patryshev

2016

http://tinyurl.com/coen260-16-f

2 of 35

In This Crash Course

database example
terminal object, initial object
products, unions
equalizers
pullbacks
functors and examples (diagrams; product; exponentiations)
currying/yoneda lemma
example with integers/rationals
monads

3 of 35

Pet Database

create type kind as enum (‘cat’, ‘dog’, ‘fly’, ‘hamster’, ‘e.coli’);

create table Person (id bigint, name varchar(80), pet bigint,

primary key (id),

constraint pet_fk foreign key pet references Animal(id));

create table Animal (id bigint, kind kind, name varchar(80), owner bigint,

primary key (id),

constraint owner_pk foreign key owner references Person(id));

4 of 35

“Conceptual Model”

Person
name

Animal

kind
{cat, dog, fly, hamster, e.coli}

‘owner’

‘pet’

‘kind’

Can compose!

kind(pet(owner(pet(“John”)))

select kind from Animal a where a.owner in (select id from Person where pet in (select id from Animal where owner in (select id from person where name=’John’)));

5 of 35

Some Types

Int

toLong

Can compose, but… are they functions?

We don’t care

It’s just a picture

toInt∘toString = identity

toLong∘toString = identity

toString∘toLong = toString

Long

String

Unit

toInt

toLong

toString

toInt

toString

6 of 35

Define: Category

Objects A,B,C,...
Arrows f:A→B, etc
Composition of arrows�f:A→B, g:B→C gives h=g∘f:A→C
Associativity: (h∘g)∘f = h∘(g∘f)
Identity: f∘id_A = f, id_A∘g=g (for g:X→A)

7 of 35

E.g. matrices

A[m,n]×B[n,k]
Associative
Identity Id[n,n]

(what are the objects?)

8 of 35

Not all objects are equal

Initial object
Terminal object
Objects built from other objects (products, unions, equalizers, pullbacks, pushouts)

How?

9 of 35

Initial Object in a Category

Definition. In a category C, Initial Object is an object 0 with a unique arrow i_X:0 → X for any given X. (this is its “universal property”)

Note that if we take X=0, we see that there is just one arrow 0 → 0. Can you name a set (or two) with only one function S→S?

What if there’s more? Say 0₁ and 0₂, both having feature.

Then, for 0₁, we have a unique a:0₁ → 0₂; and similarly we have a unique b:0₂ → 0₁. Composing a and b either way, we get an identity.

An Initial Object is unique up to an isomorphism.

10 of 35

Examples of Initial Objects

Sets: ∅, and it is unique (by sets axioms)
Monoids: {0} - all “such monoids” are isomorphic
Categories: empty category (whether there’s a plurality of them…)
No initial object in this category of three objects:
In this category c is initial object:
How about more than one

initial object?

They are

isomorphic!

11 of 35

Terminal Object in a Category

Definition. In a category C, Terminal Object is an object 1 with a unique arrow u_X:X → 1 for any given X. (this is its “universal property”)

For X=1, we see that there is just one function 1 → 1, same as with 0.

What if there’s more? Say 1₁ and 1₂. Then there’s a unique a:1₁ → 1₂; and similarly we have a unique b:1₂ → 1₁. Composing a and b either way, we get an identity; so they are isomorphisms.

A Terminal Object is unique up to an isomorphism.

12 of 35

Examples of Terminal Objects

Sets: any singleton {x} is terminal. They are not equal, but are isomorphic.
Monoids: {0} - all “such monoids” are isomorphic
Categories: Singleton Category (whether there’s a plurality of them…)
In this category of three objects there’s no terminal object:
In this category c is terminal object:

13 of 35

Initial and Terminal Object in our DB

terminal

14 of 35

Cartesian Product

Definition. Given a category C, and two objects in it, X and Y, their Cartesian Product is such an object Z=X×Y, together with two arrows (projections), p_X:Z→X and p_Y:Z→Y, that for any pair f:A→X and g:A→Y, f=p_X∘h and g=p_Y∘h for some unique h. (this is its “universal property”)

Cartesian product is unique up to an isomorphism. (proof?)

15 of 35

Examples of Cartesian Products

Sets: AxB = {(a,b)|a∈A,b∈B}, and it is unique (by sets axioms)
Databases: select * from A,B;
Good programming languages, e.g. Scala: (A,B)

val intWithString: (Int, String) = (42, “Hello 42”)

In a monoid? We have just one object… so?
In a partial order? It’s min(a,b)

16 of 35

Disjoint Union (dual to Product)

Definition. Given a category C, and two objects, X and Y, their Disjoint Union is such an object Z=X+Y, together with two arrows, i_X:X→Z and i_Y:Y→Z, that for any pair f:X→A and g:Y→A, f=h∘i_X and g=h∘i_Y for some unique h. (this is its “universal property”)

Disjoint union is unique up to an isomorphism. (proof?)

17 of 35

Examples of Disjoint Unions

Sets: A+B = A⊔B, and it is unique (by sets axioms)
Databases: select * from A union B;
Good programming languages, e.g. Scala: Either[A,B]

val intOrString: Either[Int, String] = Left(42)// Right(“Hello 42”)

In a partial order? It’s max(a,b)

18 of 35

Equalizers

Definition. Given a category C, two objects in it, X and Y, and two arrows, f,g:X→Y, their Equalizer is an object E=Eq(f,g), together with an arrow eq:E→X, such that that f∘eq=g∘eq , and for any m:O→X, such that f∘m=g∘m, m=eq∘u for some unique u. (this is its “universal property”)

An equalizer is unique up to an isomorphism. (proof?)

select * from X where X.f=X.g;

In this case, the arrow eq is the inclusion of this selection into the whole X.

19 of 35

Pullbacks

Definition. Given a category C, and three objects, X,Y and Z, and two arrows, f:X→Z and g:Y→Z, their Pullback is such an object X×_ZY, together with arrows (projections) p_X:X×_ZY→X and p_Y:X×_ZY→Y, such that g∘p_Y = f∘p_X, and for any pair x:U→X, y:U→Y,such that gy=fx, the following holds:

x=p_X∘h and y=p_Y∘h for some unique h. (this is its “universal property”)

A pullback is unique up to an isomorphism. (proof?)

20 of 35

Examples of Pullbacks

Sets: {(x,y)|x∈X,y∈Y,f(x)=g(y)}
Databases: select * from A, B where A.f=B.g;

e.g. select * from Person A, Person B where A.pet=B.pet;

In a poset? Same as min.
Cartesian products are pullbacks (over what?)

21 of 35

Functor

It is just an arrow in the category of all categories

22 of 35

Functor

Given categories A and B, a functor F: A → B

consists of mappings F_o: Objects(A) → Objects(B)

and F_a: Arrows(A) → Arrows(B),

so that

F(id_X)=id_F(X)

and F(f∘g)=F(f)∘F(g)

23 of 35

Example: Parametric Class

trait List[A] extends Iterable[A] {

def map[A](f:A=>B):List[B]

}

24 of 35

Examples

A = 3 , B=Sets; what is a functor 3 → Sets?

Have to define: sets F(0), F(1), F(2); functions F(f), F(g), F(gf)

Any f:X→Y in category C is a functor from 2 to C.

25 of 35

Cartesian Product is a Functor

Choose an object A. X ↦ X×A is a functor.

How does it work on arrows? f:X→Y ↦ f×id_A: X×A → Y×A

26 of 35

+1 is a Functor

In Sets, take X ↦ X+1. f: X→Y ↦ (f+1): X+1 → Y+1

This functor is called Option[T].

27 of 35

Category of Categories

Take functors F:A→B, G:B→C; their composition H=G∘F is also a functor.

H(id_X) = G(F(id_X)) = G(id_F(X)) = id_G(F(X))

H(p∘q) = G(F(p∘q)) = G(F(p)∘F(q)) = G(F(p))∘G(F(q)) = H(p)∘H(q)

Identity functor Id_A:A→A Id(f) = f

Cat - a category of all categories.

No barber problems, nobody shaves nobody.

28 of 35

Exponential Functor

A, B - objects in category C. B^A - an object of functions from A to B, if such exists.

E.g. in Sets, {f:A→B}.

In Scala	In old Java (Guava) (https://code.google.com/p/guava-libraries/wiki/FunctionalExplained)
trait Function[X,Y] { def apply(x:X): Y }	interface Function<X,Y> { Y apply(X x); }
val len:Function[String, Int] = _.length	Function<String, Integer> lengthFunction = new Function<String, Integer>() { public Integer apply(String string) { return string.length(); } };

29 of 35

Define Exponential via Currying

In Sets, f:A→C^B ≡ f’:A×B→C

f(x)(b) = f’(x,b)

Very similar to P⊢(Q→R) ≡ P∧Q ⊢ R

Actually… it’s the same thing.

Take a partial order, for example, a Boolean lattice,

where a×b ≡ min(a,b) ≡ a∧b

a∧b ≤ c ≡ a ≤ (b→c)

30 of 35

Currying: Yoneda Lemma

Arrows(A×B, C) ≡ Arrows(A, C^B)

(Caveat: what is Arrows? A set? It’s not always available as a set)

31 of 35

Monad

* f:F(X)->G(X) is natural if for all p:X→ Y

Given a category C, an endofunctor M: C → C

is called a Monad if it has two features:

unit_X: X → M(X)
flatten_X: M(M(X)) → M(X)

These two arrows must be natural*

32 of 35

Example with Lists

Category Scala

Take functor List.

We see two properties:

singleton: X → List[X]
flatten: List[List[X]] → List[X]

Do you see a monad?

33 of 35

Example with Numbers

Category ℤ = (ℤ,≤); category ℚ = (ℚ,≤)

Inclusion i_z: ℤ ↣ ℚ - preserves order, so is a functor.

How about ℚ → ℤ? Upb: q ↦ Upb(q)

Upb(q) ≤ n /* this is in Z */ ≡ q ≤ n /* this is in Q */

Take composition q ↦ i_Z(Upb(q)), call it Int.