features of a category composability and identity and then

I started talking about the most important example of a category that we

use in programming, that's the category of types and functions, right. so in

programming we have types and functions.

But the model for types and functions is really sets, sets and

functions between sets, right. So I mean every time you design a language you have

to provide semantics for the language right?

What does it mean, certain things in language and a lot of languages are

defined using so-called operational semantics i mean the ones who actually

have semantics, right.

There are very few of them, none of the major ones. But they sort of like, have part of its semantics

defined right? And there are two ways of defining semantics one is by telling

how this thing executes right, so it's called operational semantics, because you're

defining operations of of the language. You know how one expression or

statement can be transformed into another simpler one and so on. And

the other is called denotational semantics where you actually map it into

some other area that you understand and in particular the most interesting

way of mapping this is into mathematics, right so you build a mathematical model you say "this statement in the

"language or this construct in the language corresponds some mathematical

"thing." and this mathematical thing for instance for types is a set of values. For

functions, it's a function between sets. Ok, that's why it's so important and that's why I

will just talk about type sometimes and sometimes I will say Set, sometimes i

will say type because I have this semantics in mind

Ok? So what is important is that a function in programming, especially when

you are considering you know imperative programming it's not exactly the same as

the function in mathematics right so we have to like be more specific by

"function between sets" we really understand something that in programming

would be called pure function right? And it will be a pure function and a total

function because a mathematical function is defined for every argument

not just for some arguments right? This is like the major source of problems in

programming that we have these partial functions, functions are defined for some

arguments and for other arguments they explode, right? I mean if they throw

exception that and then we catch this exception it's fine right but quite often

they don't they just

destroy the computer, explode and stuff. So, a total function is defined for all its

arguments right and these arguments are taken from some type so like if it's a

function on integers it has to be defined for all integers right? And

it's a pure function and how can you tell if a function is pure? So I have this test

for a purity of a function: a function is pure if you can memoise it which means

ah you know you can turn it into a lookup table right? Because for every

value of an argument it should return one particular value right? And you can

just remember this value, okay, you call this function once it evaluates it and then

you can remember the next time you do a lookup into a table right? So if you have

like you know, types that are finite that only have a finite number of

elements like boolean right then it's really easy to tabulate them,

functions on characters if it's just ASCII characters, they are really easy to tabulate

right, all these functions like `isAlpha`, you know, or `isPrintable`, they

are all actually tabulated, so they are very fast.

Now functions on, let's say integers or strings, they usually cannot be

tabulated right but that's only a problem because of resources right? If we

had infinite resources we could tabulate it. So ask yourself the question "can I

actually memoise this function?" and for instance a function like `getChar` cannot

be memoised, right? You call it once and then you say "Oh, it returned 'h', good.

"I'll just remember it and from now on whenever somebody calls function getChar I will return 'h'

"and that's it". No, you can't do this, right, so this is not a pure function. Now of course

you might say "okay, but how can you program using only pure functions" right?

We need things like side effects

So all this stuff can be described on top of pure functions, but

what we really want is to get to the bottom of the abstraction like what is the

lowest level (or the highest level of abstraction depending on how you look at it) right?

so what is the atom, what are the building blocks

what are the simplest building blocks from which we can build more

complex stuff right? Using again the same idea of composability so first we want

to decompose the problem, get to the little blocks at the bottom, and then

recompose stuff from there.

So when we are decomposing this idea of using procedures and data types and so

on, we eventually get to the bottom and that's pure functions. So on top of your

functions we can be building more complex stuff, including things like I/O

So now that we have this category of types and functions, right and I talked a little

bit about this, now let me expand on functions, because functions are very

interesting, there's much more to know about functions than we usually consider

right? So they are really interesting beasts. Even these pure

functions right? Total pure functions. We have to look at them from a

slightly different perspective- from a perspective of how we can use them

as morphisms in our category right? The category Set

which contains sets and functions between sets.

So functions are defined in mathematics as special kinds of relations

ok what's a relation? Relation is, you know, take two sets they have elements

right. Now we're talking about set as in set theory, not as a category. In a category

won't be able to look at elements, but in set theory we can look at elements right? A relation is

just a subset of pairs of elements

So it's just a pairing of things, we say this element in a relation

with this element, ok? And again as I explained we are using our brains to

understand these things and here we are like talking about relationships so

this is, you know our relationship frame, talking about social

interactions in mathematics.

Yes you have a question > Does the relation have to be total?

In general? No.

We're just talking about general relations in mathematics right?

So we say ok, this person is in a relation with this person and they are, lets say friends.

So this guy's a friend of this guy maybe this guy's not a friend of this

guy so the relation doesn't have to be symmetric you know? So, let me define a

relation okay?

First of all what is a set of pairs? A set of pairs in mathematics is called a

Cartesian product, right? So we have two sets, S1 and S2, and we can do

a Cartesian product of it so all elements from one set are paired with

all possible evidence from the other set so the set of all pairs forms the

Cartesian product. Now we take a subset of this Cartesian product, we just pick

some pairs, randomly or not, you know, if they are meaningful. We just

pick a subset and any subset of this Cartesian product is a relation by

definition that's a relation ok? So there are no other requirements, just a subset of

the Cartesian product, that's a relation.

So in this sense relation does not have a directionality, right, whereas functions

functions have direction functions are these arrows so this is one of the most

important things to understand, that functions have some kind of

directionality. So what kind of condition do we have to impose on the

relation for it to become a function? And in a relation we can have this element

you know, pick an element in this set, it can be in relation with many elements in this

other set right? And vice versa, an element from set can be in relation–

(well okay I'm drawing, putting these arrows in this direction). So many elements from set S1 can be

in relation with a single element in set 2, or one element from set 1

can be in relation with many elements from set 2, both are ok for every

relation. One of them is not okay for functions.

(I need an eraser)

I'm not gonna use my hand!

Which one is bad for a function? The top one right? One element, one argument of a

function cannot be mapped into a bunch of things. It has to be mapped to one thing

ok? It's still ok for multiple arguments to be mapped into the same value for a

function, but not the other way. So that's where the directionality comes from. Last,

we want to be considering total functions for our category right? So this

whole set has to be mapped. All elements of this set must be mapped into something in this other set

Ok? However it's not true that all the elements from this set have to

counter, you know, have to come from this set. So this could be a subset that's being mapped

Ok? Now these things have names so let me name these things for future reference

so that we can talk about them easily. So if you have a function f,

(so this is like a graph of the function f) this is called the domain

of a function, right? The domain of the function is just this set from

which we have started, the whole set.

that's its domain. This set is called the codomain.

And this subset that was obtained by mapping the whole domain is usually

called the image of the function.

Ok?

So functions are not symmetric in this way, you

see? This is the whole set, this could be a subset. Multiple elements can be

merged into one element but not vice versa.

So there is this directionality and this directionality is very important

That's a very important intuition about functions, and this is

not only an intuition about functions because later we'll see that in

category theory also we have all kinds of other mappings, we have mappings between

categories called functors, we have mappings between functors which are called natural transformations

and so on. All these mappings have the same kind of

directionality, ok? And the simplest way to understand this directionality

is asking "is the function invertible?". Like, if I go from here to here is it

possible to go back?

And usually it's not. So if there is a function f from some A to B, you

know, there isn't always a function that goes the other way around, that is the

inverse of this function. How do we define an inverse of a function?

Well, if you have a function that goes from A to B, and I will be

using this notation that is just taken from Haskell,

So f is a function, double colon means "this is the type of function",

the type of function, it goes from a to b. Alright so this is set A, set B, type a type b.

Ok? So this function is invertible if there is another function that goes in

the other direction, from b to a. That's the inverse of this one, what does

it mean? It means that g after f equals id.

Ok? So if you first go f to B and then go back from B to A using g, you should end up

in the same, exactly the same point. So if you have an x here, x maps it to

some y here and then you apply g to y, you should get back to x ok? That

means the inverse, ok, but we can compose them two ways right? So g after f is one,

but there's also a composition f after g and this one also has to be an identity.

So we go g first and then f, and you should end up at the same point ok? So this makes it

symmetric. So a function that's invertible is automatically symmetric ok?

And the function that is invertible is called isomorphism.

So this is the definition of isomorphism and notice an interesting thing:

this is in the language of categories.

Maybe with a little bit of additional notation, if f goes from A to B and g

goes from B to A then this is an identity in which object? In A. Right? So

Now let's forget about this picture and say A, B, this is f, this is g.

Ok? So g after f, I'll get identity on a. and then f after g, is the same as

identity on b. Okay, and I have written this in categorical language, I'm not talking

anymore about elements, right? Here I was talking about elements of sets, I

don't need to. Okay? Now I can go back to categories and say "this is a definition

of isomorphism in any category". Not only in a category of sets, in any category because

it's expressed in terms of composition and identity, nothing else, right? So f is

an isomorphism if there exists a g with these properties

Ok?

So isomorphisms are great because isomorphisms, like, identify two

sets they say "this set really looks like this set", that there's like one to one

mapping between elements of these sets right? So that's, you know, if this is a two

element set and this is a two element set, you know I have a mapping between

these elements. That's great, right? For my purposes they are sort of like

identical right? It's not really identity, it's isomorphism, but I have an

identification between these two sets. So for finite sets you know an isomorphism

is just an identification of elements, this element corresponds to this, this

corresponds to this and so on,

one-to-one correspondence. For infinite sets, of course, this is a little bit more

complicated. For instance you can have a one-to-one correspondence between

natural numbers and even numbers.

y = 2x

even numbers. Or odd numbers

Right? These are functions that are invertible. Is that true?

No, but if this is a set of even numbers, right, so let's say this is a

set of even numbers (not the set of all numbers, just a set of even numbers) and this

is the set of all numbers, and then I have one-to-one correspondence between

even numbers and all numbers, right?

That's because they are infinite and for infinite sets you can do tricks like

these, but if this is a natural number and this is, say, you know

real numbers, right? Real numbers.

Now you know that there is no correspondence like this right? Do you know that?

There's a good argument, that [...]

But that's just a side remark, right. So just to make you aware of the fact that

isomorphisms kinda tell you that these two things are for some intents and purposes identical

But most functions are not isomorphisms, right?

Most in a sense of, I dunno, most functions that we deal with are not

isomorphisms and there are two reasons for a function not to be an isomorphism,

Ok? So you have to have good reasons not to be an isomorphism. One reason is because

the function can collapse elements of a set, right? So it takes multiple

multiple elements of this set are mapped to a single element of this set, so let me be

more precise here, just focus on one thing

so you have some x_1 and you have some x_2, and function f maps both of these elements to the same y.

Ok? For instance, let's see, a function `isEven`, which returns a boolean, right?

So `isEven` maps every even number into this one element of the boolean called true.

All even numbers are mapped to true, all odd numbers are mapped false so lots,